Synthesis of combinational circuits by means of bi-decomposition of Boolean functions

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