DOI: 10.17587/prin.11.152-168

Minimization of Binary Decision Diagrams for Systems of Incompletely Defined Boolean Functions Using Inverse Cofactors

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

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

Completely defined Boolean functions are mathematical models of combinational logic circuits. In design practice, models of incompletely defined (partial) Boolean functions are also used. Uncertain values of such functions in the design process are determined in order to obtain the best characteristics of logic circuits. The main characteristics of logic circuits are chip size, delays and power consumption. Currently, the circuit implementation of systems of partial functions uses two approaches. The first approach assumes minimization of the initial representation of systems of partial functions in the class of disjunctive normal forms (DNF). The second approach is related to obtaining minimized multilevel representations of a system of functions. Finding multilevel representations corresponds to solving various problems of decomposition of systems of partial functions. Among the many types of functional decomposition and the corresponding forms of representations of function systems, the multilevel representations of function systems based on the Shannon expansion were the most effective, which are also known as BDD representations in the literature. In this article, algorithms for the logical minimization of BDD representations (BDD — Binary Decision Diagram) of systems of partial Boolean functions are proposed. The result of the minimization is the multilevel BDD representations of systems of completely defined functions in the form of Shannon expansion formulas using both identical and mutually inverse cofactors. The minimization of the number of mutually inverse partial cofactors at the same level of the BDD representation of the system of partial functions is reduced to solving the combinatorial problem of finding the shortest implicating form of the ternary matrix that defines the values of the cofactors of this level of the BDD representation..

Keywords: Boolean function, disjunctive normal form, Shannon expansion, binary decision diagram (BDD), graph coloring, synthesis of logical circuit

pp. 152–168

For citation:
Bibilo P. N. Minimization of Binary Decision Diagrams for Systems of Incompletely Defined Boolean Functions Using Inverse Cofactors, Programmnaya Ingeneria, 2020, vol. 11, no. 3, pp. 152—168