On the structure, complexity, and depth of the circuits over the basis {&,˅} realizing step Boolean functions

S.A. Lozhkin^∗ , D.S. Kinzhikeyeva^∗∗

Lomonosov Moscow State University, Moscow, 119991 Russia

E-mail: ^∗lozhkin@cs.msu.ru, ^∗∗kinzhikeyeva@yandex.ru

Received August 11, 2020

Full text PDF

DOI: 10.26907/2541-7746.2020.3.335-349

For citation: Lozhkin S.A., Kinzhikeyeva D.S. On the structure, complexity, and depth of the circuits over the basis {&, ∨} realizing step Boolean functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 335–349. doi: 10.26907/2541-7746.2020.3.335-349. (In Russian)

Abstract

The step Boolean function is a function of the algebra of logic of n Boolean variables, n = 1, 2, … , reducing to 1 on all of the sets of an n -dimensional unit cube, the ordinal numbers of which are not lower than the given set. In this paper, the problem of synthesis of circuits over the basis {&, ∨} realizing step Boolean functions was considered. The optimized structure of the given circuits was studied with regard to complexity and depth. Step functions often appear in theoretical and applied tasks as an auxiliary subfunctions. For instance, an n- bit adder contains such a subfunction.

Keywords: Boolean circuits, basis {&, ∨}, step Boolean functions, complexity and depth minimization, structure of minimal circuits

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. Khrapchenko V.M. Asymptotic estimation of addition time of a parallel adder. Probl. Kibern., 1967, no. 19, pp. 107–122. (In Russian)
2. Grinchuk M.I. Sharpening an upper bound on the adder and comparator depths. J. Appl. Ind. Math., vol. 3, no. 1, pp. 61–67. doi: 10.1134/S1990478909010086.
3. Lupanov O.B. Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem [Asymptotic Estimates of Complexity of Control Systems]. Moscow, Izd. Mosk. Univ., 1989. 138 p. (In Russian)
4. Lozhkin S.A. Lektsii po osnovam kibernetiki [Lectures on Principles of Cybernetics]. Moscow, Izd. Otd. Fak. VMiK MGU, 2004. 253 p. (In Russian)
5. Lozhkin S.A., Kinzhikeyeva D.S. On the structure, complexity, and depth of the circuits over the basis {&, ∨} realizing step Boolean functions. Problemy teoreticheskoi kibernetiki: Materialy zaochnogo seminara XIX Mezhdunar. konf. [Problems of Theoretical Cybernetics: Proc. Virtual Semin. XIX Int. Conf.]. Zhuravlev Yu.I. (Ed.). Kazan, Izd. Kazan. Univ., 2020, pp. 72–75. (In Russian)
6. Kinzhikeyeva D.S. Methods for synthesis of circuits from certain classes realizing step functions, estimates of their complexity and depth. Master’s Thesis. Moscow, Mosk. Gos. Univ. im. M.V. Lomonosova, Fak. Vychisl. Mat. Kibern., Kafedra Mat. Kibern., 2020. 27 p. (In Russian)
7. Vlaskin V.M. On the complexity and depth of circuits realizing step functions. Graduation Thesis. Moscow, Mosk. Gos. Univ. im. M.V. Lomonosova, Fak. Vychisl. Mat. Kibern., Kafedra Mat. Kibern., 1995. 13 p. (In Russian)

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