Прежде всего, отметим, что будет применен предложенный ав-
тором принцип использования не всюду определенных функций при
реализации всюду определенных функций. Не всюду определенную
функцию назовем
слабо определенной
, если число наборов, на кото-
рых она определена, не превосходит число ее переменных, увеличен-
ное на единицу. В изложенном ниже методе будут использованы слабо
определенные функции.
Пусть
G
0
,m
— множество всех не всюду определенных булевых
функций
m
переменных, сохраняющих константу 0 и равных единице
на наборах, имеющих одну единичную компоненту,
G
0
=
∞
[
m
=2
G
0
,m
.
В представлении (1) для любого набора
e
x
(определяющего номер
полосы
i
) значение не более одной из функций
f
i,j
(
e
x
)
,
0
≤
j
≤
p
,
равно единице. Вследствие этого при реализации булевых функций в
произвольном базисе будет использовано представление вида
f
(
e
x,
e
y
) =
2
n
−
r
−
1
[
j
=0
g
(
f
1
,j
(
e
x
)
, . . . , f
p,j
(
e
x
))
K
j
(
e
y
)
,
(3)
где
g
(
z
1
, . . . , z
p
)
2
G
0
.
Базис, приведенный вес которого равен единице, назовем
нормиро-
ванным
. Без ограничения общности рассмотрим нормированные бази-
сы. Отметим, что базис
B
0
— нормированный.
В случае произвольного базиса
B
схему
S
в этом базисе, реали-
зующую произвольную булеву функцию
f n
переменных, получим из
схемы
S
0
следующим образом.
Параметры
r
и
s
представления функции
f
выбираем такими же,
как и для базиса
B
0
. В блоках схемы
S
0
, отличных от блока
D
, элемен-
ты, реализующие конъюнкцию, дизъюнкцию и отрицание, заменим
схемами в базисе
B
, реализующими эти функции. При этом слож-
ность этих блоков увеличится не более чем в константу (зависящую
от базиса) раз. Блоки, полученные таким способом из блоков
A
,
B
,
C
,
E
,
F
, обозначим как
KX
,
KY
,
UX
,
CN
,
DS
. Блок
D
заменим блоками
BTB
и
LW
. Блок
LW
сформируем из элементов базиса
B
с минималь-
ным приведенным весом. Соединения блоков схема
S
приведены на
рис. 1,
б
.
Опишем блоки
LW
и
BTB
. Пусть
E
— имеющий минимальный
приведенный вес элемент базиса
B
, а
d
+1
— число входов элемента
E
.
Состоящую из
m
элементов
E
схему, в которой выход каждого
элемента присоединен к последнему входу следующего элемента, на-
зовем
E
m
-цепочкой, а последний (
(
d
+ 1)
-й) вход первого элемента
E
m
-цепочки —
стыковочным
. Вход
t
-го элемента
E
m
-цепочки с номе-
ром
i
полагаем
(
i
+ (
t
−
1)
d
)
-м входом этой цепочки. Блок
LW
состоит
из
2
n
−
r
E
]
p/d
[
-цепочек.
106 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1
