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

В системах проектирования цифровых СБИС (сверхбольших интегральных схем) графовый аппарат BDD (Binary Decision Diagram - бинарная диаграмма решений) применяется при верификации СБИС, а также при технологически независимой оптимизации, выполняемой как первый этап синтеза логических схем в различных технологических базисах. BDD представляет собой ациклический граф, задающий булеву функцию либо систему булевых функций. Каждой вершине этого графа соответствует полная или редуцированная формула разложения Шеннона. После получения BDD-представлений систем булевых функций предлагается выполнять дополнительные логические оптимизации на основе описываемого в статье метода поиска алгебраических представлений кофакторов (подфункций разложения Шеннона) одного уровня BDD в виде дизъюнкции, конъюнкции либо суммы по модулю два подфункций того же уровня либо нижних уровней BDD. Ориентированный граф BDD для системы функций строится на основе разложений Шеннона всех компонентных функций системы по одной и той же перестановке переменных. Метод позволяет уменьшать число литералов путем замены формул разложений Шеннона более простыми логическими формулами и сокращать число литералов в описании системы булевых функций. Число литералов в алгебраических многоуровневых представлениях систем полностью определенных булевых функций является основным критерием логической оптимизации при синтезе комбинационных схем из библиотечных логических элементов.

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

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

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

4. Тарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. - М. : Горячая линия - Телеком, 2020. - 538 с.

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

6. Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM J. of Research and Development. -1987. - Vol. 31, no. 2. - P. 187-198.

7. MIS: a multiple-level logic optimization systems / R. K. Brayton [et al.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1987. - Vol. 6, iss. 6. - P. 1062-1081.

8. Boolean decomposition in multilevel logic optimization / S. Devadas [et al.] // IEEE J. of Solid-State Circuits. - 1989. - Vol. 24, no. 2. - P. 399-407.

9. Brayton, R. Boolean factoring and decomposition of logic networks / R. Brayton, A. Mishchenko, S. Chatterjee; eds.: S. P. Khatri, K. Gulati // Advanced Techniques in Logic Synthesis, Optimizations and Applications. - Springer, 2011. - P. 47-66.

10. Curtis, H. A. A New Approach to the Design of Switching Circuit / H. A. Curtis. - Princeton, Van Nostrand, 1962. - 635 p.

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

12. Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. - Минск : Беларус. навука, 2006. - 327 с.

13. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. - Минск : Беларус. навука, 2009. - 211 с.

14. Lin, H.-P. Ashenhurst decomposition using SAT and interpolation / H.-P. Lin, J.-H. R. Jiang, R.-R. Lee; eds.: S. P. Khatri, K. Gulati // Advanced Techniques in Logic Synthesis, Optimizations and Applications. -Springer, 2011. - P. 67-86.

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

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

17. Ebendt, R. Advanced BDD Optimization / R. Ebendt , G. Fey, R. Drechsler. - Springer, 2005. - 222 p.

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

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

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

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

22. Уткин, А. А. Анализ логических сетей и техника булевых вычислений / А. А. Уткин. - Минск : Наука и техника, 1979. - 152 с.

23. Романов, В. И. Программные средства для решения логико-комбинаторных задач / В. И. Романов // Информатика. - 2005. - № 4(8). - С. 114-123.

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

25. Goldberg, E. BerkMin: a fast and robust SAT-solver / E. Goldberg , Y. Novikov // Discrete Applied Mathematics. - 2007. - Vol. 155, no. 12. - P. 1549-1561.

26. Handbook of Satisfiability / eds.: A. Biere, M. Heule, H. van Maaren, T. Valsh. - IOS Press, 2009. -980 p.

27. Романовский, И. В. Дискретный анализ : учебное пособие / И. В. Романовский. - 4-е изд., испр. и доп. - СПб. : Невский Диалект, БХВ-Петербург, 2008. - 336 с.

28. Бибило, П. Н. Синтез комбинационных схем методами функциональной декомпозиции / П. Н. Бибило, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.

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

30. Бибило, П. Н. Минимизация многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. - 2017. - № 2(54). - С. 45-57.

31. Бибило, П. Н. Логическая минимизация булевых сетей с использованием разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. - 2019. - Т. 16, № 2. - С. 73-89.

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

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