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

DOI: 10.17587/it.29.574-582

P. N. Bibilo, Dr. Sci. (Eng.), Professor,
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Republic of Belarus

Joint and Separate Minimization of Multilevel Representations of Boolean Function Systems

The results of experimental studies of the effectiveness of programs for minimizing multilevel representations of systems of Boolean functions performed during the synthesis of combinational circuits in the design library of custom CMOS VLSI are presented. The efficiency of joint and separate minimization programs using Shannon expansions for constructing multilevel representations of systems of fully defined Boolean functions in the form of interconnected systems of logical equations — complete or abbreviated formulas of Shannon expansion or formulas corresponding to Boolean networks is investigated. A comparison is made with the results of experiments performed for various types of joint minimization only. A comparison is also made with the results of solutions obtained by the program of joint and separate minimization of Boolean function systems in the DNF class. It is shown that the use of joint minimization of multi-level representations makes it possible to obtain circuits of a smaller area more often, and the use of a separate one — circuits with a lower delay.
Êeywords: system of Boolean functions, Disjunctive Normal Form (DNF), Binary Decision Diagram (BDD), Boolean net, Shannon expansion, digital logic synthesis, VHDL, VLSI

P. 574-582

References

1. Bibilo P. N., Lankevich Yu. Yu., Romanov V. I. Logical minimization of multilevel representations of Boolean function systems, Informacionnye tekhnologii, 2023, Vol. 29, no. 2, pp. 59—71 (in Russian).
2. Bibilo P. N. Binary decision diagrams in logical design, Moscow, LENAND, 2023, 560 p. (in Russian).
3. Zakrevskiy A. D. ed. Synthesis of asynchronous automata on a computer, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).
4. Brayton R. K., McMullen C. T. The Decomposition and Factorization of Boolean Expressions, Proc. of 1982 ISCAS Symp. Rome, May 10—12, 1982, pp. 49—54.
5. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Multilevel Logic Synthesis, Trudy Institute inzhenerov po jelektronike i radiotehnike, 1990, vol. 78, no. 2, ðð . 38—83 (in Russian).
6. 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.
7. Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions, In Sasao T., Fu-jita M. (eds.), Kluwer Academic Publishers, 1996, pp. 233—258.
8. Scholl C. Functional Decomposition with Applications to FPGA Synthesis, Boston: Kluwer Academic Publishers, 2001, 288 p.
9. Kubica M., Kania D. SMTBDD: New form of BDD for logic synthesis, Intern. J. of Electronics and Telecommunications, 2016, vol. 62, no. 1, pp. 33—41.
10. 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.
11. Bryant R. E. Graph-based algorithms for boolean func­tions manipulation, IEEE Trans. on Computers, 1986, vol. C-35, no. 8, pp. 677—691.
12. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD — Foundations and Applications, Berlin, Heidelberg, Springer-Verlag, 1998 , 267 p.
13. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation, N. Y, Springer, 1998, 210 p.
14. Ebendt R. Fey G., Drechsler R. Advanced BDD Optimization, Springer, 2005, 222 p.
15. Dutta A., Baishnab K. L., Chaudhary S. A New Evolutionary 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. 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).
19. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verication, Springer, 2017, 156 p.
20. Bibilo P. N., Lankevich Yu. Yu. Logical optimization of Boolean nets using Shannon expansion, Informatika, 2019, vol. 16, no. 2, pp. 73—89 (in Russian).
21. Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, no. 4, ðð. 4—19 (in Russian).
22. Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).
23. Neto W. L., Austin M., Temple S., Amaru L., Tang X., Gaillardon P.-E. LSOracle: a Logic Synthesis Framework Driven by Artificial Intelligence, IEEE/ACM International Conference on Computer-Aided Design (ICCAD) 04-07 November 2019. DOI: 10.1109/ICCAD45719.2019.8942145

To the contents