Перейдем к описанию блока
BTB
(блок настройки на базис) и пока-
жем, что его сложность линейна относительно числа его входов. Если
функция, реализуемая элементом
E
, принадлежит множеству
G
0
, то
блок
BTB
не потребуется.
Блок
BTB
позволяет функции, реализуемые
E
]
p/d
[
-цепочками блока
LW
, преобразовать в функции из множества
G
0
.
Функцию
u
i,
2
s
−
1
(
e
x
)
будем называть
характеристической функцией
i
полосы. Если
s
0
6
=
s
, то характеристическая функция
p
-й полосы
определяется как
u
i,m
(
e
x
)
, где
m
= 2
s
0
−
1
.
Через
i
t
обозначим номер полосы матрицы
M
f
, содержащей стро-
ку с номером
t
. Нетрудно проверить, что для любого
t
при
e
x
=
X
t
значение одной характеристической функции (полосы с номером
i
t
)
равно единице, а значения всех функций
f
i,j
(
e
x
)
, i
6
=
i
t
,
— нулю.
Для рассмотрения общего случая опишем несколько вспомогатель-
ных блоков. Под знаком “ ” будем понимать булеву операцию сложе-
ния по модулю два. Пусть
MD
— это
(2
,
1)
-блок, реализующий функ-
цию
x
1
x
2
,
MOD
m
—
(
m
+ 1
, m
)
-блок, состоящий из
m
блоков
MD
,
выходы (первые входы) которых являются его выходами (входами).
Вторые входы блоков
MD
соединены между собой и с
(
m
+ 1)
-м вхо-
дом блока
MOD
m
. Этот вход будем называть управляющим. Отметим,
что блок
MOD
1
является блоком
MD
.
Функция
h
, реализуемая элементом
E
, существенно зависит от
всех своих переменных, т.е. для
8
i
,
1
≤
i
≤
d
+ 1
,
существует такой
набор
a
1
,i
, a
2
,i
, . . . , a
d
+1
,i
, что
h
(
a
1
,i
, . . . , a
i
−
1
,i
, x
i
, a
i
+1
,i
, . . . , a
d
+1
,i
) =
x
i
a
i,i
.
(4)
Переменную
x
i
булевой функции назовем
прямой
, если существу-
ет представление вида (4), в котором
a
i,i
= 0
. Сначала рассмотрим
случай, когда
(
d
+ 1)
-я переменная функции
h
является прямой:
h
(
a
1
,d
+1
, . . . , a
d,d
+1
, x
d
+1
) =
x
d
+1
.
Двоичный набор длиной
m
, в котором единственная единичная
компонента имеет номер
k
(все компоненты равны нулю), обозначим
как
b
m,k
(через
0
m
).
Пусть
CB
—
(
d, d
)
-блок, который на наборе
b
d,i
,
1
≤
i
≤
d
, выдает
набор
a
1
,i
, a
2
,i
, . . . , a
i,d
, а на наборе
0
d
— набор
a
1
,d
+1
, a
2
,d
+1
, . . . , a
d,d
+1
;
IB
—
(
d,
1)
-блок, значение выхода которого на наборе
b
d,i
,
1
≤
i
≤
d
,
(наборе
0
d
) равно
a
d
+1
,i
(
a
d
+1
,d
+1
);
S
1
—
(2
d
+ 1
,
1)
-схема, состоящая
из элемента
E
, блока
CB
, блока
IB
и
d
+ 1
блоков
MD
. Соединения
элементов схемы
S
1
приведены на рис. 2,
а
.
Входы схемы
S
1
, представляющие собой входы блока
CB
(первых
d
блоков
MD
,
(
d
+ 1)
-го блока
MD
), назовем управляющими (инфор-
мационными, стыковочным). Нетрудно проверить, что
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1 107
