ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 8. Vol. 27. 2021

DOI: 10.17587/it.27.395-408

P. N. Bibilo, Dr. Sci. (Eng.), Professor, e-mail: bibilo@newman.bas-net.by, V. I. Romanov, Ph. D. (Eng.), e-mail: rom@newman.bas-net.by, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Republic of Belarus

Minimization of Binary Decision Diagrams for Systems of Completely Defined Boolean Functions using Algebraic Representations of Cofactors

In design systems for digital VLSI (very large integrated circuits), the BDD is used for VLSI verification, as well as for technologically independent optimization, performed as the first stage in the synthesis of logic circuits in various technological bases. 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. Having constructed BDD representation for systems of Boolean functions, 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 or conjunction of other cofactors of this BDD level. 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 library logic gates.
Keywords: system of Boolean functions, Disjunctive Normal Form (DNF), Binary Decision Diagram (BDD), Shannon expansion, digital logic synthesis, VHDL, VLSI

P. 395–408

To the contents