informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-294Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNЛогическая оптимизация многоуровневых представлений систем булевых функций на основе блочного разбиения и разложения ШеннонаLogical optimization the multilevel representations of systems of Boolean functions based on partitioning into blocksand Shannon decompositionБибилоП. Н.BibiloP. N.

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

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

PetrN. Bibilo – D. Sc. (Engineering), Professor.

bibilo@newman.bas-net.byКириенкоН. А.KirienkoN. A.

Кириенко Наталья Алексеевна – кандидат технических наук, доцент.

Natalia A. Kirienko – Ph. D. (Engineering).

6, Surganovа Str., 220012, Minsk

kir@newman.bas-net.byЛанкевичЮ. Ю.LankevichY. Y.

Ланкевич Юрий Юрьевич – младший научный  сотрудник.

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

Yury Y. Lankevich – Researcher.

6, Surganovа Str., 220012, Minsk

yurafreedom18@gmail.comОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2018260920181535670Copyright © Бибило П.Н., Кириенко Н.А., Ланкевич Ю.Ю., 20182018Бибило П.Н., Кириенко Н.А., Ланкевич Ю.Ю.Bibilo P.N., Kirienko N.A., Lankevich Y.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/294

Описываются результаты экспериментального исследования эффективности применения процедур оптимизации систем булевых функций, предварительно выполняемых при синтезе комбинационных схем. Процедуры используют алгоритмы разбиения систем функций на подсистемы и алгоритмы оптимизации многоуровневых представлений функций на основе разложения Шеннона. Показывается, что разбиение исходной системы булевых функций на подсистемы и оптимизация подсистем на основе разложения Шеннона с нахождением инверсных подфункций, входящих в разложения (BDDI-оптимизация), во многих случаях позволяют при синтезе уменьшать площадь комбинационных схем из библиотечных элементов. Совместная BDDI-оптимизация является более предпочтительным методом по сравнению с раздельной технологически независимой BDDI-оптимизацией, так как площадь схем, построенных по совместным BDDI, в подавляющем числе случаев меньше площади схем, построенных по раздельным BDDI.

The results of experimental study of the effectiveness of optimization procedures for systems of Boolean functions which are used in the synthesis of combinational circuits are described. The procedures use algorithms for partitioning systems of functions into subsystems and algorithms for optimizing multilevel representations of functions based on Shannon decomposition. The Shannon decomposition uses the procedure for finding inverse subfunctions, contained  in decomposition result (BDDI-optimization). It is shown that these procedures can reduce the area of combinational circuits from library gates in many cases in the process of synthesis. Joint BDDI optimization is more preferable method in comparison to separate technologically independent BDDI optimization, since the area of circuits built on joint BDDI is smaller than the area of circuits built on separate BDDI in most cases.

булева функциядизъюнктивная нормальная формадиаграмма двоичного выбораразбиение системы булевых функцийсинтез логической схемыКМОП-технологияBoolean functiondisjunctive normal formbinary decision diagram (BDD)partitioning systems of functionssynthesis of logical circuitCMOS-technologyReferencesБрейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // ТИИЭР. – 1990. – Т. 78, № 2. – С. 38–83.Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Sintez mnogourovnevyh kombinacionnyh logicheskih skhem [Multilevel Logic Synthesis]. TIIJeR [TIIER], 1990, vol. 78, no. 2, рр. 38–83 (in Russian).Поляков, А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры / А. К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.Polyakov A. K. Yazyki VHDL i VERILOG v proektirovanii tsifrovoi apparatury. The VHDL and VERILOG Languages in Designing of Digital Hardware. Moscow, SOLON-Press Publ., 2003, 320 p. (in Russian).Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Zakrevskij A. D., Pottosin Ju. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Bases of Design of Discrete Devices. Moscow, Fizmatlit Publ., 2007, 592 р. (in Russian).Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascade Circuits. Moscow, Nauka Publ., 1981, 416 p. (in Russian).Sasao, T. FPGA design by generalized functional decomposition / T. Sasao // Representations of Discrete Functions ; ed. by T. Sasao, M. Fujita. – Kluwer Academic Publishers, 1996. – P. 233–258.Sasao T. FPGA design by generalized functional decomposition. Representations of Discrete Functions. Kluwer Academic Publishers, 1996, рр. 233–258.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.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Bibilo P. N. Primenenie diagramm dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Decision Diagrams at Synthesis of Logical Circuits. Minsk, Belarus. Navuka Publ., 2014, 231 p. (in Russian).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.Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification ; ed. by S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.Bryant R. E., Meinel C. Ordered binary decision diagrams. 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 Publ., 1998, 267 p.Amaru, L. G. New Data Structures and Algorithms for Logic Synthesis and Verification / L. G. Amaru. – Springer, 2017. – 156 p.Amaru L. G. New Data Structures and Algorithms for Logic Synthesis and Verification. Springer Publ., 2017, 156 p.Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.Chen M., Qin K., Ku H.-M., Mishra P. Validaciya na sistemnom urovne. Vysokourovnevoe modelirovanie i upravlenie testirovaniem. Validation at the System Level. High-Level Simulation and Testing Management. Moscow, Tekhnosfera Publ., 2014, 296 p. (in Russian).Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. – 2017. – № 3. – С. 369–384.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 with minimization of multilevel representations of systems of Boolean functions on the basis of the Shannon decomposition]. Programmnaya inzheneriya [Software Engineering], 2017, no. 3, рр. 369–384 (in Russian).Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка 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 Publ., 2005, 384 p. (in Russian).Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционнофреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. – Минск : Беларус. навука, 2011. – 279 с.Bibilo P. N., Romanov V. I. Logicheskoe proektirovanie diskretnyh ustrojstv s ispol'zovaniem produkcionnofrejmovoj modeli predstavlenija znanij. Logical Design of Discrete Devices with Use of Productional and Frame Model of Representation of Knowledge. Minsk, Belarus. Navuka Publ., 2011, 279 p. (in Russian).Григорьян, С. Г. Конструирование электронных устройств систем автоматизации и вычислительной техники / С. Г. Григорьян. – Ростов н/Д : Феникс, 2007. – 303 с.Grigor'yan S. G. Konstruirovanie jelektronnyh ustrojstv sistem avtomatizacii i vychislitel'noj tekhniki. Design of Electronic Devices of Automation Systems and Computers. Rostov n/D, Feniks Publ., 2007, 303 p. (in Russian).Кузовлев, В. И. Выявление высокоуровневых иерархических структур сверхбольших интегральных схем через сильно связанные логические группы / В. И. Кузовлев, Н. А. Иванова // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. – 2016. – № 4. – С. 4–18.Kuzovlev V. I., Ivanova N. A. Vyyavlenie vysokourovnevyh ierarhicheskih struktur sverhbol'shih integral'nyh skhem cherez sil'no svyazannye logicheskie gruppy [Circuit detection through tangled logic structures]. Vestnik MGTU im. N. E. Baumana, ser. Priborostroenie [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2016, no. 4, рр. 4–18 (in Russian).Netlist and system partitioning / A. B. Kahng [et al.] // VLSI Physical Design: From Graph Partitioning to Timing Closure. – Springer, 2011. – Chap. 2. – P. 31–54.Kahng A. B., Liening J., Markov I. L., Hu J. Netlist and system partitioning. VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, 2011, ch. 2, рр. 31–54.Бибило, П. Н. Оптимизационные преобразования логической схемы на основе блочного разбиения / П. Н. Бибило, Н. А. Кириенко // Информатика. – 2009. – № 3(23). – С. 5–15.Bibilo P. N., Kirienko N. A. Optimizacionnye preobrazovaniya logicheskoj skhemy na osnove blochnogo razbieniya [Optimizing conversions of a logic circuit by partitioning into blocks]. Informatika [Informatics], 2009, no. 3, рр. 5–15 (in Russian).Jeong, C. Computer-Aided Design of Digital Systems / C. Jeong // Department of Computer Science [Electronic resource]. – Mode of access: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex. – Date of access: 20.03.2018.Jeong C. Computer-Aided Design of Digital Systems. Department of Computer Science. Available at: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex (accessed 20.03.2018).

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