informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2021-18-2-7-32inform-1120Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМинимизация многоуровневых представлений систем полностью определенных булевых функций с использованием разложений Шеннона и алгебраических представлений кофакторовMinimization of binary decision diagrams for systems of completely defined Boolean functions using Shannon expansions and algebraic representations of cofactorsБибилоП. Н.BibiloP. N.

Бибило Петр Николаевич - доктор технических наук, профессор, заведующий лабораторией.

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

Petr N. Bibilo - Dr. Sci. (Eng.), Professor, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.

st. Surganova, 6, Minsk, 220012.

bibilo@newman.bas-net.byРомановВ. И.RomanovV. I.

Романов Владимир Ильич - кандидат технических наук, доцент.

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

Vladimir I. Romanov - Cand. Sci. (Eng.), The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.

st. Surganova, 6, Minsk, 220012.

rom@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus202121042021182732Copyright © Бибило П.Н., Романов В.И., 20212021Бибило П.Н., Романов В.И.Bibilo P.N., Romanov V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1120

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

In the systems of digital VLSI design (Very Large Integrated Circuits), the BDD (Binary Decision Diagram) is used for VLSI verification, as well as for technologically independent optimization as the first stage in the synthesis of logic circuits in various technological bases. The BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph corresponds to the complete or reduced Shannon expansion formula. When BDD representation for systems of Boolean functions is constructed, it is possible to perform additional logical optimization based on the proposed method of searching for algebraic representations of cofactors (subfunctions) of the same BDD level in the form of a disjunction, conjunction either exclusive-or of cofactors of the same level or lower levels of BDD. A directed BDD graph for a system of functions is constructed on the basis of Shannon expansion of all component functions of the system by the same permutation of variables. The method allows to reduce the number of literals by replacing the Shannon expansion formulas with simpler formulas that are disjunctions or conjunctions of cofactors, and to reduce the number of literals in specifying a system of Boolean functions. The number of literals in algebraic multilevel representations of systems of fully defined Boolean functions is the main optimization criterion in the synthesis of combinational circuits from librarian logic elements.

система булевых функцийдизъюнктивная нормальная формаBinary Decision Diagramразложение Шеннонасинтез логической схемыСБИСsystem of Boolean functionsdisjunctive normal formBinary Decision DiagramShannon expansiondigital logic synthesisVLSIReferencesLogic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. - Boston : Kluwer Academic Publishers, 1984. - 193 p.Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. L. Logic Minimization Algorithm for VLSI Synthesis. Boston, Kluwer Academic Publishers, 1984, 193 p.Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. - М. : Наука, 1981. - 416 c.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. - 1990. - Т. 78, № 2. - С. 38-83.Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multi-level combinational logic circuits. Trudy Institute inzhenerov po jelektronike i radiotehnike [Proceedings of the Institute of Electronics and Radio Engineering], 1990, vol. 78, no. 2, рр. 38-83 (In Russ.).Тарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. - М. : Горячая линия - Телеком, 2020. - 538 с.Tarasov I. E. PLIS Xilinx. Yazyki opisaniya apparatury VHDL i Verilog, SAPR, priemy proektirovaniya. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques. Moscow, Goryachaya liniya - Telekom, 2020, 538 р.Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. - Минск : Наука и техника, 1975. - 184 с.Sintez asinhronnyh avtomatov na EHVM. Synthesis of Asynchronous Automata on a Computer. In Zakrevskogo A. D. (ed.). Minsk, Nauka i tekhnika, 1975, 184 р.Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM J. of Research and Development. -1987. - Vol. 31, no. 2. - P. 187-198.Brayton K. R. Factoring logic functions. IBM Journal of Research and Development, 1987, vol. 31, no. 2, рр. 187-198.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.Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: a multiple-level logic optimization systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. 6, iss. 6, рр. 1062-1081.Boolean decomposition in multilevel logic optimization / S. Devadas [et al.] // IEEE J. of Solid-State Circuits. - 1989. - Vol. 24, no. 2. - P. 399-407.Devadas S., Wang A. R., Newton A. R., Sangiovanni-Vincentelli A. Boolean decomposition in multilevel logic optimization. IEEE Journal of Solid-State Circuits, 1989, vol. 24, no. 2, рр. 399-407.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.Brayton R., Mishchenko A., Chatterjee S. Boolean factoring and decomposition of logic networks. In Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2011, рр. 47-66.Curtis, H. A. A New Approach to the Design of Switching Circuit / H. A. Curtis. - Princeton, Van Nostrand, 1962. - 635 p.Curtis H. A. A New Approach to the Design of Switching Circuit. Princeton, Van Nostrand, 1962, 635 p.Scholl, C. Functional Decomposition with Applications to FPGA Synthesis / C. Scholl. - Kluwer Academic Publishers, 2001. - 288 p.Scholl C. Functional Decomposition with Applications to FPGA Synthesis. Kluwer Academic Publishers, 2001, 288 p.Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. - Минск : Беларус. навука, 2006. - 327 с.Pottosin Yu. V., Shestakov E. A. Tablichnye metody dekompozicii sistem polnost'yu opredelennyh bulevyh funkcij. Tabular methods for decomposition of systems of completely defined Boolean functions. Minsk, Belaruskaja navuka, 2006, 327 р. (In Russ.).Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. - Минск : Беларус. навука, 2009. - 211 с.Bibilo P. N. Dekompoziciya bulevyh funkcij na osnove resheniya logicheskih uravnenij. Decomposition of Boolean Functions Based on the Solution of Logical Equations. Minsk, Belaruskaja navuka, 2009, 211 p. (In Russ.).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.Lin H.-P., Jiang J.-H. R., Lee R.-R. Ashenhurst decomposition using SAT and interpolation. In Khatri S. P., Gulati K. (eds.). Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, 2011, рр. 67-86.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.Bryant R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 1986, vol. 35, no. 8, рр. 677-691.Drechsler, R. Binary Decision Diagrams: Theory and Implementation / R. Drechsler, B. Becker. -Springer, 1998. - 210 p.Drechsler R., Becker B. Binary Decision Diagrams: Theory and Implementation. Springer, 1998, 210 p.Ebendt, R. Advanced BDD Optimization / R. Ebendt , G. Fey, R. Drechsler. - Springer, 2005. - 222 p.Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.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.Bryant R. E., Meinel C. Ordered binary decision diagrams. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Logic Synthesis and Verification. Kluwer Academic Publishers, 2002, рр. 285-307.Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications / C. Meinel, T. Theobald. - Berlin, Heidelberg : Springer-Verlag, 1998. - 267 p.Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. - М. : Вильямс, 2013. - 960 с.Knuth D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 2011, 912 р.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. - Минск : Беларус. навука, 2014. - 231 с.Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (In Russ.).Уткин, А. А. Анализ логических сетей и техника булевых вычислений / А. А. Уткин. - Минск : Наука и техника, 1979. - 152 с.Utkin A. A. Analiz logicheskih setej i tekhnika bulevyh vychislenij. The analysis of logical networks and the technique of Boolean calculations. Minsk, Nauka i tekhnika, 1979, 152 р. (In Russ.).Романов, В. И. Программные средства для решения логико-комбинаторных задач / В. И. Романов // Информатика. - 2005. - № 4(8). - С. 114-123.Romanov V. I. Software tools for the solution of the logical-combinatorial task. Informatika [Informatics], 2005, no. 4(8), рр. 114-123 (In Russ.).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. - 2017. - № 8. - С. 369-384.Bibilo P. N., Lankevich Yu. Yu. The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion. Programmnaya inzheneriya [Software Engineering], 2017, no. 8, рр. 369-384 (In Russ.).Goldberg, E. BerkMin: a fast and robust SAT-solver / E. Goldberg , Y. Novikov // Discrete Applied Mathematics. - 2007. - Vol. 155, no. 12. - P. 1549-1561.Goldberg E., Novikov Y. BerkMin: a fast and robust SAT-solver. Discrete Applied Mathematics, 2007, vol. 155, no. 12, pp. 1549-1561.Handbook of Satisfiability / eds.: A. Biere, M. Heule, H. van Maaren, T. Valsh. - IOS Press, 2009. -980 p.Handbook of Satisfiability. In Biere A., Heule M., Van Maaren H., Valsh T. (eds.). IOS Press, 2009, 980 p.Романовский, И. В. Дискретный анализ : учебное пособие / И. В. Романовский. - 4-е изд., испр. и доп. - СПб. : Невский Диалект, БХВ-Петербург, 2008. - 336 с.Romanovskij I. V. Diskretnyj analiz. Discrete Analysis. Saint Petersburg, Nevskij Dialekt, BHV-Peterburg, 2008, 336 р. (In Russ.).Бибило, П. Н. Синтез комбинационных схем методами функциональной декомпозиции / П. Н. Бибило, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.Bibilo P. N., Enin S. V. Sintez kombinacionnyh skhem metodami funkcional'noj dekompozicii. Synthesis of Combination Circuits by Methods of Functional Decomposition. Minsk, Nauka i tekhnika, 1987, 189 р. (In Russ.).Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. - Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. - Вып. 4. - С. 4-19.Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4-19 (In Russ.).Бибило, П. Н. Минимизация многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. - 2017. - № 2(54). - С. 45-57.Bibilo P. N., Lankevich Yu. Yu. Minimizing multilevel representations of systems of Boolean functions based on Shannon expansion. Informatika [Informatics], 2017, no. 2(54), рр. 45-57 (In Russ.).Бибило, П. Н. Логическая минимизация булевых сетей с использованием разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Информатика. - 2019. - Т. 16, № 2. - С. 73-89.Bibilo P. N., Lankevich Yu. Yu. Logical optimization of Boolean nets using Shannon eXpansion. Informatika [Informatics], 2019, vol. 16, no. 2, рр. 73-89 (In Russ.).Ashenden, P. J. VHDL-2008. Just the New Stuff / P. J. Ashenden, J. Lewis. - Burlington, MA, USA : Morgan Kaufman Publishers, 2008. - 909 p.Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff. Burlington, MA, USA, Morgan Kaufman Publishers, 2008, 909 p.Бибило, П. Н. Системы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. - М. : СОЛОН-Пресс, 2005. - 384 с.Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim, LeonardoSpectrum. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum. Moscow, SOLON-Press, 2005, 384 р. (In Russ.).

The authors declare that there are no conflicts of interest present.