Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70208010.17587/it.31.526-537Cad-systemsСистемы автоматизированного проектированияResearch ArticlePolarization of functions when minimizing of Boolean netsПоляризация функций при минимизации булевых сетейBibiloP. N.БибилоП. Н.
Belarus

Dr. Sci. (Eng.), Professor

д-р техн. наук, проф.

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

Ph. D. (Eng.), Associate Prof.

канд. техн. наук, доц.

rom@newman.bas-net.byThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusОбъединенный институт проблем информатики Национальной академии наук Беларуси1510202531105265370202202602022026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702080

The results of an experimental study of a program for technologically independent minimization of multilevel representations of systems of fully defined functions in the form of Boolean nets, which are based on Shannon expansions of systems of disjunctive normal forms (DNF) of Boolean functions, are described. The main attention is paid to the effectiveness of using the choice of the best (in terms of the number of literals of Boolean variables) function polarization option when minimizing of Boolean nets. Polarization refers to the choice of an inverse or conventional form of assignment of each of the system functions. For minimized polarized Boolean nets, logic circuits are synthesized in the design library of digital ASIC (Application-Specific Integrated Circuits). The obtained results are compared in terms of crystal area and speed (time delay) with the synthesis results for minimized unpolarized Boolean nets and for jointly and separately minimized Boolean nets built using polarized DNF systems.

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

the system of Boolean functionspolarization of Boolean functionsBoolean netdigital logic synthesisVHDLASICсистема булевых функцийполяризация булевых функцийбулева сетьсинтез логической схемыVHDLзаказная СБИСBrayton R. K., Hachtel G. D., Sangiovanni-Vincentel- li А. L. Synthesis of multi-level combinational logic circuits, Trudy Institute inzhenerov po jelektronike i radiotehnike, 1990, vol. 78, no. 2, pp. 38—83 (In Russian).Брейтон Р. К., Хэчтел Г. Д., Санджованни-Винчентелли А. Л. Синтез многоуровневых комбинационных логических схем // ТИИЭР. 1990. Т. 78, № 2. С. 38—83.Zakrevskij А. D. Logical Synthesis of Cascading Circuit, Moscow, Nauka, 1981, 416 р. (in Russian).Закревский А. Д. Логический синтез каскадных схем. М.: Наука, 1981. 416 c.Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli А. L. Logic Minimization Algorithm for VLSI Synthesis, Boston, Kluwer Academic Publishers, 1984, 193 p.Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni- Vincentelli А. L. Logic Minimization Algorithm for VLSI Synthesis. Boston: Kluwer Academic Publishers, 1984. 193 p.Zakrevskii A. D. ed. Synthesis of Asynchronous Automata on a Computer, Minsk, Nauka i tekhnika, 1975, 184 p. (in Russian).Синтез асинхронных автоматов на ЭВМ / Под ред. А. Д. Закревского. Минск: Наука и техника, 1975. 184 с.Brayton K. R. Factoring logic functions, IBM J. Res. and Developm., 1987, vol. 31, no. 2, pp. 187—198.Brayton K. R. Factoring logic functions // IBM J. Res. and Developm. 1987. V. 31, N. 2. P. 187—198.Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: А multiple-level logic optimization systems, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1987, vol. CAD-6, no. 6, pp. 1062—1081.Brayton R. K., Rudell R., Sangiovanni-Vincentelli A. L., Wang A. R. MIS: А multiple-level logic optimization systems // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 1987. Vol. CAD-6, N. 6. P. 1062—1081.Wey C., Chang S.-M., Jou J.-Y. OPAM: an efficient output phase assignment for multilevel logic minimization, Proceedings 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp. 271—273, DOI: 10.1109/ ICCD.1989.63369.Wey C., Chang S.-M., Jou J.-Y. OPAM: an efficient output phase assignment for multilevel logic minimization // Proceedings 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors. P. 271—273. DOI: 10.1109/ICCD.1989.63369.Bibilo P. N. Binary decision diagrams in logical design, Moscow, LENAND, 2024, 560 p. (in Russian).Бибило П. Н. Бинарные диаграммы решений в логическом проектировании. М.: ЛЕНАНД, 2024. 560 с.Wey C. L., Chang T. Y. An efficient output assignment for PLA minimization, IEEE Trans. Computer-Aided Design, 1990, vol. 9, no. 1, pp. 1—7.Wey C. L., Chang T. Y. An efficient output assignment for PLA minimization // IEEE Trans. Comput.-AidedDesign. 1990. Vol. 9, N. 1. P. 1—7.Bibilo P. N., Romanov V. I. The system of logical optimization of functional structural descriptions of digital circuits based on production-frame knowledge representation model, Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh system, 2020, Sb. trudov pod obshch. red. akad. RANA. L. Stempkovskogo, Moscow, IPPMRAN, 2020, no. 4, pp. 9—16 (in Russian).Бибило П. Н., Романов В. И. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний // Проблемы разработки перспективных микро- и наноэлектронных систем. 2020. Сб. трудов под общ. ред. акад. РАН А. Л. Стемпковского. М.: ИППМ РАН, 2020. № 4. С. 9—16.Toropov N. R. Minimization of systems of Boolean functions in the class DNF, Logicheskoe proektirovanie, Minsk, Institut tehnicheskoj kibernetiki Nacional’noj akademii nauk Belarusi. 1999, no. 4, pp. 4—19 (in Russian).Торопов Н. Р. Минимизация систем булевых функций в классе ДНФ // Логическое проектирование. Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. Вып. 4. С. 4—19.Sasao T. Input Variable Assignment and Output Phase Optimization of PLA’s, IEEE Trans. Comput., 1984, vol. C-33, no. 10, pp. 879—894.Sasao T. Input Variable Assignment and Output Phase Optimization of PLA’s // IEEE Trans. Comput. 1984. V. C-33, N. 10. P. 879—894.Das A., Pradhan S. N. Thermal-aware Output Polarity Selection Based on And-Inverter Graph Manipulation, Recent Advances in Electrical & Electronic Engineering, 2019, vol.12, no. 1, pp. 30—39, DOI: 10.2174/2352096511666180320120016Das A., Pradhan S. N. Thermal-aware Output Polarity Selection Based on And-Inverter Graph Manipulation // Recent Advances in Electrical & Electronic Engineering. 2019. Vol. 12, N. 1. P. 30—39. DOI: 10.2174/2352096511666180320120016.Bibilo P. N., Lankevich Yu. Yu. Experimental investigation of effectiveness of algorithms for minimizing BDD representations of Boolean function systems. Software & Systems, 2020, vol. 33, no. 3, pp. 449—463 (in Russian), DOI: 10.15827/0236-235X.131.449-463.Бибило П. Н., Ланкевич Ю. Ю. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD- представлений систем булевых функций // Программные продукты и системы. 2020. Т. 33, № 3. С. 449—463. DOI: 10.15827/0236-235X.131.449-463.Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).Бибило П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum. М.: СОЛОН-Пресс, 2005. 384 с.Kirienko N. A. An algorithm for converting functional descriptions of logic circuits using inverse representations, Tanaevskie chteniya: doklady Devyatoj Mezhdunarodnoj nauchnoj konferencii (29—30 marta 2021, Minsk), Minsk, OIPI NAN Belarusi, 2021, pp. 39—43 (in Russian).Кириенко Н. А. Алгоритм преобразования функциональных описаний логических схем с использованием инверсных представлений. // Танаевские чтения: доклады Девятой Международной научной конференции (29—30 марта 2021 г., Минск). Минск: ОИПИ НАН Беларуси, 2021. С. 39—43.Bibilo P. N. Joint and separate minimization of multilevel representations of Boolean function systems, Informacionnye tehnologii, 2023, vol. 29, no. 11, pp. 574—582, DOI: 10.17587/ it.29.574-582 (in Russian).Бибило П. Н. Совместная и раздельная минимизация многоуровневых представлений систем булевых функций // Информационные технологии. 2023. Т. 29, № 11. С. 574—582. DOI: 10.17587/it.29.574-582.