Для матричных форм разреженных систем дизъюнктивных нормальных форм (ДНФ) булевых функций троичная матрица, задающая элементарные конъюнкции, содержит большую долю неопределенных значений, соответствующих в алгебраической записи отсутствующим литералам булевых переменных, а булева матрица, задающая вхождения конъюнкций в ДНФ функций, содержит большую долю нулевых значений. В работе рассмотрена проблема выбора лучших способов схемной реализации в заказных цифровых СБИС разреженных систем ДНФ полностью определенных булевых функций. Установлено, что для таких систем ДНФ достаточно эффективным способом технологически независимой оптимизации является двухэтапный способ, включающий в себя на первом этапе блочное покрытие системы ДНФ блоками (подсистемами ДНФ) меньшей размерности, на втором этапе – минимизацию многоуровневых представлений подсистем функций блоков в классе бинарных диаграмм решений либо в классе булевых сетей. Показано, что выбор лучшего блочного покрытия основан на переборе покрытий с ограниченным числом входных переменных блоков покрытия.
-
Ключевые слова:
система булевых функций, дизъюнктивная нормальная форма (ДНФ), минимизация ДНФ, Binary Decision Diagram (BDD), булева сеть, разложение Шеннона, блочное покрытие системы ДНФ, синтез логической схемы, заказная СБИС, VHDL
-
Опубликовано в разделе:
Схемотехника и проектирование
-
Библиографическая ссылка:
Бибило П. Н., Кардаш С. Н., Романов В. И. Выбор блочных покрытий при схемной реализации разреженных систем дизъюнктивных нормальных форм булевых функций // Изв. вузов. Электроника. 2024. Т. 29. № 5. С. 658–678. https://doi.org/10.24151/1561-5405-2024-29-5-658-678. – EDN: GIOVEJ.
Бибило Петр Николаевич
Объединенный институт проблем информатики Национальной академии наук Беларуси, Беларусь, 220012, г. Минск, ул. Сурганова, 6
Кардаш Сергей Николаевич
Объединенный институт проблем информатики Национальной академии наук Беларуси, Беларусь, 220012, г. Минск, ул. Сурганова, 6
Романов Владимир Ильич
Объединенный институт проблем информатики Национальной академии наук Беларуси, Беларусь, 220012, г. Минск, ул. Сурганова, 6
1. Amarú L., Gaillardon P.-E., Mitra S., De Micheli G. New logic synthesis as nanotechnology enabler // Proceedings of the IEEE. 2015. Vol. 103. No. 11. P. 2168–2195. https://doi.org/10.1109/JPROC.2015.2460377
2. Amarú L. G. New data structures and algorithms for logic synthesis and verification. Cham: Springer, 2017. XVI, 156 p.
3. Soeken M., Amarú L. G., Gaillardon P.-E., De Micheli G. Optimizing majority-inverter graphs with functional hashing // 2016 Design, Automation & Test in Europe Conference and Exhibition (DATE). Dresden: IEEE, 2016. P. 1030–1035.
4. Soeken M., Amarú L. G., Gaillardon P.-E., De Micheli G. Exact synthesis of majority-inverter graphs and its applications // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2017. Vol. 36. No. 11. P. 1842–1855. https://doi.org/10.1109/TCAD.2017.2664059
5. Гуров C. И. Мажоритарная алгебра для синтеза комбинационно-логических схем. Обзор // Таврический вестник информатики и математики. 2020. № 2 (47). С. 39–60. EDN: CNJUKV.
6. Böttcher A., Kumm M. Towards globally optimal design of multipliers for FPGAs // IEEE Transactions on Computers. 2023. Vol. 72. No. 5. P. 1261–1273. https://doi.org/10.1109/TC.2023.3238128
7. Соловьев В. В. Проектирование на программируемых логических интегральных схемах быстрых компараторов большой разрядности // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2016. № 3. С. 198–205. EDN: WWZKPP.
8. Gorodecky D., Sousa L. Two-operand modular multiplication to small bit ranges // Advanced Boolean techniques: Selected papers from the 15th International Workshop on Boolean Problems / eds R. Drechsler, S. Huhn. Cham: Springer, 2023. P. 111–122. https://doi.org/10.1007/978-3-031-28916-3_8
9. Solomko M., Tadeyev P., Nazaruk V., Khariv N. Optimal performance of 16-bit acyclic adders of binary codes // Eastern-European Journal of Enterprise Technologies. 2019. Vol. 3. No. 4 (99). P. 21–36. https://doi.org/10.15587/1729-4061.2019.168485
10. Mailhot F., Di Micheli G. Algorithms for technology mapping based on binary decision diagrams and on Boolean operations // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1993. Vol. 12. No. 5. P. 599–620. https://doi.org/10.1109/43.277607
11. Kaxiras S., Martonosi M. Idle-unit switching activity: clock gating // Computer architecture techniques for power-efficiency / S. Kaxiras, M. Martonosi. Williston, VT: Morgan & Claypool, 2008. P. 51–57.
12. Авдеев Н. А., Бибило П. Н. Автоматизированное проектирование цифровых операционных устройств с пониженным энергопотреблением // Программная инженерия. 2021. Т. 12. № 2. С. 63–73. https://doi.org/10.17587/prin.12.63-73. – EDN: VSVBVZ.
13. Шашков А. С. Проектирование цифровых систем с пониженным энергопотреблением с применением технологии UPF-описания подсистемы питания // Информатика. 2015. № 3 (47). С. 90–104. EDN: ZWZPJX.
14. Тарасов И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования. М.: Горячая линия – Телеком, 2020. 538 с.
15. Закревский А. Д. Логический синтез каскадных схем. М.: Наука, 1981. 416 c.
16. Бибило П. Н., Ланкевич Ю. Ю. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-представлений систем булевых функций // Программные продукты и системы. 2020. № 3. С. 449–463. EDN: SAITXW.
17. Бибило П. Н. Бинарные диаграммы решений в логическом проектировании. М.: URSS: ЛЕНАНД, 2024. 560 с.
18. Бибило П. Н. Системы проектирования интегральных схем на основе языка VHDL: StateCAD, ModelSim, LeonardoSpectrum. М.: СОЛОН-Пресс, 2005. 384 с.
19. Бибило П. Н., Романов В. И. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2020. № 4. С. 9–16. https://doi.org/10.31114/2078-7707-2020-4-9-16. – EDN: ZHOFRS.
20. Торопов Н. Р. Минимизация систем булевых функций в классе ДНФ // Логическое проектирование: сб. науч. тр. Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. Вып. 4. С. 4–19.
21. Кардаш С. Н. Построение блочных разбиений систем булевых функций на основе задачи покрытия булевых матриц // BIG DATA и анализ высокого уровня: сб. науч. ст. IX Междунар. науч.-практ. конф. (Минск, 17–18 мая 2023 г.): в 2 ч. Ч. 2. Минск: БГУИР, 2023. С. 326–330. EDN: OGQMZK.
22. Бибило П. Н., Ланкевич Ю. Ю., Романов В. И. Логическая минимизация многоуровневых представлений систем булевых функций // Информационные технологии. 2023. Т. 29. № 2. С. 59–71. https://doi.org/10.17587/it.29.59-71. – EDN: RGJEJU.