УДК 519.714
Особенности автоматизации синтеза
булевых функций
© А. <...> К.Э. Циолковского, Москва, 121552, Россия
2
Изложен оригинальный подход к автоматическому синтезу дискретных устройств в базисе микросхем. <...> Методические установки этого подхода основываются на математическом и информационном описаниях булевых функций и их
структурно-функциональной декомпозиции. <...> Параллельная и последовательная декомпозиции по сложности (числу подформул) характеризуются одинаковым качеством, но по глубине лучшим качеством (меньшим или равным значением) обладает первая, поэтому для синтеза схем применена параллельная декомпозиция. <...> В частности, предложен вычислительный метод для нахождения оценок сложности реализации произвольных булевых функций в базисе Жегалкина на основе
параллельной декомпозиции. <...> Метод позволяет оценить возможность минимизации числа транзисторов и времени задержки схемы. <...> В данной работе применяется метод структурно-функциональной
декомпозиции булевых функций и схем из функциональных элементов [1–5]. <...> При использовании структурно-функциональной декомпозиции произвольной булевой функции, зависящей от любого конечного числа переменных, получены функционалы, позволяющие заранее подсчитывать показатели качества синтеза — число элементов и
глубину схемы [2, 3, 6, 7]. <...> Для автоматического нахождения оценки здесь приводится алгоритм, позволяющий это легко сделать [5, 10]. <...> Пусть X x1 , , xn — множество булевых переменных и произвольная булевой функции f n задаeтся полиномом Жегалкина F n в
базисе G3 (n — число переменных); m — длина полинома; Ki — монотонная элементарная конъюнкция ранга ri, i 1, m . <...> А.А. Гурченков, Е.К. Егорова
r r1 , , ri , , rm рангов полинома Жегалкина упорядочивается для
алгоритма один раз, отношением “ ≥”. <...> Полином Жегалкина F n представляется в виде табл. <...> Первые m строк и n
столбцов определяют полином Жегалкина, ( m 1 )-я строка применяется для указания числа повторений <...>