informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2020-17-1-63-77inform-922Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNВыделение подсистем связанных функций из многоуровневого представления системы булевых функцийThe search for subsystems of related functions from multilevel representation of systems of Boolean functions1БибилоП. Н.BibiloP. N.

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

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

bibilo@newman.bas-net.byПознякА. М.PazniakA. M.

Позняк Андрей Михайлович, магистрант

Andrei M. Pazniak, Undergraduate

krucios@mail.ruОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2020080120201716377Copyright © Бибило П.Н., Позняк А.М., 20202020Бибило П.Н., Позняк А.М.Bibilo P.N., Pazniak A.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/922

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

One of the directions of logical optimization of multilevel representations of systems of Boolean     functions is the methods based on the search of subsystems of functions that have the same parts in the domains of functions of selected subsystems. Such subsystems are called related. The good relationship of functions leads to the appearance of a large number of identical structural parts (conjunctions, algebraic expressions,  subfunctions, etc.) in optimized forms of representation of functions which are used in the construction of   combinational logic circuits. The more the functions of the selected subsystem are related, the sooner it is expected that in the representations of the functions of this subsystem will be more identical subexpressions and synthesized logic circuits will have less complexity. 

We describe software-implemented algorithms for extracting subsystems of related functions from a BDD    representation of a system of Boolean functions based on introduced numerical estimates of the relationship of BDD representations of functions. The relationship of Boolean functions is the presence of Boolean vectors, where the functions take the value as one, or of the same equations in BDD representations. BDD representations of Boolean functions are compact forms defining functions and are constructed as the result of Shannon decomposition of the functions of the original system (resulting from the decomposition of subfunctions) by all variables, which the functions of the original system depend on. The experiments show the effectiveness of proposed algorithms and programs in the synthesis of logic circuits from  logic elements library.

булева функцияразложение ШеннонаBDD-представлениедизъюнктивная нормальная формасинтез логических схемBoolean functionShannon decompositionBDD representationdisjunctive normal formlogic synthesisReferencesБрейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Sintez mnogourovnevyh kombinacionnyh logicheskih skhem [Synthesis of multi-level combinational logic circuits]. Trudy Institute 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.Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 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).Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on the Solution of Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (in Russian).Кузнецов, О. П. О программной реализации логических функций и автоматов / О. П. Кузнецов // Автоматика и телемеханика. – 1977. – № 7. – С. 63–74.Kuznecov O. P. O programmnoj realizacii logicheskih funkcij i avtomatov [On the software implementation of logical functions and automata]. Avtomatika i telemekhanika [Automation and Telemechanics], 1977, no. 7, pp. 63–74 (in Russian).Akers, S. B. Binary decision diagrams / S. B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C-27, no. 6. – P. 509–516.Akers S. B. Binary decision diagrams. IEEE Transactions on Computers, 1978, vol. C-27, no. 6, pр. 509–516.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 S. Hassoun, T. Sasao, R. K. Brayton. 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 diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (in Russian).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 3. – С. 369–384.Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov Zhegalkina pri minimizacii mnogourovnevyh predstavlenij system bulevyh funkcij na osnove razlozheniya Shennona [The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion]. Programmnaya inzheneriya [Software Engineering], 2017, no. 3, рр. 369–384 (in Russian).Бибило, П. Н. Разбиение системы булевых функций на подсистемы «связанных» функций / П. Н. Бибило // Известия РАН. Теория и системы управления. – 2019. – № 2. – С. 14–29.Bibilo P. N. Razbienie sistemy bulevyh funkcij na podsistemy "svyazannyh" funkcij [Partitioning a system of Boolean functions into subsystems of "related" functions]. Izvestija Rossijskoj akademii nauk. Teoriya i sistem yupravleniya [Proceedings of the Russian Academy of Sciences. Theory and control systems], 2019, no. 2, pp. 14–29 (in Russian).Шлее, М. Qt 5.3. Профессиональное программирование на С++ / М. Шлее. – СПб. : БХВ-Петербург, 2015. – 928 с.SHlee M. Qt 5.3. Professional'noe programmirovanie na S++. Qt 5.3. Professional C ++ Programming. Saint Petersburg, BHV-Peterburg, 2015, 928 р. (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 Using a ProductionFrame Knowledge Representation Model. Minsk, Belaruskaja navuka, 2011, 279 p. (in Russian).Система логического проектирования функциональных блоков заказных КМОП СБИС с пониженным энергопотреблением / П. Н. Бибило [и др.] // Микроэлектроника. – 2017. – Т. 46, № 1. – С. 72–88.Bibilo P. N., Avdeev N. A., Kardash S. N., Kirienko N. A., Lankevich Yu. Yu., …, Cheremisinova L. D. Sistema logicheskogo proektirovaniya funkcional'nyh blokov zakaznyh KMOP SBIS s ponizhennym energopotrebleniem [System for the logical design of functional blocks of custom CMOS VLSI with low power consumption]. Mikroelektronika [Microelectronics], 2017, vol. 46, no. 1, рр. 72–88 (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).Авдеев, Н. А. Эффективность логической оптимизации при синтезе комбинационных схем из библиотечных элементов / Н. А. Авдеев, П. Н. Бибило // Микроэлектроника. – 2015. – Т. 44, № 5. –С. 383–399.Avdeev N. A., Bibilo P. N. Effektivnost' logicheskoj optimizacii pri sinteze kombinacionnyh skhem iz bibliotechnyh elementov [The effectiveness of logical optimization in the synthesis of combinational circuits from library elements]. Mikroelektronika [Microelectronics], 2015, vol. 44, no. 5, рр. 383–399 (in Russian).Jeong, C. Computer-aided design of digital systems / C. Jeong // Department of Computer Science [Electronic resource]. – 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).

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