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

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

1. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.

2. Бибило, П. Н. Синтез комбинационных схем методом функциональной декомпозиции / П. Н. Бибило, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.

3. Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. - Минск : Беларуская навука, 2006. - 327 с.

4. Поттосин, Ю. В. Метод многоблочной параллельной декомпозиции системы частичных булевых функций / Ю. В. Поттосин // Информатика. - 2017. - № 3(55). - С. 92-98.

5. Поттосин, Ю. В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю. В. Поттосин, Е. А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф., Екатеринбург, 1998. - Екатеринбург : УрО РАН, 1998. -С. 185-189.