Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Experimental Research of Effectiveness of Programs for Minimizing BDD Representations of Boolean Function Systems in Synthesis of Combinatorial CMOS Circuits
Authors
	Bibilo P.N.
	Lankevich Y.Y.
Date of publication
	2020
DOI
	10.31114/2078-7707-2020-1-33-39
Abstract
	the mathematical apparatus of BDD [1] 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 [2, 3]. The perspective of BDD is connected now with solving the SAT problem [4, 5], as well. However, the use of BDD in the digital circuits design is not limited to verification only. Design systems of digital VLSI use programs of BDD minimization at the stage of technologically independent optimization [6]. Many articles consider optimization of BDD representations of systems of completely defined Boolean functions, short reviews of these articles can be found in [2, 6, 7]. Main attention was paid to finding an arrangement of variables [11] for minimizing the BDD complexity. The variable ar-rangement 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 [8, 9] 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 [10] and logic optimization systems use several programs for minimization of BDD representa-tion of Boolean function systems that implement various algorithms. The purpose of this paper is to study the efficien-cy of these programs for synthesis of combinational circuits from library CMOS elements. After obtaining BDD mini-mized as for the number of graph nodes and defined as a set of interconnected formulas of Shannon expansion, the syn-thesis of a logic circuit is performed in the same design li-brary 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 per-forming 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 [13]. It is agreed with “the number of literals” criterion [12] in optimization of multi-level logic circuits. The results of experiments on standard examples are presented [14].
Keywords
	system of Boolean functions, Disjunctive Normal Form (DNF), Binary Decision Diagram (BDD), digital logic synthesis, VHDL, VLSI, CMOS.
Library reference
	Bibilo P.N., Lankevich Y.Y. Experimental Research of Effectiveness of Programs for Minimizing BDD Representations of Boolean Function Systems in Synthesis of Combinatorial CMOS Circuits // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2020. Issue 1. P. 33-39. doi:10.31114/2078-7707-2020-1-33-39
URL of paper
	http://www.mes-conference.ru/data/year2020/pdf/D004.pdf