Применение диаграмм решений не полностью определенных функций k-значной логики при синтезе логических схем

Цели. Рассматривается проблема схемной реализации не полностью определенных функций k-значной логики, заданных табличными представлениями. Изучается этап технологически независимой оптимизации. Целью этого этапа является получение по табличным представлениям не полностью определенных функций k-значной логики минимизированных представлений систем полностью определенных булевых функций, по которым выполняется технологическое отображение (technology mapping) – второй этап синтеза логических схем.
Методы. При синтезе логических схем на этапе технологически независимой оптимизации предлагается использовать доопределения многозначных диаграмм решений (Reduced Ordered Multi-valued Decision Diagrams, ROMDD), которые далее называются MDD, и доопределения бинарных диаграмм решений (Binary Decision Diagram, BDD), задающих не полностью определенные системы булевых функций. Доопределение MDD ориентировано на уменьшение числа вершин графа MDD, соответствующих кофакторам разложения Шеннона многозначной функции.
Результаты. Задача минимизации MDD сведена к решению задач минимальной раскраски неориентированных графов несовместимости кофакторов. Кодирование многозначных значений аргументов и значений функций k-значной логики двоичными кодами приводит к системам не полностью определенных булевых функций, которые также доопределяются с целью минимизации их многоуровневых BDD-представлений.
Заключение. Предложенный подход позволяет в два этапа провести доопределение частичных многозначных функций до полностью определенных булевых функций. На втором этапе используются известные и эффективные методы доопределения BDD, задающих системы не полностью определенных булевых функций. В результате такого двухэтапного подхода получаются минимизированные BDD-представления систем полностью определенных функций. По полностью определенным булевым функциям выполняется технологическое отображение в заданную библиотеку логических элементов, т. е. покрытие оптимизированных описаний систем булевых функций описаниями логических элементов.

1. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Н. И. Червяков [и др.]. – М. : Физматлит, 2003. – 288 c.

2. Особенности проектирования модулярных умножителей с помощью современных САПР / Р. А. Соловьев [и др.]. // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). – 2016. – № 1. – С. 249–254.

3. Амербаев, В. М. Реализация библиотеки модульных арифметических операций на основе алгоритмов минимизации логических функций / В. М. Амербаев, Р. А. Соловьев, Д. В. Тельпухов // Изв. ЮФУ. Техн. науки. – 2013. – № 7. – С. 221–225.

4. Multi-Valued Decision Diagrams for Logic Synthesis and Verification / T. Kam [et al.]. – Berkeley : College of Engineering University of California, 1996. – 39 p.

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

6. Drechsler, R. Binary Decision Diagrams: Theory and Implementation / R. Drechsler, B. Becker. – Springer, 1998. – 210 p.

7. Ebendt, R. Advanced BDD Optimization / R. Ebendt, G. Fey, R. Drechsler. – Springer, 2005. – 222 p.

8. Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification / eds.: S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.

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

10. Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. – М. : Вильямс, 2013. – 960 с.

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

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

13. Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.

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

15. Бибило, П. Н. Оценка энергопотребления логических КМОП-схем по их переключательной активности / П. Н. Бибило, Н. А. Кириенко // Микроэлектроника. – 2012. – № 1. – C. 65–77.

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

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

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

19. Бибило П. Н. Минимизация BDDI-представлений систем не полностью определенных булевых функций / П. Н. Бибило // Программная инженерия. – 2020. – Т. 11, № 3. – С. 152–168.

20. Ashenden, P. J. VHDL-2008. Just the New Stuff / P. J. Ashenden, J. Lewis. – Burlington : Morgan Kaufman Publishers, 2008. – 909 p.