Preview

Информатика

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

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

Аннотация

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

Об авторах

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

Бибило Петр Николаевич – доктор технических наук, профессор.

Ул. Сурганова, 6, 220012, Минск



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

Кириенко Наталья Алексеевна – кандидат технических наук, доцент.

Ул. Сурганова, 6, 220012, Минск


Ю. Ю. Ланкевич
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь

Ланкевич Юрий Юрьевич – младший научный  сотрудник.

Ул. Сурганова, 6, 220012, Минск



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

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.


Рецензия

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


Бибило П.Н., Кириенко Н.А., Ланкевич Ю.Ю. Логическая оптимизация многоуровневых представлений систем булевых функций на основе блочного разбиения и разложения Шеннона. Информатика. 2018;15(3):56-70.

For citation:


Bibilo P.N., Kirienko N.A., Lankevich Y.Y. Logical optimization the multilevel representations of systems of Boolean functions based on partitioning into blocksand Shannon decomposition. Informatics. 2018;15(3):56-70. (In Russ.)

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


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


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