набор
a
1
a
2
. . . a
t
— это двоичная запись числа
m
. Столбец высотой
h
, являющийся двоичной записью числа
t
,
0
≤
t
≤
2
h
−
1
, назовем
(
h, t
)
-столбцом.
Функцию, у которой каждый столбец
i
-й полосы представляет со-
бой
(
s, t
)
-столбец,
0
≤
t
≤
2
s
−
1
, обозначим как
f
t
i
(
e
x
)
. Пусть
f
t,
1
i
(
e
x,
e
y
)
— функция, получающаяся из функции
f
i
(
e
x,
e
y
)
заменой всех
(
s, k
)
-
столбцов,
k
6
=
t
,
(
s,
0)
-столбцами.
Нетрудно проверить, что
f
i
(
e
x,
e
y
) =
2
s
−
1
[
t
=0
f
t,
1
i
(
e
x,
e
y
)
.
Рассмотрим реализацию функций
f
t,
1
i
(
e
x,
e
y
)
. Пусть
u
i,t
(
e
x
)
– функ-
ция, у которой все столбцы
i
-й полосы ее матрицы являются
(
s, t
)
-
столбцами, а все остальные строки нулевые. Функция
u
i,t
(
e
x
)
не за-
висит существенно от переменных
y
1
, y
2
, . . . , y
n
−
r
. Множество но-
меров столбцов полосы
M
f
i
, являющихся
(
s, t
)
-столбцами, —
J
f,i,t
.
Пусть
f
t,
2
i
(
e
x,
e
y
) =
S
j
2
J
f,i,t
K
j
(
e
y
)
. Если множество
J
f,i,t
пустое, то зна-
чение
f
t,
2
i
(
e
x,
e
y
)
полагаем равным нулю. Нетрудно проверить, что
f
t,
1
i
(
e
x,
e
y
) =
f
t,
2
i
(
e
x,
e
y
)
u
i,t
(
e
x
)
.
Опишем разработанную автором модификацию метода Лупанова.
Будем использовать следующее представление произвольной булевой
функции
f
:
f
(
e
x,
e
y
) =
2
n
−
r
−
1
[
j
=0
f
(
x
)
j
(
e
x
)
K
j
(
e
y
)
,
где
f
(
x
)
j
(
e
x
)
— функция, у которой все столбцы равны
j
-му столбцу
матрицы
M
f
.
Пусть
f
(
x
)
j,i
(
e
x
)
— функция, которая получается из функции
f
i
заменой всех столбцов ее
j
-м столбцом. Нетрудно проверить, что
f
(
x
)
j,i
(
e
x
) =
u
i,t
(
e
x
)
, где
t
— число, двоичной записью которого является
j
-й столбец полосы
M
f
i
. Нетрудно проверить, что
f
(
x
)
j
(
e
x
) =
p
[
i
=1
f
i,j
(
e
x
)
.
(1)
Схема, имеющая
s
входов и
t
выходов, называется
(
s, t
)
-схемой,
или
(
s, t
)
-блоком.
Реализующую произвольную функцию
f
схему
S
0
(в базисе
B
0
)
строим на основе представления (1). Такая схема состоит из
(
r,
2
r
)
-
блока
A
,
(
n
−
r
)
-блока
B
,
(2
r
,
(
p
−
1)2
s
+ 2
s
0
)
-блока
C
,
((
p
−
1)2
s
+
+ 2
s
0
,
2
n
−
r
)
-блока
D
,
(2
n
+1
−
r
,
2
n
−
r
)
-блока
E
и
(2
n
−
r
,
1)
-блока
F
. Соеди-
нения блоков схемы
S
0
приведены на рис. 1,
а
.
104 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1
