informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-211Research ArticleАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯCOMPUTER AIDED DESIGNМИНИМИЗАЦИЯ МНОГОУРОВНЕВЫХ ПРЕДСТАВЛЕНИЙ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ РАЗЛОЖЕНИЯ ШЕННОНАMINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITIONБибилоП. Н.BibiloP. N.bibilo@newman.bas-net.byЛанкевичЮ. Ю.LankevichY. Y.yurafreedom18@gmail.comОбъединенный институт проблем информатики НАН БеларусиBelarus20171506201702(54)4557Copyright © Бибило П.Н., Ланкевич Ю.Ю., 20172017Бибило П.Н., Ланкевич Ю.Ю.Bibilo P.N., 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/211

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

A locally optimal algorithm is proposed to form a permutation of variables, which are used to obtain successive Shannon decompositions of a system of disjunctive normal forms of completely specified Boolean functions. The goal of it is a multilevel representation of functions which is called a reduced ordered Binary Decision Diagram. The results of experimental comparison of the program implementing the proposed algorithm and the program implementing the algorithm for enumeration of random permutations are given. The results show the advantage of the proposed algorithm when it is used for synthesis of logical circuits on the basis of library elements.

ReferencesШеннон, К. Синтез двухполюсных переключательных схем / К. Шеннон // Работы по теории информации и кибернетике. – М. : ИЛ, 1963. – С. 59–105.Шеннон, К. Синтез двухполюсных переключательных схем / К. Шеннон // Работы по теории информации и кибернетике. – М. : ИЛ, 1963. – С. 59–105.Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Akers, S.B. Binary Decision Diagrams / S.B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C–27, no. 6. – P. 509–516.Akers, S.B. Binary Decision Diagrams / S.B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C–27, no. 6. – P. 509–516.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 / R.E. Bryant //IEEE Transactions on Computers. – 1986. – Vol. 35, no. 8. – P. 677–691.Bryant, R.E. Ordered Binary Decision Diagrams / R.E. Bryant, C. Meinel // Logic synthesis and verification. – Boston, Dordrecht, London : Kluwer Academic Publishers, 2002. – P. 285–307.Bryant, R.E. Ordered Binary Decision Diagrams / R.E. Bryant, C. Meinel // Logic synthesis and verification. – Boston, Dordrecht, London : Kluwer Academic Publishers, 2002. – P. 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. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.Кнут, Д.Э. Искусство программирования / Д.Э. Кнут. – М. : Вильямс, 2013. – Т. 4, А : Комбинаторные алгоритмы, ч. 1. – 960 с.Кнут, Д.Э. Искусство программирования / Д.Э. Кнут. – М. : Вильямс, 2013. – Т. 4, А : Комбинаторные алгоритмы, ч. 1. – 960 с.Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.Карпов, Ю.Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем / Ю.Г. Карпов. – СПб. : БХВ-Петербург, 2010. – 560 с.Карпов, Ю.Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем / Ю.Г. Карпов. – СПб. : БХВ-Петербург, 2010. – 560 с.Бибило, П.Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П.Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.Бибило, П.Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П.Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.Бибило, П.Н. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системыи машины. – 2009. – № 6. – С. 42–49.Бибило, П.Н. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системыи машины. – 2009. – № 6. – С. 42–49.Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.Закревский, А.Д. Вычисления в многомерном булевом пространстве / А.Д. Закревский. – Минск : ОИПИ НАН Беларуси, 2011. – 106 с.Закревский, А.Д. Вычисления в многомерном булевом пространстве / А.Д. Закревский. – Минск : ОИПИ НАН Беларуси, 2011. – 106 с.Ishiura, N. Minimization of binary decision diagrams based on exchange of variables /N. Ishiura, H. Sawada, S. Yajima // Computer-Aided Design : proc. 29th IEEE Intern. conf., Santa Clara, 11–14 Nov. 1991 / IEEE Computer Society. – Washington, 1991. – P. 472–475.Ishiura, N. Minimization of binary decision diagrams based on exchange of variables /N. Ishiura, H. Sawada, S. Yajima // Computer-Aided Design : proc. 29th IEEE Intern. conf., Santa Clara, 11–14 Nov. 1991 / IEEE Computer Society. – Washington, 1991. – P. 472–475.Jeong, S.-W. An efficient method for optimal BDD ordering computation / S.-W. Jeong, T.-S. Kim, F. Somenzi // VLSI and CAD : proc. of Intern. conf. – Taejon, 1993. – P. 252–256.Jeong, S.-W. An efficient method for optimal BDD ordering computation / S.-W. Jeong, T.-S. Kim, F. Somenzi // VLSI and CAD : proc. of Intern. conf. – Taejon, 1993. – P. 252–256.Friedman, S.J. Finding the optimal variable ordering for binary decision diagrams /S.J. Friedman, K.J. Supowit // IEEE Trans. Computers. – 1990. – Vol. 39, no. 5. – P. 710–713.Friedman, S.J. Finding the optimal variable ordering for binary decision diagrams /S.J. Friedman, K.J. Supowit // IEEE Trans. Computers. – 1990. – Vol. 39, no. 5. – P. 710–713.Fujii, H. Interleaving based variable ordering methods for ordered binary decision diagrams / H. Fujii, G. Ootomo, C. Hori // Computer-aided design : proc. of the 1993 IEEE/ACM Intern. conf., Santa Clara, 7–11 Nov. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 38–41.Fujii, H. Interleaving based variable ordering methods for ordered binary decision diagrams / H. Fujii, G. Ootomo, C. Hori // Computer-aided design : proc. of the 1993 IEEE/ACM Intern. conf., Santa Clara, 7–11 Nov. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 38–41.Dynamic variable reordering for BDD minimization / E. Felt [et al.] // Design Automation : proc. EURO-DAC, Hamburg, 20–24 Sep. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 130–135.Dynamic variable reordering for BDD minimization / E. Felt [et al.] // Design Automation : proc. EURO-DAC, Hamburg, 20–24 Sep. 1993 / IEEE Computer Society Press. – Los Alamitos, 1993. – P. 130–135.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/espressoexamples/ex. – Date of access : 20.03.2017.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/espressoexamples/ex. – Date of access : 20.03.2017.Бибило, П.Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П.Н. Бибило, В.И. Романов. – Минск :Беларус. навука, 2011. – 279 с.Бибило, П.Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П.Н. Бибило, В.И. Романов. – Минск :Беларус. навука, 2011. – 279 с.Поляков, А.К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры /А.К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.Поляков, А.К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры /А.К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.Лохов, А. Функциональная верификация СБИС в свете решений Mentor Graphics /А. Лохов // Электроника: наука, технология, бизнес. – 2004. – № 1. – С. 58–62.Лохов, А. Функциональная верификация СБИС в свете решений Mentor Graphics /А. Лохов // Электроника: наука, технология, бизнес. – 2004. – № 1. – С. 58–62.

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