Логическая минимизация булевых сетей с использованием разложения Шеннона

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

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

1. Advanced Techniques in Logic Synthesis, Optimizations and Applications / ed.: S. P. Khatri, K. Gulati. – Springer, 2010. – 423 p.

2. Advanced Logic Synthesis / ed.: A. I. Reis, R. Drechsler. – Springer, 2017. – 232 p.

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

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

5. Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM J. of Research & Development. – 1987. – Vol. 31, no. 2. – P. 187–198.

6. Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. – Минск : Наука и техника, 1975. – 184 с.

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

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

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

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

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

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

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

14. Amaru, L. G. New Data Structures and Algorithms for Logic Synthesis and Verification / L. G. Amaru. – Springer, 2017. – 156 p.

15. Прихожий, А. А. Частично определенные логические системы и алгоритмы / А. А. Прихожий. – Минск : БНТУ, 2013. – 343 с.

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

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

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

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

20. Поляков, А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры / А. К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.