Особенности автоматизации синтеза булевых функций
3
Таблица 2
№
n
m
F
1
: –1
n n
:
j
m p
F
2
:
n n
:
m m m
F
…
…
…
…
В алгоритме используются следующие параметры:
t
1
= 1, 2, … —
номер последней функции, записанной в табл. 2;
t
2
= 1, 2, … — номер
последней прочитанной функции;
j = j
max
— индекс переменной
x
j
с
максимальным
числом
p
j
повторений в табл. 1. Если сразу несколько
переменных удовлетворяют этому условию, то, для сохранения упо-
рядоченности рангов, выбираем из них переменную с минимальными
индексами
i
и
j
.
Реализуемая формула
n
F
(и получаемые остаточные) в общем
случае разбивается на две более простые следующим образом:
1 ,1
1 , 2
max
.
n
n
n
j
F x F
F
На каждом шаге остаточные формулы за-
писываются в табл. 2, при этом значение
1
t
увеличивается на единицу
с каждой записанной формулой. На следующем шаге происходит
чтение формулы из строки с номером
2
t
, после чего значение
2
t
так-
же увеличивается на
1
. Алгоритм завершается, когда выполнится
условие
2 1
t t
. Таким образом, будут получены суперпозиционная
формула
n
F
и оценка числа подформул
n
F
L F N
, где
N
нахо-
дится в процессе работы алгоритма.
Шаг 1.
Подготовка начальных данных.
Вводится полином
n
F
, для него подсчитываются
n
,
m
,
B
L
. Со-
ставляется таблица, подсчитываются и упорядочиваются векторы
r
и
p
. Инициализируются переменные
1
0: ,
t
2
0: ,
t
0: .
N
Шаг 2.
Исходный полином записывается в таблицу. Счетчик за-
писи увеличивается на единицу:
1 1
1 :
.
t
t
Шаг 3
. Чтение из таблицы полинома с индексом
2
t
.
2
2
1 :
.
t
t
Шаг 4
. Проверка
1.
m
Если формула состоит только из одной конъюнкции
,
то
1
:
;
N N m
1 1
1 :
.
t
t
Переход к шагу 9.
