Выделение подсистем связанных функций из многоуровневого представления системы булевых функций

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

булева функция, разложение Шеннона, BDD-представление, дизъюнктивная нормальная форма, синтез логических схем

1. Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.

2. Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston : Kluwer Academic Publishers, 1984. – 193 p.

3. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.

4. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.

5. Кузнецов, О. П. О программной реализации логических функций и автоматов / О. П. Кузнецов // Автоматика и телемеханика. – 1977. – № 7. – С. 63–74.

6. Akers, S. B. Binary decision diagrams / S. B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C-27, no. 6. – P. 509–516.

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

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

9. Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.

10. Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 3. – С. 369–384.

11. Бибило, П. Н. Разбиение системы булевых функций на подсистемы «связанных» функций / П. Н. Бибило // Известия РАН. Теория и системы управления. – 2019. – № 2. – С. 14–29.

12. Шлее, М. Qt 5.3. Профессиональное программирование на С++ / М. Шлее. – СПб. : БХВ-Петербург, 2015. – 928 с.

13. Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.

14. Система логического проектирования функциональных блоков заказных КМОП СБИС с пониженным энергопотреблением / П. Н. Бибило [и др.] // Микроэлектроника. – 2017. – Т. 46, № 1. – С. 72–88.

15. Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.

16. Авдеев, Н. А. Эффективность логической оптимизации при синтезе комбинационных схем из библиотечных элементов / Н. А. Авдеев, П. Н. Бибило // Микроэлектроника. – 2015. – Т. 44, № 5. –С. 383–399.

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