Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements

S. A. Lozhkin ; V. S. Zizov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 322-334

Résumé

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.

Détail

Keywords: functional elements, switching elements, area, decoder, asymptotic estimates.
Mots-clés : cellular circuits