|
This article is cited in 4 scientific papers (total in 4 papers)
Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements
S. A. Lozhkin, V. S. Zizov footnotesize Lomonosov Moscow State University, Moscow, 119991 Russia
Abstract:
The model of cellular circuits was considered in a single basis of functional and switching elements, which is built in accordance with the standard basis $\text{B}_0$ consisting of Boolean functions $x_1 \& x_2, $ $x_1\lor x_2,$ $ \overline{x_1}$. In this model, both inputs and outputs of the cellular circuit $\Sigma$ associated with various input and output Boolean variables, respectively, are irreversibly located on the border of the corresponding rectangular lattice, and the cellular circuit $\Sigma$ itself corresponds, structurally and functionally, to a scheme of functional elements $S$ in the basis $\text{B}_0$ with the same sets of input and output Boolean variables.
We studied the complexity (area) of cellular circuits with $n$ inputs and $2^n$ outputs that implements a system of all $2^n$ elementary conjunctions of rank $n$ from input Boolean variables, i.e., a binary decoder with power $n$. It was proved that the smallest possible area of a cellular circuit implementing such a decoder, provided that $n = 1, 2, \dots$, is equal to $n2^{n-1}(1+\mathcal{O}({1}/{n}))$. This is the first time when so-called asymptotic estimates of a high degree of accuracy, i.e., estimates with a relative error $\mathcal{O}({1}/{n})$, were obtained for it.
Keywords:
functional elements, switching elements, cellular circuits, area, decoder, asymptotic estimates.
Received: 12.08.2020
Citation:
S. A. Lozhkin, V. S. Zizov, “Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 162, no. 3, Kazan University, Kazan, 2020, 322–334
Linking options:
https://www.mathnet.ru/eng/uzku1564 https://www.mathnet.ru/eng/uzku/v162/i3/p322
|
Statistics & downloads: |
Abstract page: | 248 | Full-text PDF : | 121 | References: | 11 |
|