Disjunctive and conjunctive decompositions of incompletely defined Boolean functions in a Binary Decision Diagram

Objectives. The problems of minimizing the number of cofactors (subfunctions) of the Shannon expansions located at the same level of the BDD, representing a system of incompletely defined (partial) Boolean functions, are considered. To reduce the number of functions, it is proposed to find a subset of such functions that can be expressed as algebraic decompositions of disjunctions or conjunctions of other predefined partial functions, while the directed graph of function occurrences in decompositions should not contain contours.

Methods. Finding disjunctive and conjunctive decompositions requires searching for appropriate additional definitions of partial functions. Finding the largest number of separate algebraic decompositions reduces to the problem of finding a weighted row cover of a Boolean matrix of occurrences of system functions in separate decompositions. The task of finding consistent predefinitions of partial functions for various types of joint decompositions is reduced to the formulation and solution of logical equations.

Results. It is shown that the constructed logical equations can be easily transformed to a conjunctive normal form (CNF), and finding the roots of such equations is reduced to the problem of satisfiability of a Boolean formula presented in the form of CNF, for which effective methods and programs are known.

Conclusion. The proposed algorithms can be generalized to other types of algebraic decompositions, when, in addition to the logical operations of disjunction and conjunction, negations of these operations can be used. The application of the proposed algorithms and already known algorithms for minimizing multilevel BDD representations of partial function systems allows us to obtain the best results of technologically independent logical optimization, the initial stage of logic circuit synthesis.

1. Bibilo P. N. Binarnye diagrammy reshenij v logicheskom proektirovanii. Binary Decision Diagrams in Logical Design. Moscow, Lenand, 2024, 560 p. (In Russ.).

2. Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866–876.

3. Bibilo P. N., Romanov V. I. Experimental study of algorithms for minimization of binary decision diagrams using algebraic representations of cofactors. Programmnaya ingeneria [Software Engineering], 2022, vol. 13, no. 2, pp. 51–67 (In Russ.).

4. Handbook of Satisfiability. In A. Biere, M. Heule, H. van Maaren, T. Valsh (eds.). IOS Press, 2009, 980 p.

5. Goldberg E., Novikov Y. BerkMin: a fast and robust SAT-solver. Discrete Applied Mathematics, 2007, vol. 155, no. 12, pp. 1549–1561.

6. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).

7. Eremeev A. V., Zaozerskaya L. A., Kolokolov A. A. The problem of covering the set: complexity, algorithms, experimental studies. Diskretnyj analiz i issledovanie operacij [Discrete Analysis and Operations Research], 2000, vol. 7, no. 2, pp. 22–46 (In Russ.).

8. Zakrevskij A. D. Logicheskie uravneniya. Logical Equations. Minsk, Nauka i tekhnika, 1975, 96 p. (In Russ.).

9. Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on Solving Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (in Russ.).

10. Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I. Lekcii po teorii grafov. Lectures on Graph Theory. Moscow, Nauka, 1990, 384 p. (In Russ.).

11. Bibilo P. N. Minimization of binary decision diagrams for systems of incompletely defined Boolean functions using inverse cofactors. Programmnaya ingeneria [Software Engineering], 2020, vol. 11, no. 3, pp. 152–168 (In Russ.).

12. 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. Informatika [Informatics], 2021, vol. 18, no. 2, pp. 7−32 (In Russ.).

13. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multilevel combinational logic circuits. Trudy Instituta inzhenerov po jelektrotehnike i radiojelektronike [Proceedings of the IEEE], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).