Logical optimization the multilevel representations of systems of Boolean functions based on partitioning into blocksand Shannon decomposition
Abstract
The results of experimental study of the effectiveness of optimization procedures for systems of Boolean functions which are used in the synthesis of combinational circuits are described. The procedures use algorithms for partitioning systems of functions into subsystems and algorithms for optimizing multilevel representations of functions based on Shannon decomposition. The Shannon decomposition uses the procedure for finding inverse subfunctions, contained in decomposition result (BDDI-optimization). It is shown that these procedures can reduce the area of combinational circuits from library gates in many cases in the process of synthesis. Joint BDDI optimization is more preferable method in comparison to separate technologically independent BDDI optimization, since the area of circuits built on joint BDDI is smaller than the area of circuits built on separate BDDI in most cases.
About the Authors
P. N. Bibilo
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
PetrN. Bibilo – D. Sc. (Engineering), Professor.
6, Surganovа Str., 220012, MinskN. A. Kirienko
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Natalia A. Kirienko – Ph. D. (Engineering).
6, Surganovа Str., 220012, Minsk
Y. Y. Lankevich
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Yury Y. Lankevich – Researcher.
6, Surganovа Str., 220012, Minsk
References
1. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Sintez mnogourovnevyh kombinacionnyh logicheskih skhem [Multilevel Logic Synthesis]. TIIJeR [TIIER], 1990, vol. 78, no. 2, рр. 38–83 (in Russian).
2. Polyakov A. K. Yazyki VHDL i VERILOG v proektirovanii tsifrovoi apparatury. The VHDL and VERILOG Languages in Designing of Digital Hardware. Moscow, SOLON-Press Publ., 2003, 320 p. (in Russian).
3. Zakrevskij A. D., Pottosin Ju. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Bases of Design of Discrete Devices. Moscow, Fizmatlit Publ., 2007, 592 р. (in Russian).
4. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascade Circuits. Moscow, Nauka Publ., 1981, 416 p. (in Russian).
5. Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions. Kluwer Academic Publishers, 1996, рр. 233–258.
6. Scholl C. Functional Decomposition with Applications to FPGA Synthesis. Kluwer Academic Publishers, 2001, 288 p.
7. Bibilo P. N. Primenenie diagramm dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Decision Diagrams at Synthesis of Logical Circuits. Minsk, Belarus. Navuka Publ., 2014, 231 p. (in Russian).
8. Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, рр. 677–691.
9. Bryant R. E., Meinel C. Ordered binary decision diagrams. Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, рр. 285–307.
10. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Berlin, Heidelberg, Springer-Verlag Publ., 1998, 267 p.
11. Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer Publ., 2017, 156 p.
12. Chen M., Qin K., Ku H.-M., Mishra P. Validaciya na sistemnom urovne. Vysokourovnevoe modelirovanie i upravlenie testirovaniem. Validation at the System Level. High-Level Simulation and Testing Management. Moscow, Tekhnosfera Publ., 2014, 296 p. (in Russian).
13. 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).
14. 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 Publ., 2005, 384 p. (in Russian).
15. Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionnofrejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices with Use of Productional and Frame Model of Representation of Knowledge. Minsk, Belarus. Navuka Publ., 2011, 279 p. (in Russian).
16. Grigor'yan S. G. Konstruirovanie jelektronnyh ustrojstv sistem avtomatizacii i vychislitel'noj tekhniki. Design of Electronic Devices of Automation Systems and Computers. Rostov n/D, Feniks Publ., 2007, 303 p. (in Russian).
17. Kuzovlev V. I., Ivanova N. A. Vyyavlenie vysokourovnevyh ierarhicheskih struktur sverhbol'shih integral'nyh skhem cherez sil'no svyazannye logicheskie gruppy [Circuit detection through tangled logic structures]. Vestnik MGTU im. N. E. Baumana, ser. Priborostroenie [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2016, no. 4, рр. 4–18 (in Russian).
18. Kahng A. B., Liening J., Markov I. L., Hu J. Netlist and system partitioning. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, 2011, ch. 2, рр. 31–54.
19. Bibilo P. N., Kirienko N. A. Optimizacionnye preobrazovaniya logicheskoj skhemy na osnove blochnogo razbieniya [Optimizing conversions of a logic circuit by partitioning into blocks]. Informatika [Informatics], 2009, no. 3, рр. 5–15 (in Russian).
20. 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).
Review
For citations:
Bibilo P.N., Kirienko N.A., Lankevich Y.Y. Logical optimization the multilevel representations of systems of Boolean functions based on partitioning into blocksand Shannon decomposition. Informatics. 2018;15(3):56-70. (In Russ.)
Views: 653
Email this article 