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

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

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

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

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

4. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. - М. : Наука, 1981. - 416 c.

5. Sasao, T. FPGA design by generalized functional decomposition / T. Sasao // Representations of Discrete Functions ; ed. by T. Sasao, M. Fujita. - Kluwer Academic Publishers, 1996. - P. 233-258.

6. Scholl, C. Functional Decomposition with Applications to FPGA Synthesis / C. Scholl. - Kluwer Academic Publishers, 2001. - 288 p.

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

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

9. Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification ; ed. by S. Hassoun, T. Sasao, R. K. Brayton. - Kluwer Academic Publishers, 2002. - P. 285-307.

10. Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications / C. Meinel, T. Theobald. - Berlin, Heidelberg : Springer-Verlag, 1998. - 267 p.

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

12. Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. - М. : Техносфера, 2014. - 296 с.

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

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

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

16. Григорьян, С. Г. Конструирование электронных устройств систем автоматизации и вычислительной техники / С. Г. Григорьян. - Ростов н/Д : Феникс, 2007. - 303 с.

17. Кузовлев, В. И. Выявление высокоуровневых иерархических структур сверхбольших интегральных схем через сильно связанные логические группы / В. И. Кузовлев, Н. А. Иванова // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. - 2016. - № 4. - С. 4-18.

18. Netlist and system partitioning / A. B. Kahng [et al.] // VLSI Physical Design: From Graph Partitioning to Timing Closure. - Springer, 2011. - Chap. 2. - P. 31-54.

19. Бибило, П. Н. Оптимизационные преобразования логической схемы на основе блочного разбиения / П. Н. Бибило, Н. А. Кириенко // Информатика. - 2009. - № 3(23). - С. 5-15.

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