DOI: 10.17587/prin.11.152-168

УДК: 517.98

Минимизация BDDI - представлений систем неполностью определенных булевых функций

П. Н. Бибило, д-р техн. наук, проф., зав. лабораторией, bibilo@newman.bas-net.by, Объединенный институт проблем информатики Национальной академии наук Беларуси, Минск

Предложена модификация BDD-представлений систем неполностью определенных (частич­ных) булевых функций, названная BDDI (Binary Decision Diagram with Inverse cofactors), и алгоритмы минимизации BDDI, результатом работы которых являются многоуровневые представления систем полностью определенных функций в виде формул разложений Шеннона c использованием как одинаковых, так и взаимно инверсных подфункций. Минимизация числа взаимно инверсных частичных подфункций на одном уровне BDDI-представления системы частичных функций сведена к решению комбинаторной задачи нахождения кратчайшей имплицирующей формы троичной матрицы, задающей значения подфункций этого уровня BDDI-представления.

Ключевые слова: булева функция, дизъюнктивная нормальная форма (ДНФ), разложение Шеннона, Binary Decision Diagram (BDD), раскраска графа, синтез логической схемы

Стр. 152–168