Дизъюнктивные и конъюнктивные разложения не полностью определенных булевых функций в бинарной диаграмме решений

Цели. Рассматриваются задачи минимизации числа функций – кофакторов (подфункций) разложения Шеннона, находящихся на одном уровне бинарной диаграммы решений (Binary Decision Diagram, BDD), которая представляет систему не полностью определенных (частичных) булевых функций. Для сокращения числа функций предлагается находить подмножество таких функций, которые могут быть выражены в виде алгебраических разложений – дизъюнкций либо конъюнкций других доопределенных частичных функций. При этом ориентированный граф вхождений функций в разложения не должен содержать контуров.

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

Результаты. Показано, что составляемые логические уравнения легко преобразуются к конъюнктивной нормальной форме (КНФ), а нахождение корней таких уравнений сведено к задаче выполнимости булевой формулы, представленной в виде КНФ, для решения которой известны эффективные методы и программы.

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

1. Бибило, П. Н. Бинарные диаграммы решений в логическом проектировании / П. Н. Бибило. - М. : Ленанд, 2024. - 560 с.

2. Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2002. - Vol. 21, no. 7. - P. 866-876.

3. Бибило, П. Н. Экспериментальное исследование алгоритмов минимизации BDDI-представлений систем булевых функций с использованием алгебраических разложений кофакторов / П. Н. Бибило, В. И. Романов // Программная инженерия. - 2022. - Т. 13, № 2. - С. 51-67.

4. Handbook of Satisfiability / ed.: A. Biere, M. Heule, H. van Maaren, T. Valsh. - IOS Press, 2009. - 980 p.

5. Goldberg, E. BerkMin: a fast and robust sat-solver / E. Goldberg, Y. Novikov // Discrete Applied Mathematics. - 2007. - Vol. 155, no. 12. - P. 1549-1561.

6. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. - М. : Наука, 1981. - 416 c.

7. Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. - 2000. - Т. 7, вып. 2. - С. 22-46.

8. Закревский, А. Д. Логические уравнения / А. Д. Закревский. - Минск : Наука и техника, 1975. - 96 c.

9. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. - Минск : Беларус. навука, 2009. - 211 с.

10. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. - М. : Наука, 1990. - 384 с.

11. Бибило, П. Н. Минимизация BDDI-представлений систем не полностью определенных булевых функций / П. Н. Бибило // Программная инженерия. - 2020. - Т. 11, № 3. - С. 152-168.

12. Бибило, П. Н. Минимизация многоуровневых представлений систем полностью определенных булевых функций с использованием разложений Шеннона и алгебраических представлений кофакторов / П. Н. Бибило, В. И. Романов // Информатика. - 2021. - Т. 18, № 2. - С. 7−32.

13. Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // Труды Института инженеров по электротехнике и радиоэлектронике. - 1990. - Т. 78, № 2. - С. 38-83.