Background Image
 1 / 16 Next Page
Information
Show Menu
1 / 16 Next Page
Page Background

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

ИНФОРМАТИКИ

УДК 004.312, 519.7

ВЕНТИЛЬНАЯ СЛОЖНОСТЬ ОБРАТИМЫХ СХЕМ

КАК МЕРА СЛОЖНОСТИ ЧЕТНЫХ ПОДСТАНОВОК

Д.В. Закаблуков

МГТУ им. Н.Э. Баумана, Москва, Российская Федерация

e-mail:

dmitriy.zakablukov@gmail.com

Рассмотрен вопрос сложности четных подстановок через оценку вентильной

сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT

и 2-CNOT. Доказано, что все четные подстановки на множестве

Z

n

2

задают-

ся обратимой схемой, не использующей дополнительные входы, с вентильной

сложностью, эквивалентной с точность до порядка

n

2

n

/

log

2

n

; оставшиеся

четные подстановки задаются обратимой схемой, не использующей дополни-

тельные входы, с меньшей вентильной сложностью. Установлено, что любая

четная подстановка на множестве

Z

n

2

реализуется обратимой схемой с вен-

тильной сложностью

.

2

n

+1

при использовании

5

2

n

/n

дополнительных

входов. Для всех четных подстановок применение дополнительных входов по-

зволяет снизить вентильную сложность реализующих их обратимых схем.

Ключевые слова

:

обратимые схемы, вентильная сложность, сложность четных

подстановок.

GATE COMPLEXITY OF REVERSIBLE CIRCUITS AS A MEASURE

OF EVEN PERMUTATION COMPLEXITY

D.V. Zakablukov

Bauman Moscow State Technical University, Moscow, Russian Federation

e-mail:

dmitriy.zakablukov@gmail.com

The article discusses even permutation complexities via the evaluation of the gate

complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates, which

implements these permutations. It is proved that almost every even permutation on

the

Z

n

2

set is implemented by the reversible circuit not using additional inputs with

the gate complexity equivalent up to about

n

2

n

/

log

2

n

; all other even permutations

are implemented by reversible circuit not using additional inputs with the less gate

complexity. It is established that every even permutation on the

Z

n

2

set is implemented

by the reversible circuit using

5

2

n

/n

additional inputs with the gate complexity

.

2

n

+1

. It is stated that for almost every even permutations the usage of additional

inputs allows to decrease gate complexity of reversible circuits implementing them.

Keywords

:

reversible circuits, gate complexity, even permutation complexity.

Введение.

В дискретной математике для оценки сложности того

или иного преобразования вводится мера сложности этого преобразо-

вания. В качестве меры сложности булевой функции зачастую рассма-

тривают вентильную сложность минимальной схемы, задающей эту

функцию. Впервые это было предложено К. Шенноном в работе [1],

с которой берет свое начало теория схемной сложности. В настоящее

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 67