Особенности автоматизации синтеза булевых функций - page 2

А.А. Гурченков, Е.К. Егорова
2
 
1, , , ,i m r r r    r рангов полинома Жегалкина упорядочивается для
алгоритма один раз, отношением “ ≥”. Получаем 1 i m r r r   .
Полином Жегалкина  n F представляется в виде табл. 1 ( , i j K ) с чис-
лом строк ( 1 m  ) и числом столбцов ( 1 n  ). Первые m строк и n
столбцов определяют полином Жегалкина, ( 1 m  )-я строка применя-
ется для указания числа повторений букв в формуле и ( 1 n  )-й стол-
бец — для рангов элементарной конъюнкции (ЭК) i K . Если
  ,
j i x K то , 1,
i j K  иначе , 0
i j K  , 1, i m  , 1, j n  , где под симво-
лом  i K понимаем множество переменных, образующих ЭК i K .
Таблица 1
1 x … j x … n x r
1 K … … … … … 1 r
… … … … … … …
i K … … , 1
i j x  … … i r
… … … … … … …
m K … … … … … m r
p 1 p … j p … n p B L
Для элементарного симметричного полинома Жегалкина ( )n
i F
шаг декомпозиции определяется с помощью рекуррентного соотно-
шения
         
1 1
1 . n n n
n i i i F x F F  
  
Остаточные функции, рассматриваемые на множестве
 
\ j X X x  , в алгоритме будем записывать соответственно как
 1
1
n
i F F 
   и  1
1 . n
i F F 
  
В алгоритме используются следующие параметры: 1 1, 2, t   —
номер последней функции, записанной в табл. 2; 2 1, 2, t   — номер
последней прочитанной функции; max j j — индекс переменной j x
с максимальным числом j p повторений в табл. 1.
На основе множества рангов i r элементарных конъюнкций i K ,
1, i m  , выносим за скобки переменную j x c максимальным числом
повторений, при этом получается полином F ʹ длиной j p . Остаточные
формулы записываются в табл. 2.