DOI: 10.17587/prin.16.181-189

Additional Optimization for Algorithm a Block Cover of a System of Disjunctive Normal Forms of Boolean Functions

P. N. Bibilo, Head of Laboratory, bibilo@newman.bas-net.by, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Belarus

Corresponding author: Petr N. Bibilo, Head of Laboratory, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus,Minsk, 220012, Belarus, E-mail: bibilo@newman.bas-net.by

The block coverage of the DNF system (Disjunctive Normal Forms) of fully defined Boolean functions consists in grouping elementary conjunctions into subsystems (blocks) with limited values of the number of input variables, functions and conjunctions. For a more effective solution to the problem of logical synthesis, an algorithm is proposed to reduce the number of different DNFs in a pair of intersecting blocks. The algorithm is based on constructing an undirected graph and coloring it into a minimum number of colors. This makes it possible to reduce the complexity of multi-level representations of block functions, since for sparse DNF systems of Boolean functions, the blocks often contain the same DNF. For matrix forms of sparse DNF systems, the ternary matrix specifying elementary conjunctions contains a large proportion of undefined values corresponding to the missing literals of Boolean input variables in the algebraic notation, and the Boolean matrix specifying the occurrences of conjunctions in the DNF of Boolean functions contains a large proportion of zero values. Thus, technologically independent optimization of sparse DNF systems of Boolean functions is divided into two stages — block coverage and minimization of multilevel representations of block functions in the form of BDD or Boolean nets.

Keywords: Boolean function system, DNF, block cover of the DNF system, coloring an undirected graph, logic synthesis, ASIC

pp. 181—189

For citation:
Bibilo P. N. Additional Optimization for Algorithm a Block Cover of a System of Disjunctive Normal Forms of Boolean Functions, Programmnaya Ingeneria, 2025, vol. 16, no. 4, pp. 181—189. DOI: 10.17587/prin.16.181-189 (in Russian).

References:

1. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification, Springer, 2017, 156 p.
2. Zakrevskij A. D. Logical Synthesis of Cascading Circuit, Moscow, Nauka, 1981, 416 р. (in Russian).
3. Brayton K. R., Hachtel G. D., McMullen C., SangiovanniVincentelli A. L. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.
4. Synthesis of Asynchronous Automata on a Computer, Pod red. A. D. Zakrevskogo, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).
5. 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.
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. DOI: 10.1109/TCAD.1987.1270347.
7. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD — Foundations and Applications, Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.
8. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. N. Y, Springer, 1998, 210 p.
9. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization, Springer, 2005, 222 p.
10. 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. DOI: 10.1109/TCAD.2003.819427.
11. Haaswijk W., Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. A novel basis for logic rewriting, Proc. of 22nd Asia and South Pacific Design Automation Conference (ASP-DAC), 2017, pp. 151—156. DOI: 10.1109/ASPDAC.2017.7858312.
12. Soeken M., Amaru L. G., Gaillardon P., De Micheli G. Optimizing majority-inverter graphs with functional hashing, Proc. Design, Automation and Test in Europe, 2016, pp. 1030—1035. DOI: 10.3850/9783981537079_0281.
13. Soeken M., Amaru L., Gaillardon P.-E., De Micheli G. Exact synthesis of majority-inverter graphs and its applications, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, vol. 36, no. 11, pp. 1842—1855.
14. Riener H., Testa E., Amaru L., Soeken M., De Micheli G. Size optimization of MIGs with an application to QCA and STMG technologies, Proc. of International Symposium on Nanoscale Architectures, 2018, pp. 157—162. DOI: 10.1145/3232195.3232202.
15. Harlecek I., Fiser P., Schmidt J. Are XORs in logic synthesis really necessary? IEEE 20th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS), 2017, pp. 134—139. DOI: 10.1109/DDECS.2017.7934583.
16. Schneider A. A., Kardash S. N. Algorithms for the synthesis of single-level combinational circuits from PLAs, Avtomatika i vychislitel’naya tekhnika, 1987, no. 5, pp. 62—67 (in Russian).
17. Kardash S. N. Construction of block partitions of Boolean function systems based on the problem of covering Boolean matrices, IX Mezhdunar. nauch.-prakt. konf. “BIG DATA and Advanced Analytics” (BIG DATA 2023): Materialy mezhdunar. nauch. konf., Respublika Belarus’, Minsk, 17—18 May 2023, Minsk: BGUIR, 2023, part 2, pp. 326—330 (in Russian).
18. Tarasov I. E. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques, Moscow, Goryachaya liniya—Telekom, 2020, 538 р. (in Russian).
19. Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).
20. Zakrevsky A. D., Pottosin Yu. V., Cheremisinova L. D. Logical foundations of the design of discrete devices. Мoscow, Fizmatlit, 2007, 592 p. (in Russian).
21. Bibilo P. N. Binary decision diagrams in logical design. Мoscow: LENAND, 2024. 560 p. (in Russian).
22. Bibilo P. N., Lankevich Yu. Yu. The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion, Programmnaya ingeneriya, 2017, vol. 8, no. 8, рр. 369—384. DOI: 10.17587/prin.8.369-384 (in Russian).