Background Image
Previous Page  3 / 16 Next Page
Information
Show Menu
Previous Page 3 / 16 Next Page
Page Background

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

вентиля. В таком случае входами обратимой схемы являются входы

первого вентиля, выходами – выходы последнего вентиля.

Базовое определение обратимых вентилей NOT и

k

-CNOT было да-

но в работе [4]. Напомним, что через

N

j

в работе [4] обозначен вентиль

NOT, инвертирующий значение на

j

-м входе; через

C

i

1

,...,i

k

;

j

=

C

I

;

j

вентиль

k

-CNOT (обобщенный элемент Тоффоли с

k

контролирующи-

ми входами), инвертирующий значение на

j

-м входе тогда и только то-

гда, когда значение на всех входах

i

1

, . . . , i

k

равно 1;

I

=

{

i

1

, . . . , i

k

}

множество контролирующих входов,

j /

I

.

Любая обратимая схема c

n >

3

входами, состоящая из вентилей

NOT, CNOT и 2-CNOT, задает какую-либо четную подстановку на

множестве

Z

n

2

. При этом такая схема может

реализовывать

некоторое

булево преобразование. Для того чтобы ввести определение обрати-

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

Z

m

2

Z

m

2

,

понадобятся отображения

ϕ

n,n

+

k

:

Z

n

2

Z

n

+

k

2

и

ψ

π

n

+

k,n

:

Z

n

+

k

2

Z

n

2

вида

ϕ

n,n

+

k

(

h

x

1

, . . . , x

n

i

) =

h

x

1

, . . . , x

n

,

0

, . . . ,

0

i

;

ψ

π

n

+

k,n

(

h

x

1

, . . . , x

n

+

k

i

) =

h

x

π

(1)

, . . . , x

π

(

n

)

i

, π

S

(

Z

n

+

k

)

.

Назовем

ϕ

n,n

+

k

расширяющим

отображением;

ψ

π

n

+

k,n

редуцирующим

отображением, подстановку

π

— перестановкой выходов.

Рассмотрим произвольную четную подстановку

h

A

(

Z

n

2

)

, кото-

рая задает булево преобразование

f

h

:

Z

n

2

Z

n

2

. Введем определения

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

f

h

либо без использо-

вания дополнительных входов, либо с использованием дополнитель-

ных входов.

Определение 1.

Обратимая схема

S

g

реализует преобразование

f

h

без использования дополнительных входов (дополнительной памя-

ти), если она имеет ровно

n

входов, при этом существует такая под-

становка

π

S

(

Z

n

)

, что задаваемое этой схемой булево преобразо-

вание

g

:

Z

n

2

Z

n

2

удовлетворяет условию

ψ

π

n,n

(

g

(x)) =

f

h

(x)

,

x

Z

n

2

.

Определение 2.

Обратимая схема

S

g

реализует преобразование

f

h

c использованием

k >

0

дополнительных входов (дополнитель-

ной памяти), если она имеет

n

+

k

входов, при этом существу-

ет такая подстановка

π

S

(

Z

n

+

k

)

, что задаваемое этой схемой

булево преобразование

g

:

Z

n

+

k

2

Z

n

+

k

2

удовлетворяет условию

ψ

π

n

+

k,n

(

g

(

ϕ

n,n

+

k

(x))) =

f

h

(x)

,

x

Z

n

2

.

Отметим, что обратимая схема

S

g

задает преобразование

f

h

при

g

(x) =

f

h

(x)

.

Напомним некоторые понятия из анализа [2]. Пусть

f

(

n

)

и

g

(

n

)

вещественные положительные функции натуральной переменной

n

,

тогда:

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