Ц е л и . Рассматривается задача синтеза комбинационных схем в базисе двухвходовых логических элементов, в качестве которых выступают элементы И, ИЛИ, И-НЕ и ИЛИ-НЕ. Целью работы является исследование возможности применения алгебраической декомпозиции булевых функций  (в  англоязычной литературе bi-decomposition) для синтеза комбинационных схем.

М е т о д ы . Используемый метод алгебраической декомпозиции сводится к поиску в графе двухблочного взвешенного покрытия полными двудольными подграфами (бикликами).

Р е з у л ь т а т ы . Исходная булева функция задается двумя троичными матрицами, одна из которых представляет собой область булева пространства аргументов, где функция имеет значение 1, а другая – область булева пространства, где функция имеет значение 0. Рассматривается граф ортогональности строк троичных матриц, представляющих заданную булеву функцию. Описан способ получения двухблочного взвешенного покрытия бикликами графа ортогональности cтрок троичных матриц. Всем бикликам из получаемого покрытия в качестве веса определенным образом приписывается некоторое множество переменных, представляющих собой аргументы заданной функции. Каждая из этих биклик определяет булеву функцию, аргументами которой являются приписанные к биклике переменные. Полученные таким образом функции составляют разложение исходной функции.

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