Software & Systems

Articles of journal № 3 at 2020 year.

Order result by: Public date | Title | Authors

21. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function syst [№3 за 2020 год]
Authors: Bibilo, P.N., Yu.Yu. Lankevich
Visitors: 5690
The mathematical apparatus of BDD is used in various fields of science. In the computer-aided design field, BDD allowed to obtain significant success in a formal verification of algorithmic descriptions of digital circuits. Design systems of digital VLSI use programs of BDD minimization at the stage of tech-nologically independent optimization. Many articles consider optimization of BDD representations of systems of completely defined Boolean functions. Main attention was paid to finding an arrangement of variables for minimizing the BDD complexity. The variable arrangement is used to decompose the initial functions of the system and sub-functions (cofactors), which are obtained in the process of de-composition. The complexity of a BDD is the number of nodes in it. Each node of the BDD corresponds to a complete or reduced form of Shannon expansion. Domestic CAD and logic optimization systems use several programs for minimization of BDD rep-resentation of Boolean function systems that implement various algorithms. The purpose of this paper is to study the efficiency of these programs for synthesis of combinational circuits from library CMOS elements. After obtaining BDD minimized as for the number of graph nodes and defined as a set of in-terconnected formulas of Shannon expansion, the synthesis of a logic circuit is performed in the same design library of digital CMOS VLSI; the results are compared by square and delay. In many cases, it is possible to achieve additional reduction of logic description complexity by performing additional logic minimization based on Boolean nets. In this case, the optimization criterion is the number of nodes in the Boolean net, without considering inversion of Boolean variables. It is agreed with “the number of literals” criterion in optimization of multi-level logic circuits. The results of experiments on standard examples are presented.

◄ ← Preview | 1 | 2 | 3