MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION
Abstract
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.
About the Authors
P. N. Bibilo
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Y. Y. Lankevich
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Шеннон, К. Синтез двухполюсных переключательных схем / К. Шеннон // Работы по теории информации и кибернетике. – М. : ИЛ, 1963. – С. 59–105.
2. Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.
3. Akers, S.B. Binary Decision Diagrams / S.B. Akers // IEEE Trans. on Computers. – 1978. – Vol. C–27, no. 6. – P. 509–516.
4. 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.
5. 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.
6. Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.
7. Кнут, Д.Э. Искусство программирования / Д.Э. Кнут. – М. : Вильямс, 2013. – Т. 4, А : Комбинаторные алгоритмы, ч. 1. – 960 с.
8. Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.
9. Карпов, Ю.Г. MODEL CHECKING. Верификация параллельных и распределенных программных систем / Ю.Г. Карпов. – СПб. : БХВ-Петербург, 2010. – 560 с.
10. Бибило, П.Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П.Н. Бибило. – М. : СОЛОН-Пресс, 2005. – 384 с.
11. Бибило, П.Н. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системыи машины. – 2009. – № 6. – С. 42–49.
12. Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.
13. Закревский, А.Д. Вычисления в многомерном булевом пространстве / А.Д. Закревский. – Минск : ОИПИ НАН Беларуси, 2011. – 106 с.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. Бибило, П.Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П.Н. Бибило, В.И. Романов. – Минск :Беларус. навука, 2011. – 279 с.
21. Поляков, А.К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры /А.К. Поляков. – М. : СОЛОН-Пресс, 2003. – 320 с.
22. Лохов, А. Функциональная верификация СБИС в свете решений Mentor Graphics /А. Лохов // Электроника: наука, технология, бизнес. – 2004. – № 1. – С. 58–62.
Review
For citations:
Bibilo P.N., Lankevich Y.Y. MINIMIZING THE MULTILEVEL REPRESENTATIONS OF SYSTEMS OF BOOLEAN FUNCTIONS BASED ON SHANNON DECOMPOSITION. Informatics. 2017;(2(54)):45-57. (In Russ.)
Views: 811
Email this article 