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

Пусть

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