4
А.А. Гурченков, Е.К. Егорова
Шаг 5. Теперь применим ФУ (1) и определим первую остаточную
функцию
F
′ =
F
1
. По
x
i
в матрице
K
нужно выбрать номера ЭК, содер-
жащие переменную
x
j
max
, число которых равно
p
j
max
, и сложить (вирту-
ально) эти ЭК, исключая переменную
x
j
max
, по модулю 2. Фактически
переписываем ЭК из одной матрицы в другую, сохраняя порядок и ис-
ключая переменную
x
j
max
. Получаем полином Жегалкина
F
′(
F
1
), а так-
же подсчитываем векторы
r
и
p
. После этого вычисляем
n
′ =
n
– 1 —
число переменных полинома Жегалкина
F
′,
m
=
p
j
— длину полинома
Жегалкина
F
′ и увеличиваем
t
1
:
t
1
=
t
1
+ 1. В строку с номером
t
1
табл. 1
запишем
n
′,
m
′,
F
′.
Теперь необходимо определить вторую остаточную функцию
F
′′ =
F
2
полинома Жегалкина из табл. 1. Для этого из матрицы
K
вы-
берем номера ЭК, не содержащие переменную
x
j
max
, и сложим (вирту-
ально) эти ЭК по модулю 2. Подсчитываем векторы
r
и
p
и получаем
полином Жегалкина
F
′′. Далее вычисляем
n
′′ =
n
′ — число переменных
полинома Жегалкина
F
′′,
m′′
=
m
–
m′
=
m
–
p
j
— длину полинома Же-
галкина
F
′′ и увеличиваем
t
1
:
t
1
=
t
1
+ 1. В строку с номером
t
1
табл. 2
пишем
n
′′,
m
′′,
F
′′.
Шаг 6. Чтение.
Вычисляем
t
2
=
t
2
+ 1. И из табл. 1 считываем по адресу
t
2
поли-
ном
F
, с которым продолжим работу. Ранее в эту таблицу были за-
писаны остаточные полиномы, получившиеся при текущем проходе
алгоритма. Таким образом, будем продолжать, пока записи в таблице
не закончатся.
Увеличиваем значение
3
,
1.
n
F
F
L F G L
Шаг 7. Если
t
2
≤
t
1
, переходим к шагу 2. В ином случае завершаем
работу алгоритма.
В результате получаем верхнюю оценку сложности (
L
F
) заданной
в виде полинома Жегалкина логической функции.
Каждую из записей в табл. 2 можно обрабатывать независимо друг
от друга. Это позволяет параллельно обрабатывать несколько функ-
ций одновременно, что положительно сказывается на скорости работы
алгоритма.
3. Примеры работы алгоритма.
Разберем алгоритм на основе сле-
дующего примера:
3
1 2 3
1 4
5
.
F x x x x x x
Для начала представим данный полином в виде следующей матри-
цы (табл. 2):
