12 / 16
Пусть
m
= log
2
n
−
log
2
log
2
n
. При доказательстве требовалось,
чтобы
k
было степенью двойки. Пусть
k
= 2
b
log
2
m
c
, тогда
m/
2
6
k
6
m
и
L
(
h
)
.
2
n
+1
12
n
m/
2
+ 2
m
+1
= 2
n
+1
24
n
log
2
n
−
log
2
log
2
n
+
2
n
log
2
n
.
Отсюда следует, что
L
(
h
)
.
52
n
2
n
/
log
2
n
для всех
h
∈
A
(
Z
n
2
)
. Таким
образом,
L
(
n
)
.
52
n
2
n
/
log
2
n
.
I
Следствие 1.
При
k
= 4
верно соотношение
L
(
n
)
.
6
n
2
n
, что асим-
птотически меньше, чем оценка (3), предложенная в работе [7].
Объединяя верхнюю и нижнюю оценки
L
(
n
)
можно сформулиро-
вать основную теорему настоящей работы.
Теорема 3.
L
(
n
)
n
2
n
/
log
2
n
.
J
Следует из теорем 1 и 2.
I
Снижение вентильной сложности при использовании дополни-
тельных входов.
В работе [3] доказано, что для любого булева пре-
образования
f
:
Z
n
2
→
Z
n
2
можно построить реализующую его схему,
состоящую из функциональных элементов базиса
{¬
,
∧
,
∨}
и имею-
щую вентильную сложность
O
(2
m
/m
)
, где
m
=
n
+log
2
n
. Такая схема
включает в себя в качестве подсхемы многополюсник, вычисляющий
все булевы функции
n
−
k
переменных. В доказательстве использо-
вано следующее представление преобразования
f
(аналог разложения
булевой функции по
k
переменным):
f
(
h
x
1
, . . . , x
n
i
) =
∨
a
1
,...,a
k
∈
Z
2
x
a
1
1
∧
. . .
∧
x
a
k
k
∧
f
(
h
a
1
, . . . , a
k
, x
k
+1
, . . . , x
n
i
)
.
Используя аналогичный подход, докажем, что верхняя оценка вен-
тильной сложности обратимых схем может быть снижена с помо-
щью дополнительных входов. Напомним, что величина
L
∗
(
n
)
соот-
ветствует максимальной вентильной сложности обратимой схемы из
всех минимальных обратимых схем, реализующих четную подстанов-
ку
h
∈
A
(
Z
n
2
)
с применением дополнительных входов.
Теорема 4
.
При
N
∼
5
∙
2
n
/n
дополнительных входах в схеме, со-
стоящей из вентилей множества
Ω
2
n
+
N
, справедливо соотношение
L
∗
(
n
)
.
2
n
+1
.
J
Покажем, что
L
∗
(
h
)
.
2
n
+1
для всех
h
∈
A
(
Z
n
2
)
. Любая подстанов-
ка
h
∈
A
(
Z
n
2
)
задает некоторое булево преобразование
f
h
:
Z
n
2
→
Z
n
2
.
Представим его следующим образом:
f
h
(
h
x
1
, . . . , x
n
i
) =
⊕
a
1
,...,a
k
∈
Z
2
x
a
1
1
∧
. . .
∧
x
a
k
k
∧
f
h
(
h
a
1
, . . . , a
k
, x
k
+1
, . . . , x
n
i
)
.
(10)
Преобразование
f
h
(
h
a
1
, . . . , a
k
, x
k
+1
, . . . , x
n
i
)
соответствует какому-
либо булеву преобразованию
n
−
k
переменных.
Построим многополюсник, вычисляющий все булевы функции
n
−
k
переменных. Обозначим через
Ω
NXA
множество функцио-
нальных элементов
{¬
,
⊕
,
∧}
(NXA – NOT, XOR, AND). Множество
78 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1