informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-658Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNЛогическая минимизация булевых сетей с использованием разложения ШеннонаLogical optimization of Boolean nets using Shannon expansionБибилоП. Н.BibiloP. N.

Бибило Петр Николаевич, доктор технических наук, профессор

Petr N. Bibilo, Dr. Sci. (Eng.), Prof.

bibilo@newman.bas-net.byЛанкевичЮ. Ю.LankevichYu. Y.

Ланкевич Юрий Юрьевич, младший научный сотрудник

Yury Y. Lankevich, Junior Researcher

yurafreedom18@gmail.comОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2019080120191627389Copyright © Бибило П.Н., Ланкевич Ю.Ю., 20192019Бибило П.Н., Ланкевич Ю.Ю.Bibilo P.N., Lankevich Y.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/658

Синтез логических схем, реализующих комбинационные блоки сверхбольших интегральных схем, – одна из важнейших задач компьютерного проектирования, так как размерность задач проектирования увеличивается, возрастает также время выполнения этапов синтеза логических схем. Особенно трудоемкой является глобальная технологическая независимая оптимизация – первый этап синтеза логической схемы. Суть второго этапа заключается в технологическом отображении оптимизированных логических представлений функций на логические элементы технологической библиотеки. Основные характеристики логической схемы, такие как площадь, быстродействие, энергопотребление, зависят от эффективности первого этапа. Эволюция методов глобальной логической оптимизации показала эффективность разложения Шеннона при оптимизации многоуровневых представлений систем полностью определенных булевых функций. Разработано множество методов и программ, использующих графические представления разложений Шеннона – BDD-представления. Большинство разработанных методов оптимизации BDD-представлений используют задания исходных систем булевых функций в виде дизъюнктивных нормальных форм (ДНФ).

Предлагается алгоритм минимизации числа вершин булевой сети, являющейся многоуровневым представлением системы полностью определенных булевых функций. Минимизация осуществляется на основе разложения Шеннона и поиска вершин сети, реализующих одинаковые и взаимно инверсные функции. Предложенный алгоритм логической оптимизации реализован в виде программы. Эксперименты показали, что данный алгоритм и полученную программу целесообразно использовать в случае, когда исходное многоуровневое представление функций невозможно представить (за приемлемое время работы компьютерной программы) в виде системы ДНФ либо когда система ДНФ, полученная из многоуровневого представления, содержит большое число (десятки и сотни тысяч) элементарных конъюнкций.

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.

булева функциябулева сетьразложение Шеннонадизъюнктивная нормальная формасинтез логических схемBDDBoolean functionBoolean netShannon expansiondisjunctive normal formsynthesis of logical circuitsBDDИсследование выполнено при финансовой поддержке БРФФИ в рамках проекта № Ф19-023.The study was carried out with the financial support of the BRFFR in the framework of project No. F19-023.ReferencesAdvanced Techniques in Logic Synthesis, Optimizations and Applications / ed.: S. P. Khatri, K. Gulati. – Springer, 2010. – 423 p.Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2010, 423 p.Advanced Logic Synthesis / ed.: A. I. Reis, R. Drechsler. – Springer, 2017. – 232 p.Reis A. I., Drechsler R. (eds.). Advanced Logic Synthesis. Springer, 2017, 232 p.Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.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).Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston : Kluwer Academic Publishers, 1984. – 193 p.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.Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM J. of Research & Development. – 1987. – Vol. 31, no. 2. – P. 187–198.Brayton K. R. Factoring logic functions. IBM Journal of Research & Development, 1987, vol. 31, no. 2, pp. 187–198.Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. – Минск : Наука и техника, 1975. – 184 с.Zakrevskij A. D. Sintez asinhronnyh avtomatov na JeVM. Synthesis of Asynchronous Machines on a Computer. Minsk, Nauka i tekhnika, 1975, 184 p.MIS: A multiple-level logic optimization systems / K. R. Brayton [et al.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 1987. – Vol. 6, no. 6. – P. 1062–1081.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.Mailhot, F. Algorithms for technology mapping based on binary decision diagrams and on Boolean operations / F. Mailhot, G. Micheli // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 1993. – Vol. 12, no. 5. – P. 599–620.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.Bryant, R. E. Graph-based algorithms for Boolean function manipulation / R. E. Bryant // IEEE Transactions on Computers. – 1986. – Vol. 35, no. 8. – P. 677–691.Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, pp. 677–691.Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification / ed.: S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.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.Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 7. – P. 866–876.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.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.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).Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.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).Amaru, L. G. New Data Structures and Algorithms for Logic Synthesis and Verification / L. G. Amaru. – Springer, 2017. – 156 p.Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer, 2017, 156 p.Прихожий, А. А. Частично определенные логические системы и алгоритмы / А. А. Прихожий. – Минск : БНТУ, 2013. – 343 с.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.Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 3. – С. 369–384.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).Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.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).Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.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).Jeong, C. Computer-aided design of digital systems / C. Jeong [Electronic resource] // Department of Computer Scienc. – Mode of access: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex. – Date of access: 20.03.2018.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).Поляков, А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры / А. К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.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.

The authors declare that there are no conflicts of interest present.