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

S.A. Lozhkin^∗ , V.S. Zizov^∗∗

Lomonosov Moscow State University, Moscow, 119991 Russia

E-mail: ^∗lozhkin@cs.msu.ru, ^∗∗vzs815@gmail.com

Received August 12, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.322-334

For citation: Lozhkin S.A., Zizov V.S. 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, 2020, vol. 162, no. 3, pp. 322–334. doi: 10.26907/2541-7746.2020.3.322-334. (In Russian)

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 B0 consisting of Boolean functions x1 & x2, x1 ∨ x2, ˉx1. In this model, both inputs and outputs of the cellular circuit Σ associated with various input and output Boolean variables, respectively, are irreversibly located on the border of the corresponding rectangular lattice, and the cellular circuit Σ itself corresponds, structurally and functionally, to a scheme of functional elements S in the basis B₀ with the same sets of input and output Boolean variables.

We studied the complexity (area) of cellular circuits with n inputs and 2ⁿ outputs that implements a system of all 2ⁿ 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,…, is equal to n2ⁿ⁻¹(1+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 O(1/n), were obtained for it.

Keywords: functional elements, switching elements, cellular circuits, area, decoder, asymptotic estimates

Acknowledgments. The study was supported by the Moscow Center for Fundamental and Applied Mathematics and the Russian Foundation for Basic Research (project no. 18-01-00800).

References

1. Kravtsov S.S. Realization of Boolean functions in a class of circuits of functional and switching elements. Probl. Kibern., 1967, no. 19, pp. 285–292. (In Russian)
2. Al’brekht A. Circuits from cellular elements. Probl. Kibern., 1975, no. 33, pp. 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, pp. 36–39. (In Russian)
4. Lozhkin S.A. On the complexity and area of cellular decoders. Problemy teoreticheskoi kibernetiki: Tez. dokl. XIV Mezhdunar. konf. [Problems of Theoretical Cybernetics: Proc. XIV Int. Conf.]. Moscow, Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., 2005, p. 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. Materialy VIII Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya” [Proc. VIII Int. Semin. “Discrete Mathematics and Its Applications”]. Moscow, Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., 2004, pp. 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. Problemy teoreticheskoi kibernetiki: Tez. dokl. IX Vsesoyuz. konf. [Problems of Theoretical Cybernetics: Proc. IX All-Union Conf.]. Volgograd, 1991, pt. 1, p. 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, pp. 68–72. (In Russian)
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, pp. 32– 41.
9. Shkalikova N.A. Realization of Boolean functions by circuits of cell elements. Mat. Vopr. Kibern., 1989, no. 2, pp. 177–197. (In Russian)
10. Hromkovich Yu., Lozhkin S., Rybko A., Sapozhenko A., Shkalikova N. Lower bounds on the area complexity of Boolean circuits. Theor. Comput. Sci., 1992, vol. 97, no. 2, pp. 285–300. doi: 10.1016/0304-3975(92)90079-U.
11. Zhukov D.A. On the computation of partial Boolean functions by cellular schemes. Diskretn. Anal. Issled. Oper. Ser 1, 2004, vol. 11, no. 2, pp. 32–40. (In Russian)
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, 2012, vol. 1, no. 4, pp. 225–231. (In Russian)
13. Thompson C.D. A complexity theory for VLSI. PhD Thesis. Pittsburgh, PA, Carnegie Mellon Univ., 1980. 148 p.
14. Chazelle B., Louis M. A model of computation for VLSI with related complexity results. J. Assoc. Comput. Mach., 1985, vol. 32, no. 3, pp. 573–588.
15. Bilardi G., Pracchi M., Preparata F.P. A critique of network speed in VLSI models of computation. IEEE J. Solid-State Circuits, 1982, vol. 17, no. 4, pp. 696–702. doi: 10.1109/JSSC.1982.1051799.
16. Kalachev G.V. Order of power of planar circuits implementing Boolean functions. Discrete Math. Appl., 2014, vol. 24, no. 4, pp. 185–205. doi: 10.1515/dma-2014-0018.
17. Kalachev G.V. On the simultaneous minimization of area, power, and depth of planar circuits implementing Boolean operators. Intellekt. Sist. Teor. Prlozh., 2016, vol. 20, no. 2, pp. 203–266. (In Russian)
18. Kalachev G.V. On power complexity of planar circuits. Cand. Phys. Mat. Sci. Diss. Moscow, 2017. 167 p. (In Russian)
19. Lozhkin S.A. Lektsii po osnovam kibernetiki [Lectures on Principles of Cybernetics]. Moscow, Izd. Otd. Fak. VMiK MGU, 2004. 253 p. (In Russian)
20. Lozhkin S.A. Exact bounds on the complexity of circuits of some classes. Mat. Vopr. Kibern., 1996, no. 6, pp. 189–214. (In Russian)
21. Cheremisin O.V. On the activity of cell circuits realising the system of all conjunctions. Discrete Math. Appl., 2003, vol. 13, no. 2, pp. 209–219. doi: 10.1515/156939203322109159.

The content is available under the license Creative Commons Attribution 4.0 License.