DOI: 10.17587/prin.16.181-189

УДК: 519.714.5

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

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

Блочное покрытие системы дизъюнктивных нормальных форм (ДНФ) полностью определенных булевых функций заключается в группировании элементарных конъюнкций в подсистемы (блоки) с ограниченными значениями числа входных переменных, функций и конъюнкций. Для более эффективного решения задачи логического синтеза предлагается алгоритм сокращения числа различных ДНФ в паре пересекающихся блоков. Алгоритм основан на построении неориентированного графа и раскраске его в минимальное число цветов. Это позволяет сокращать сложность многоуровневых представлений функций блоков, так как для разреженных систем ДНФ булевых функций в блоках чаще оказываются одинаковые ДНФ. Для матричных форм разреженных систем ДНФ троичная матрица, задающая элементарные конъюнкции, содержит большую долю неопределенных значений, соответствующих в алгебраической записи отсутствующим литералам булевых входных переменных, а булева матрица, задающая вхождения конъюнкций в ДНФ булевых функций, содержит большую долю нулевых значений. Таким образом, технологически независимая оптимизация разреженных систем ДНФ булевых функций разбивается на два этапа — блочное покрытие и минимизацию многоуровневых представлений функций блоков в виде BDD или булевых сетей.

Ключевые слова: система булевых функций, ДНФ, блочное покрытие системы ДНФ, раскраска неориентированного графа, синтез логической схемы, заказная СБИС

Стр. 181—189

Ссылка для цитирования:
Бибило П. Н. Алгоритм дополнительной оптимизации блочного покрытия системы дизъюнктивных нормальных форм булевых функций // Программная инженерия. 2025. Том 16, № 4. С. 181—189. DOI: 10.17587/prin.16.181-189.

Полный текст на eLIBRARY