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

Bibliographie

[1] Kravtsov S. S., “Realization of Boolean functions in a class of circuits of functional and switching elements”, Probl. Kibern., 19, 1967, 285–292 (In Russian)

[2] Al'brekht A., “Circuits from cellular elements”, Probl. Kibern., 33, 1975, 209–214 (In Russian)

[3] Gribok S. V., “On a basis for circuits from cellular elements”, Vestn. Mosk. Univ. Ser. 15. Vychisl. Mat. Kibern., 1999, no. 4, 36–39 (In Russian) | MR | Zbl

[4] Lozhkin S. A., “On the complexity and area of cellular decoders”, Problems of Theoretical Cybernetics, Proc. XIV Int. Conf., Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., M., 2005, 88 (In Russian)

[5] Lozhkin S. A., Evdokimova T. N., “On the complexity of realization of some systems of functions in a class of generalized cellular circuits”, Proc. VIII Int. Semin. “Discrete Mathematics and Its Applications”, Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., M., 2004, 61–63 (In Russian)

[6] Lozhkin S. A., Pashkovskii A. M., “On the complexity of realization of some systems of Boolean functions using cellular and planar circuits”, Problems of Theoretical Cybernetics, Proc. IX All-Union Conf. (Volgograd, 1991), v. 1, 28 (In Russian)

[7] Gribok S. V., “On the asymptotics of complexity of a cellular contact decoder”, Vestn. Nizhegorod. Gos. Univ. Mat. Model. Optim. Upr., 2000, no. 1, 68–72 (In Russian) | Zbl

[8] Lozhkin S. A., Evdokimova T. N., “On the asymptotics of complexity of a universal cellular contact multiterminal circuit”, Moscow Univ. Comput. Math. Cybern., 2005, no. 4, 32–41 | MR | Zbl

[9] Shkalikova N. A., “Realization of Boolean functions by circuits of cell elements”, Mat. Vopr. Kibern., 2, 1989, 177–197 (In Russian) | MR

[10] Hromkovich Yu., Lozhkin S., Rybko A., Sapozhenko A., Shkalikova N., “Lower bounds on the area complexity of Boolean circuits”, Theor. Comput. Sci., 97:2 (1992), 285–300 | DOI | MR

[11] Zhukov D. A., “On the computation of partial Boolean functions by cellular schemes”, Diskretn. Anal. Issled. Oper. Ser. 1, 11:2 (2004), 32–40 (In Russian) | MR | Zbl

[12] Yablonskaya A.Yu., “On realization of the complexity of Boolean functions from invariant classes by cellular circuits with limited height and multiple inputs”, Vestn. Nizhegorod. Univ. im. N.I. Lobachevskogo, 1:4 (2012), 225–231 (In Russian)

[13] Thompson C. D., A complexity theory for VLSI, Ph.D. Thesis, Carnegie Mellon Univ., Pittsburgh, PA, 1980, 148 pp.

[14] Chazelle B., Louis M., “A model of computation for VLSI with related complexity results”, J. Associat. Comput. Machinery, 32:3 (1985), 573–588 | DOI | MR | Zbl

[15] Bilardi G., Pracchi M., Preparata F. P., “A critique of network speed in VLSI models of computation”, IEEE J. Solid-State Circuits, 17:4 (1982), 696–702 | DOI

[16] Kalachev G. V., “Order of power of planar circuits implementing Boolean functions”, Discrete Math. Appl., 24:4 (2014), 185–205 | DOI | MR | Zbl

[17] Kalachev G. V., “On the simultaneous minimization of area, power, and depth of planar circuits implementing Boolean operators”, Intellekt. Sist. Teor. Prlozh., 20:2 (2016), 203–266 (In Russian) | MR

[18] Kalachev G. V., On power complexity of planar circuits, Cand. Phys. Mat. Sci. Diss., M., 2017, 167 pp. (In Russian)

[19] Lozhkin S. A., Lectures on Principles of Cybernetics, Izd. Otd. Fak. VMiK MGU, M., 2004, 253 pp. (In Russian)

[20] Lozhkin S. A., “Exact bounds on the complexity of circuits of some classes”, Mat. Vopr. Kibern., 6, 1996, 189–214 (In Russian) | MR

[21] Cheremisin O. V., “On the activity of cell circuits realising the system of all conjunctions”, Discrete Math. Appl., 13:2 (2003), 209–219 | DOI | MR | Zbl