Minimization of binary decision diagrams for systems of completely defined Boolean functions using Shannon expansions and algebraic representations of cofactors
https://doi.org/10.37661/1816-0301-2021-18-2-7-32
Abstract
In the systems of digital VLSI design (Very Large Integrated Circuits), the BDD (Binary Decision Diagram) is used for VLSI verification, as well as for technologically independent optimization as the first stage in the synthesis of logic circuits in various technological bases. The BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph corresponds to the complete or reduced Shannon expansion formula. When BDD representation for systems of Boolean functions is constructed, it is possible to perform additional logical optimization based on the proposed method of searching for algebraic representations of cofactors (subfunctions) of the same BDD level in the form of a disjunction, conjunction either exclusive-or of cofactors of the same level or lower levels of BDD. A directed BDD graph for a system of functions is constructed on the basis of Shannon expansion of all component functions of the system by the same permutation of variables. The method allows to reduce the number of literals by replacing the Shannon expansion formulas with simpler formulas that are disjunctions or conjunctions of cofactors, and to reduce the number of literals in specifying a system of Boolean functions. The number of literals in algebraic multilevel representations of systems of fully defined Boolean functions is the main optimization criterion in the synthesis of combinational circuits from librarian logic elements.
About the Authors
P. N. Bibilo
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Petr N. Bibilo - Dr. Sci. (Eng.), Professor, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.
st. Surganova, 6, Minsk, 220012.
V. I. Romanov
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Vladimir I. Romanov - Cand. Sci. (Eng.), The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.
st. Surganova, 6, Minsk, 220012.
References
1. 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.
2. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).
3. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. 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 Russ.).
4. Tarasov I. E. PLIS Xilinx. Yazyki opisaniya apparatury VHDL i Verilog, SAPR, priemy proektirovaniya. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques. Moscow, Goryachaya liniya - Telekom, 2020, 538 р.
5. Sintez asinhronnyh avtomatov na EHVM. Synthesis of Asynchronous Automata on a Computer. In Zakrevskogo A. D. (ed.). Minsk, Nauka i tekhnika, 1975, 184 р.
6. Brayton K. R. Factoring logic functions. IBM Journal of Research and Development, 1987, vol. 31, no. 2, рр. 187-198.
7. Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: a multiple-level logic optimization systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. 6, iss. 6, рр. 1062-1081.
8. Devadas S., Wang A. R., Newton A. R., Sangiovanni-Vincentelli A. Boolean decomposition in multilevel logic optimization. IEEE Journal of Solid-State Circuits, 1989, vol. 24, no. 2, рр. 399-407.
9. Brayton R., Mishchenko A., Chatterjee S. Boolean factoring and decomposition of logic networks. In Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2011, рр. 47-66.
10. Curtis H. A. A New Approach to the Design of Switching Circuit. Princeton, Van Nostrand, 1962, 635 p.
11. Scholl C. Functional Decomposition with Applications to FPGA Synthesis. Kluwer Academic Publishers, 2001, 288 p.
12. Pottosin Yu. V., Shestakov E. A. Tablichnye metody dekompozicii sistem polnost'yu opredelennyh bulevyh funkcij. Tabular methods for decomposition of systems of completely defined Boolean functions. Minsk, Belaruskaja navuka, 2006, 327 р. (In Russ.).
13. 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 Russ.).
14. Lin H.-P., Jiang J.-H. R., Lee R.-R. Ashenhurst decomposition using SAT and interpolation. In Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2011, рр. 67-86.
15. Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, рр. 677-691.
16. Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998, 210 p.
17. Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.
18. Bryant R. E., Meinel C. Ordered binary decision diagrams. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, рр. 285-307.
19. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.
20. Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2011, 912 р.
21. 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 Russ.).
22. Utkin A. A. Analiz logicheskih setej i tekhnika bulevyh vychislenij. The analysis of logical networks and the technique of Boolean calculations. Minsk, Nauka i tekhnika, 1979, 152 р. (In Russ.).
23. Romanov V. I. Software tools for the solution of the logical-combinatorial task. Informatika [Informatics], 2005, no. 4(8), рр. 114-123 (In Russ.).
24. 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 inzheneriya [Software Engineering], 2017, no. 8, рр. 369-384 (In Russ.).
25. Goldberg E., Novikov Y. BerkMin: a fast and robust SAT-solver. Discrete Applied Mathematics, 2007, vol. 155, no. 12, pp. 1549-1561.
26. Handbook of Satisfiability. In Biere A., Heule M., Van Maaren H., Valsh T. (eds.). IOS Press, 2009, 980 p.
27. Romanovskij I. V. Diskretnyj analiz. Discrete Analysis. Saint Petersburg, Nevskij Dialekt, BHV-Peterburg, 2008, 336 р. (In Russ.).
28. Bibilo P. N., Enin S. V. Sintez kombinacionnyh skhem metodami funkcional'noj dekompozicii. Synthesis of Combination Circuits by Methods of Functional Decomposition. Minsk, Nauka i tekhnika, 1987, 189 р. (In Russ.).
29. Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4-19 (In Russ.).
30. Bibilo P. N., Lankevich Yu. Yu. Minimizing multilevel representations of systems of Boolean functions based on Shannon expansion. Informatika [Informatics], 2017, no. 2(54), рр. 45-57 (In Russ.).
31. Bibilo P. N., Lankevich Yu. Yu. Logical optimization of Boolean nets using Shannon eXpansion. Informatika [Informatics], 2019, vol. 16, no. 2, рр. 73-89 (In Russ.).
32. Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff. Burlington, MA, USA, Morgan Kaufman Publishers, 2008, 909 p.
33. 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 р. (In Russ.).
Review
For citations:
Bibilo P.N., Romanov V.I. Minimization of binary decision diagrams for systems of completely defined Boolean functions using Shannon expansions and algebraic representations of cofactors. Informatics. 2021;18(2):7-32. (In Russ.) https://doi.org/10.37661/1816-0301-2021-18-2-7-32
Views: 506
Email this article 