МИНИМИЗАЦИЯ МНОГОУРОВНЕВЫХ ПРЕДСТАВЛЕНИЙ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ РАЗЛОЖЕНИЯ ШЕННОНА
Аннотация
Предлагается приближенный алгоритм формирования перестановки переменных, по каждой из которых последовательно строятся разложения Шеннона системы дизъюнктивных нормальных форм полностью определенных булевых функций с целью получения многоуровневого представления функций, называемого в литературе сокращенной упорядоченной диаграммой двоичного выбора либо диаграммой двоичных решений. Приводятся результаты экспериментального сравнения программы, реализующей предложенный алгоритм, с программой, реализующей алгоритм перебора случайных перестановок.
Об авторах
П. Н. Бибило
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Ю. Ю. Ланкевич
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
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.
Рецензия
Для цитирования:
Бибило П.Н., Ланкевич Ю.Ю. МИНИМИЗАЦИЯ МНОГОУРОВНЕВЫХ ПРЕДСТАВЛЕНИЙ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ РАЗЛОЖЕНИЯ ШЕННОНА. Информатика. 2017;(2(54)):45-57.
For citation:
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.)
Просмотров: 780
Послать статью по эл. почте 