Preview

Информатика

Расширенный поиск

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

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

Аннотация

Одним из направлений логической оптимизации многоуровневых представлений систем булевых функций являются методы, основанные на выделении подсистем функций, которые имеют одинаковые части в областях определения функций выделенных подсистем. Такие подсистемы называются связанными. Связанность функций приводит к появлению большого числа одинаковых структурных частей (конъюнкций, алгебраических выражений, подфункций и др.) в оптимизированных формах представления функций, по которым строятся в дальнейшем комбинационные логические схемы. Чем сильнее связаны функции выделенной подсистемы, тем скорее можно ожидать, что в представлениях функций данной подсистемы будет больше одинаковых подвыражений и синтезированные логические схемы будут иметь меньшую сложность.  Описываются программно реализованные алгоритмы выделения подсистем связанных функций из 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.


Рецензия

Для цитирования:


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

For citation:


Bibilo P.N., Pazniak A.M. The search for subsystems of related functions from multilevel representation of systems of Boolean functions1. Informatics. 2020;17(1):63-77. (In Russ.) https://doi.org/10.37661/1816-0301-2020-17-1-63-77

Просмотров: 570


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)