Рис. 1. Соединения блоков схем
S
0
(
а
) и
S
(
б
)
Блок
A
(блок
B
) реализует функции
K
t
(
e
x
)
,
0
≤
t
≤
2
r
−
1
(функции
K
j
(
e
y
)
,
0
≤
j
≤
2
n
−
r
−
1
), блок
C
, используя функции
K
t
(
e
x
)
, — все
функции
u
i,t
(
e
x
)
, блок
D
по представлению (1) с помощью функций
u
i,t
(
e
x
)
— функции
f
(
x
)
j
(
e
x
)
, блок
E
— конъюнкции функций, полученных
блоками
B
и
D
, блок
F
, используя функции
f
j
(
e
x,
e
y
)
, — функцию
f
(
e
x,
e
y
)
.
Приведем легко получаемые оценки сложностей блоков схемы
S
0
L
(
A
)
≤
2
r
+
r
2
]
r/
2[
,
L
(
B
)
≤
2
n
−
r
+(
n
−
r
)2
](
n
−
r
)
/
2[
,
L
(
E
) =
L
(
F
)
≤
2
n
−
r
,
L
(
C
)
≤
p
(2
s
+
s
2
]
s/
2[
)
и
L
(
D
)
≤
p
2
n
−
r
.
Отметим, что все блоки имеют линейную относительно суммы
чисел их входов и выходов сложность.
Далее через
log
n
обозначим
log
2
n
. Выбирая
r
= [2 log
n
]
и
s
= [
n
−
3 log
n
]
, получаем оценку
L
B
0
(
n
)
≤
L
(
S
0
)
≤
2
n
n
1 +
3 log
n
n
+
o
log
n
n
.
(2)
Нетрудно проверить, что сложность схемы
S
0
асимптотически рав-
на сложности блока
D
, состоящего из элементов, реализующих дизъ-
юнкцию.
Отметим, что
все
блоки схемы
S
0
не зависят от функции
f
(в
схеме, построенной по методу Лупанова, составляющие основную
сложность схемы блоки, реализующие функции
f
t,
2
i
(
e
x,
e
y
)
, строятся
по функции
f
). В схеме
S
0
функция
f
определяет только соединения
входов блока
D
с выходами блока
C
.
Перейдем теперь к реализации булевых функций схемами из функ-
циональных элементов в произвольном полном конечном булевом ба-
зисе
B
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 1 105
