informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2023-20-2-39-64inform-1240Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNПрименение диаграмм решений не полностью определенных функций k-значной логики при синтезе логических схемApplication of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuitsБибилоП. Н.BibiloP. N.

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

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

Petr N. Bibilo, D. Sc. (Eng.), Prof.

st. Surganova, 6, Minsk, 220012

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

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

Objectives. The problem of circuit implementation of incompletely specified (partial) k-valued logic functions given by tabular representations is considered. The stage of technologically independent optimization is studied to obtain minimized representations of systems of completely specified Boolean functions from tabular representations of partial functions of k-valued logic. According to these representations of Boolean functions, technological mapping is performed at the second stage of the synthesis of logic circuits.Methods. Using additional definitions of Multi-valued Decision Diagrams (MDD) representing partial functions of k-valued logic, and Binary Decision Diagrams (BDD) representing partial systems of Boolean functions at the stage of technologically independent optimization is proposed. The task of additional definition of MDD is oriented to reducing the number of vertices of the MDD graph that correspond to the cofactors of the Shannon expansion of a multi-valued function.Results. The MDD minimization problem is reduced to solving the problems of coloring undirected graphs of incompatibility of cofactors by minimum number of colors. Encoding of multi-valued values of arguments and values of functions of k-valued logic by binary codes leads to systems of partial Boolean functions, which are also further defined in order to minimize their multi-level BDD representations.Conclusion. The proposed approach makes it possible to define partial multi-valued functions to fully defined Boolean functions in two stages. At the second stage, well-known and effective methods are used to redefine BDD representing systems of partial Boolean functions. As a result of this two-step approach, minimized BDD representations of systems of completely defined functions are obtained. According to completely defined Boolean functions, a technological mapping into a given library of logical elements is performed, i.e. the optimized descriptions of Boolean function systems are covered with descriptions of logical elements

не полностью определенные функцииk-значная логикаMulti-valued Decision Diagram (MDD)булевы функцииBinary Decision Diagram (BDD)разложение Шеннонасинтез логической схемыVHDLСБИСpartial functionsk-valued logicMulti-valued Decision Diagram (MDD)Boolean functionsBinary Decision Diagram (BDD)Shannon expansiondigital logic synthesisVHDLVLSIReferencesМодулярные параллельные вычислительные структуры нейропроцессорных систем / Н. И. Червяков [и др.]. – М. : Физматлит, 2003. – 288 c.Chervyakov N.I., Sakhnyuk P.A., Shaposhnikov A.V., Ryadnov S.A. Modulyarnye parallel'nye vychislitel'nye struktury neyroprotsessornykh system [Modular parallel computing structures of neuroprocessor systems]. M.: Fizmatlit, 2003, 288 p. (in Russ.).Особенности проектирования модулярных умножителей с помощью современных САПР / Р. А. Соловьев [и др.]. // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). – 2016. – № 1. – С. 249–254.Solov'ev R.A., Tel'puhov D.V., Balaka E.S., Ruhlov V.S., Mihmel' A.S. Osobennosti proektirovaniya modulyarnyh umnozhitelej s pomoshch'yu sovremennyh SAPR [Design features of modular multipliers using modern CAD]. // Problemy razrabotki perspektivnyh mikro- inanoelektronnyh sistem (MES). 2016, no. 1, pp. 249–254.Амербаев, В. М. Реализация библиотеки модульных арифметических операций на основе алгоритмов минимизации логических функций / В. М. Амербаев, Р. А. Соловьев, Д. В. Тельпухов // Изв. ЮФУ. Техн. науки. – 2013. – № 7. – С. 221–225.Amerbaev V.M., Solov'ev R.A., Tel'puhov D.V. Realizaciya biblioteki modul'nyh arifmeticheskih operacij na osnove algoritmov minimizacii logicheskih funkcij [Implementation of a library of modular arithmetic operations based on algorithms for minimizing logical functions]. // Izvestiya YUFU. Tekhnicheskienauki, Taganrog. 2013, no. 7, pp.221–225. (In Russ.).Multi-Valued Decision Diagrams for Logic Synthesis and Verification / T. Kam [et al.]. – Berkeley : College of Engineering University of California, 1996. – 39 p.Kam T., Villa T., Brayton R. K., Sangiovanni-Vincentelli A. L. Multi-Valued Decision Diagrams for Logic Synthesis and Verification // Memorandum No. UCB/ERL M96/75, 1996. 39 p.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.http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/ERL-96-75.pdfDrechsler, R. Binary Decision Diagrams: Theory and Implementation / R. Drechsler, B. Becker. – Springer, 1998. – 210 p.Bryant R. E. Graph-based algorithms for Boolean function manipulation // IEEE Transactions on Computers. – 1986. – Vol. 35, no. 8. – P. 677–691.Ebendt, R. Advanced BDD Optimization / R. Ebendt, G. Fey, R. Drechsler. – Springer, 2005. – 222 p.Drechsler R. Binary Decision Diagrams: Theory and Implementation. Springer, 1998. – 210 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.Ebendt R., Fey G, Drechsler R. Advanced BDD Optimization. Springer, 2005. – 222 p.Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.Bryant R. E., C. Meinel Ordered binary decision diagrams // Logic Synthesis and Verification / eds.: S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. – М. : Вильямс, 2013. – 960 с.Meinel C.,Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. – Berlin, Heidelberg: Springer-Verlag, 1998. – 267 p.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Knut D. E. Iskusstvo programmirovaniya. T. 4, A. Kombinatornye algoritmy. [The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.] CH. 1 : per. s angl.M.: Vil'yams, 2013, 960 p. (In Russ.).Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. – Boston, Kluwer Academic Publishers, 1984. – 193 p.Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. [Application of Binary Decision Diagrams in the Synthesis of Logic Circuits]. Minsk, Belaruskajanavuka, 2014, 231 p. (In Russ.).Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование : сб. науч. тр. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.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.Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetik iNacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4–19 (In Russ.).Бибило, П. Н. Оценка энергопотребления логических КМОП-схем по их переключательной активности / П. Н. Бибило, Н. А. Кириенко // Микроэлектроника. – 2012. – № 1. – C. 65–77.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.).Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.Bibilo P.N., Kirienko N.A. Ocenka energopotrebleniya logicheskih KMOP-skhem po ih pereklyuchatel'noj aktivnosti [Estimating Energy Consumption in Logical CMOS Circuits Based on Their Switching Activity] // Mikroelektronika, 2012, no. 1, pp. 65 – 77 (In Russ.).Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.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.).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Про-граммная инженерия. – 2017. – № 8. – С. 369–384.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. [Logical Synthesis of Cascading Circuit]. Moscow, Nauka, 1981, 416 р. (In Russ.).Бибило П. Н. Минимизация BDDI-представлений систем не полностью определенных булевых функций / П. Н. Бибило // Программная инженерия. – 2020. – Т. 11, № 3. – С. 152–168.Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov ZHegalkina pri minimizacii mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove razlozheniya SHennona [The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion]. Programmnayainzheneriya [Software Engineering], 2017, no. 8,рр. 369–384 (In Russ.).Ashenden, P. J. VHDL-2008. Just the New Stuff / P. J. Ashenden, J. Lewis. – Burlington : Morgan Kaufman Publishers, 2008. – 909 p.Bibilo P. N. Minimizaciya BDDI-predstavlenij sistem ne polnost'yu opredelennyh bulevyh funkcij [Minimization of Binary Decision Diagrams for Systemsof Incompletely Defined Boolean Functions using inverse cofactors] // Programmnaya inzheneriya [Software Engineering], 2020, vol. 11, no. 3, pp. 152–168 (In Russ.).Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff. – 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.

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