Experimental Research of Effectiveness of Programs for Minimizing BDD Representations of Boolean Function Systems in Synthesis of Combinatorial CMOS Circuits
The mathematical apparatus of BDD is used in various fields of science. Design systems of digital VLSI use programs of BDD minimization at the stage of technologically independent optimization. Many articles consider optimization of BDD representations of systems of completely defined Boolean functions, short reviews of these articles can be found in. 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 decomposition. 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. Also there are known approaches that are oriented to a final stage of synthesis - technology mapping based on covering BDD with logical element descriptions. It results in obtaining the structure description that is a netlist of a logical circuit in a given technological basis that is also called logical synthesis library. Domestic CAD and logic optimization systems use several programs for minimization of BDD representation 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 interconnected 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.