ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 2. Vol. 29. 2023

DOI: 10.17587/it.29.59-71

P. N. Bibilo, Dr. Sci. (Eng.), Professor, Yu. Yu. Lankevich, Researcher, V. I. Romanov, Ph. D. (Eng.), Associate Professor, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus,
Minsk, 220012, Republic of Belarus

Logical Minimization of Multilevel Representations of Boolean Function Systems

A decisive influence on complexity and speed of a combinational logic circuit of library CMOS elements is exerted by the preliminary stage of technologically independent optimization of the implemented system of Boolean functions. At present, the main methods of such optimization in the logical synthesis of custom CMOS VLSI blocks are methods for minimizing binary decision diagrams — Binary Decision Diagrams (BDD) or their modifications. Graphical representations of BDD are built on the basis of the Shannon expansions of Boolean functions. A BDD graph corresponds to a set of interrelated Shannon expansion formulas that form a multilevel representation of the minimized system of Boolean functions. The efficiency of applying various optimization procedures of minimization for several types of BDD representations of systems of Boolean functions is investigated in the paper. 7hese procedures are used as a technologically independent optimization in the synthesis of multi-output logic circuits of library CMOS elements. In addition to single logical optimization procedures, sequences of such procedures are studied that form various methods of logical optimization of multilevel representations of systems of Boolean functions. The results of experiments on 49 examples of systems of Boolean functions are presented. 25 optimization routes have been studied, efficient routes have been determined for various types of specifications of function systems. The obtained experimental results are compared with the known ones. It has been established that to estimate the complexity of optimized algebraic representations of systems of functions, it is advisable to use such a criterion as the total number of literals (variables or their inversions) of Boolean variables.
Keywords: system of Boolean functions, Disjunctive Normal Form (DNF), Binary Decision Diagram (BDD), Boolean net, Shannon expansion, digital logic synthesis, VHDL, VLSI

P. 59–71

References

1. Zakrevskij A. D. Algorithms for the synthesis of discrete automata, Moscow, Nauka, 1971, 512 p. (in Russian).
2. Zakrevskiy A. D. ed. Synthesis of asynchronous automata on a computer, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).
3. Trevillyan L. An Overview of Logic Synthesis Systems, DAC '87: Proc. of the 24th ACM/IEEE Design Automation Conference, 1987, pp. 166—172.
4. Gavrilov M. A., Devyatkov V. V., Pupyrev E. I. Logical de­sign of discrete automata, Moscow, Nauka, 1977, 352 p. (in Russian).
5. Zakrevskij A. D. Logical synthesis of cascading circuits, Moscow, Nauka, 1981, 416 p. (in Russian).
6. Brayton K. R. et al. Logic Minimization Algorithm for VLSI Synthesis, Boston, Kluwer Academic Publishers, 1984, 193 p.
7. Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: A multiple-level logic optimization systems, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 6, pp. 1062—1081.
8. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentel­li A. L. Multilevel Logic Synthesis, Trudy Institute inzhenerov po jele-ktronike i radiotehnike, 1990, vol. 78, no. 2, pp. 38—83 (in Russian).
9. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD — Foundations and Applications, Berlin, Heidelberg, Springer-Verlag, 1998 , 267 p.
10. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation, Springer, 1998, 210 p.
11. Ebendt R., Fey G., Drechsler R. Advanced BDD optimiation, Springer, 2005, 222 p.
12. Bibilo P. N. Application of Binary Decision Diagrams in the Synthesis of Logic Circuits, Minsk, Belaruskaja navuka, 2014, 231 p. (in Russian).
13. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verication, Springer, 2017, 156 p.
14. Mailhot F., De Micheli G. Algorithms for technology mapping based on binary decision diagrams and on Boolean operations, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1993, vol. 12, no. 5, pp. 599— 620.
15. Dutta A., Baishnab K. L., Chaudhary S. A New Evolu­tionary Algorithm based BDD Optimization for Area and Power, International Journal of Electronic and Electrical Engineering, 2010, vol. 3, no 3, pp. 147—160.
16. Rudell R. Dynamic variable ordering for ordered binary decision diagrams, Computer-Aided Design: proc. of the 1993 IEEE/ACM intern. conf., Santa Clara, 7—11 Nov. 1993, IEEE Computer Society Press, Los Alamitos, 1993, pp. 42—47.
17. Ebendt R., Gunther W., Drechsler R. An improved branch and bound algorithm for exact BDD minimization, Computer-Aided Design of Integrated Circuits and Systems, 2003, vol. 22, no. 12, pp. 1657—1663.
18. Karpov Yu. G. MODEL CHECKING. Verification of parallel and distributed software systems, SPb., BHV-Peterburg, 2010, 560 p. (in Russian).
19. Chen M., Qin X., Koo H.-M., Mishra M. System-Level Validation. Hight-Level Modeling and Direct Test Generation Techniques, Springer, 2013, 247 p.
20. Gavrilov S. Methods of logical correlation analysis for CAD digital CMOS VLSI, Moscow, Tekhnosfera, 2011, 136 p. (in Russian).
21. Biere A. [et al.] ed. Handbook of Satisfiability, IOS Press, 2009, 980 p.
22. Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions, In Sasao T., Fujita M. (eds.), Kluwer Academic Publishers, 1996, pp. 233—258.
23. Kubica M., Kania D. SMTBDD: New form of BDD for logic synthesis, International Journal of Electronics and Telecom­munications, 2016, vol. 62, no. 1, pp. 33—41.
24. Kubica M., Kania D. Decomposition of multi-output functions oriented to configurability of logic blocks, Bulletin of the Polish Academy of Sciences. Technical Sciences, 2017, vol. 65, no. 3, pp. 317—331.
25. Vemuri N., Kalla P., Tessier R. BDD-based logic synthesis for LUT-6-based FPGAs, ACM Transactions on Design Automation of Electronic Systems, 2002, vol. 7, no. 4, pp. 501—525.
26. Yang S., Ciesielski M. BDS: a BDD-based logic optimization system, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866—876.
27. Bibilo P. N., Romanov V. I. Experimental Study of Algorithms for Minimization of Binary Decision Diagrams using Algebraic Representations of Cofactors, Programmnaya Ingeneria, 2022, vol. 13, no. 2, pp. 51—67 (in Russian).
28. Bibilo P. N., Lankevich Yu. Yu. The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion, Programmnaya Ingeneria, 2017, vol. 8, no. 8, pp. 369—384. (in Russian).
29. Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems, Software & Systems, 2020, vol. 33, no. 3, pp. 197—206. (in Russian).
30. Bibilo P. N., Romanov V. I. The system of logical optimization of functional structural descriptions of digital circuits based on production-frame knowledge representation model, Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system, 2020, Sb. trudov pod obshch. red. akad. RAN A. L. Stempkovskogo, Moscow, IPPM RAN, 2020, no. 4, pp. 9—16 (in Russian).
31. Lohov A. VLSI design tools of Mentor Graphics, ELEKTRONIKA: Nauka, Tekhnologiya, Biznes, 2003, no. 7, pp. 30—32 (in Russian).
32. Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex
    

To the contents