The search for subsystems of related functions from multilevel representation of systems of Boolean functions1
https://doi.org/10.37661/1816-0301-2020-17-1-63-77
Abstract
One of the directions of logical optimization of multilevel representations of systems of Boolean functions is the methods based on the search of subsystems of functions that have the same parts in the domains of functions of selected subsystems. Such subsystems are called related. The good relationship of functions leads to the appearance of a large number of identical structural parts (conjunctions, algebraic expressions, subfunctions, etc.) in optimized forms of representation of functions which are used in the construction of combinational logic circuits. The more the functions of the selected subsystem are related, the sooner it is expected that in the representations of the functions of this subsystem will be more identical subexpressions and synthesized logic circuits will have less complexity.
We describe software-implemented algorithms for extracting subsystems of related functions from a BDD representation of a system of Boolean functions based on introduced numerical estimates of the relationship of BDD representations of functions. The relationship of Boolean functions is the presence of Boolean vectors, where the functions take the value as one, or of the same equations in BDD representations. BDD representations of Boolean functions are compact forms defining functions and are constructed as the result of Shannon decomposition of the functions of the original system (resulting from the decomposition of subfunctions) by all variables, which the functions of the original system depend on. The experiments show the effectiveness of proposed algorithms and programs in the synthesis of logic circuits from logic elements library.
About the Authors
P. N. Bibilo
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Petr N. Bibilo, Dr. Sci. (Eng.), Professor
Belarus
Petr N. Bibilo, Dr. Sci. (Eng.), Professor
A. M. Pazniak
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Andrei M. Pazniak, Undergraduate
Belarus
Andrei M. Pazniak, Undergraduate
References
1. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Sintez mnogourovnevyh kombinacionnyh logicheskih skhem [Synthesis of multi-level combinational logic circuits]. Trudy Institute inzhenerov po jelektronike i radiotehnike [Proceedings of the Institute of Electronics and Radio Engineering], 1990, vol. 78, no. 2, рр. 38–83 (in Russian).
2. Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. L. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.
3. Zakrevskij A. D., Pottosin Ju. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Bases of Design of Discrete Devices. Moscow, Fizmatlit, 2007, 592 р. (in Russian).
4. Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on the Solution of Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (in Russian).
5. Kuznecov O. P. O programmnoj realizacii logicheskih funkcij i avtomatov [On the software implementation of logical functions and automata]. Avtomatika i telemekhanika [Automation and Telemechanics], 1977, no. 7, pp. 63–74 (in Russian).
6. Akers S. B. Binary decision diagrams. IEEE Transactions on Computers, 1978, vol. C-27, no. 6, pр. 509–516.
7. Bryant R. E., Meinel C. Ordered binary decision diagrams. Logic Synthesis and Verification. In S. Hassoun, T. Sasao, R. K. Brayton. Kluwer Academic Publishers, 2002, pp. 285–307.
8. Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866–876.
9. Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (in Russian).
10. Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov Zhegalkina pri minimizacii mnogourovnevyh predstavlenij system bulevyh funkcij na osnove razlozheniya Shennona [The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion]. Programmnaya inzheneriya [Software Engineering], 2017, no. 3, рр. 369–384 (in Russian).
11. Bibilo P. N. Razbienie sistemy bulevyh funkcij na podsistemy "svyazannyh" funkcij [Partitioning a system of Boolean functions into subsystems of "related" functions]. Izvestija Rossijskoj akademii nauk. Teoriya i sistem yupravleniya [Proceedings of the Russian Academy of Sciences. Theory and control systems], 2019, no. 2, pp. 14–29 (in Russian).
12. SHlee M. Qt 5.3. Professional'noe programmirovanie na S++. Qt 5.3. Professional C ++ Programming. Saint Petersburg, BHV-Peterburg, 2015, 928 р. (in Russian).
13. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices Using a ProductionFrame Knowledge Representation Model. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).
14. Bibilo P. N., Avdeev N. A., Kardash S. N., Kirienko N. A., Lankevich Yu. Yu., …, Cheremisinova L. D. Sistema logicheskogo proektirovaniya funkcional'nyh blokov zakaznyh KMOP SBIS s ponizhennym energopotrebleniem [System for the logical design of functional blocks of custom CMOS VLSI with low power consumption]. Mikroelektronika [Microelectronics], 2017, vol. 46, no. 1, рр. 72–88 (in Russian).
15. Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum. Moscow, SOLON-Press, 2005, 384 p. (in Russian).
16. Avdeev N. A., Bibilo P. N. Effektivnost' logicheskoj optimizacii pri sinteze kombinacionnyh skhem iz bibliotechnyh elementov [The effectiveness of logical optimization in the synthesis of combinational circuits from library elements]. Mikroelektronika [Microelectronics], 2015, vol. 44, no. 5, рр. 383–399 (in Russian).
17. Jeong C. Computer-aided design of digital systems. Department of Computer Science. Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed 20.03.2018).
Review
For citations:
Bibilo P.N., Pazniak A.M. The search for subsystems of related functions from multilevel representation of systems of Boolean functions1. Informatics. 2020;17(1):63-77. (In Russ.) https://doi.org/10.37661/1816-0301-2020-17-1-63-77
Views: 669
Email this article 