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

Бибило П. Н.; Позняк А. М.

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

Бибило П. Н., Позняк А. М.

2020

https://doi.org/10.37661/1816-0301-2020-17-1-63-77

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

Бибило П. Н., Позняк А. М. Выделение подсистем связанных функций из многоуровневого представления системы булевых функций. Информатика. 2020;17(1):63-77. https://doi.org/10.37661/1816-0301-2020-17-1-63-77

Цитирование

Список литературы

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.

Источник

Информация

Автор

Бибило П. Н. Объединенный институт проблем информатики Национальной академии наук Беларуси
Позняк А. М. Объединенный институт проблем информатики Национальной академии наук Беларуси

Страницы

63-77

Год издания

2020

Ключевые слова

Коллекции

Информатика