Logical optimization of Boolean nets using Shannon expansion

A synthesis of logical circuits, comprising functional combination blocks of very large scale integration circuits, is one of the most important tasks of computer-aided design. As the data size of design tasks increases, the execution time of synthesis of logic circuits also increases. The global technological independent optimization as the first stage of synthesis of logical circuit is especially labor-consuming. The second stage is technological mapping of optimized logical representations of functions to the logical elements of technological library. The main features of logical circuit, such as area, performance, power consumption, depend on the efficiency of the first stage – global logical optimization. The evolution of methods of global logical optimization has revealed the efficiency of Shannon expansion in case of optimization of multi-level representations of the systems of fully defined Boolean function. A number of methods and programs were developed using graphical representations of Shannon expansions – BDD representations. Most of the developed methods of optimization of BDD-representations use the initial representations of functions systems in the form of disjunctive normal form (DNF).

In the article an algorithm of minimization of nodes number of Boolean net, which is a multi-level representation of the system of fully defined Boolean function, is proposed. Minimization is based on Shannon expansion and a search of equal (with accuracy up to inversion) nodes in Boolean net. Such algorithm of logical optimization was implemented as application. The experiments have shown that this algorithm and the application is reasonable to use in cases when the initial multi-level representation of functions is impossible to define as DNF system, or when DNF system contains a large number of elementary conjunctions.

1. Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2010, 423 p.

2. Reis A. I., Drechsler R. (eds.). Advanced Logic Synthesis. Springer, 2017, 232 p.

3. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Sintez mnogourovnevyh kombinacionnyh logicheskih skhem [Multilevel logic synthesis]. Trudy Instituta inzhenerov po jelektronike i radiotehnike [Proceedings of the Institute of Electronics and Radio Engineering], 1990, vol. 78, no. 2, рр. 38–83 (in Russian).

4. Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. L. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.

5. Brayton K. R. Factoring logic functions. IBM Journal of Research & Development, 1987, vol. 31, no. 2, pp. 187–198.

6. Zakrevskij A. D. Sintez asinhronnyh avtomatov na JeVM. Synthesis of Asynchronous Machines on a Computer. Minsk, Nauka i tekhnika, 1975, 184 p.

7. Brayton K. R., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: A multiple-level logic optimization systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. 6, no. 6, pp. 1062–1081.

8. Mailhot F., Micheli G. Algorithms for technology mapping based on binary decision diagrams and on Boolean operations. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993, vol. 12, no. 5, pp. 599–620.

9. Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, pp. 677–691.

10. Bryant R. E., Meinel C. Ordered binary decision diagrams. Logic Synthesis and Verification. In Hassoun S., Sasao T., Brayton R. K. (eds.). Kluwer Academic Publishers, 2002, pp. 285–307.

11. 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.

12. Bibilo P. N. Primenenie diagramm dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Decision Diagrams at Synthesis of Logical Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (in Russian).

13. Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum. Moscow, SOLON-Press, 2005, 384 p. (in Russian).

14. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p.

15. Prihozhij A. A. Chastichno opredelennye logicheskie sistemy i algoritmy. Partially Defined the Logical Systems and Algorithms. Minsk, Belorusskij nacional'nyj tehnicheskij universitet, 2013, 343 p.

16. Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov Zhegalkina pri minimizacii mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove razlozheniya Shennona [The use of Zhegalkin polynomials with minimization of multilevel representations of systems of Boolean functions on the basis of the Shannon decomposition]. Programmnaya inzheneriya [Software Engineering], 2017, no. 3, рр. 369–384 (in Russian).

17. Zakrevskij A. D., Pottosin Ju. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Bases of Design of Discrete Devices. Moscow, Fizmatlit, 2007, 592 р. (in Russian).

18. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionno-frejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices with Use of Productional and Frame Model of Representation of Knowledge. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).

19. Jeong C. Computer-aided design of digital systems. Department of Computer Science. Available at : http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed 20.03.2018).

20. Poljakov A. K. Jazyki VHDL i VERILOG v proektirovanii cifrovoj apparatury. VHDL and VERILOG in the design of digital equipment. Moscow, SOLON-Press, 2003, 320 p.