1
УДК 519.714
Особенности автоматизации синтеза
булевых функций
© А.А. Гурченков
1
, Е.К. Егорова
2
1
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
2
МАТИ — РГТУ им. К.Э. Циолковского, Москва, 121552, Россия
Изложен оригинальный подход к автоматическому синтезу дискретных уст-
ройств в базисе микросхем. Методические установки этого подхода основывают-
ся на математическом и информационном описаниях булевых функций и их
структурно-функциональной декомпозиции. Параллельная и последовательная де-
композиции по сложности (числу подформул) характеризуются одинаковым каче-
ством, но по глубине лучшим качеством (меньшим или равным значением) облада-
ет первая, поэтому для синтеза схем применена параллельная декомпозиция.
В частности, предложен вычислительный метод для нахождения оценок слож-
ности реализации произвольных булевых функций в базисе Жегалкина на основе
параллельной декомпозиции. Метод позволяет оценить возможность минимиза-
ции числа транзисторов и времени задержки схемы. Для алгоритма рассмотрены
несколько особых случаев с примерами. На основе этих особенностей внесены до-
полнения в алгоритм, в результате чего алгоритм стал универсальным.
Ключевые слова:
булевы функции, показатели сложности, минимизация, декомпо-
зиция, функциональные уравнения, схемы.
В данной работе применяется метод структурно-функциональной
декомпозиции булевых функций и схем из функциональных элемен-
тов [1–5]. При использовании структурно-функциональной декомпо-
зиции произвольной булевой функции, зависящей от любого конеч-
ного числа переменных, получены функционалы, позволяющие зара-
нее подсчитывать показатели качества синтеза — число элементов и
глубину схемы [2, 3, 6, 7]. Функционалы также могут быть использо-
ваны для оптимизации синтеза [1, 6, 8–10].
Для автоматического нахождения оценки здесь приводится алго-
ритм, позволяющий это легко сделать [5, 10]. Кроме того, рассмотрен
ряд особых случаев, для обработки которых пришлось модифициро-
вать построенный алгоритм. Для лучшего понимания работы алго-
ритма особые случаи подтверждены примерами.
Пусть
1
, ,
n
X x x
— множество булевых переменных и произ-
вольная булевой функции
n
f
задаeтся полиномом Жегалкина
n
F
в
базисе
G
3
(
n
— число переменных);
m
— длина полинома;
K
i
— моно-
тонная элементарная конъюнкция ранга
r
i
,
1,
i
m
. Вектор
