ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 187
Скачиваний: 1
Каскад полных сумматоров, позволяющий построить цепь для сложения двух 2-х битовых
целых
(
x
1
x
0
) + (
y
1
y
0
)
x
1
x
0
y
1
y
0
x
1
x
0
y
1
y
0
c
x
0
y
0
x
+
y
10-тичное
число
0
0
0
0
0
0
0
0
0
0
0
000
0
0
1
0
0
0
0
0
1
0
0
1
001
1
1
0
0
0
1
0
0
0
0
1
0
010
2
1
1
0
0
1
0
0
1
0
1
1
011
3
0
0
0
1
0
0
0
1
0
0
1
001
1
0
1
0
1
0
1
0
0
0
1
0
010
2
1
0
0
1
1
0
0
1
0
1
1
011
3
1
1
0
1
1
1
0
0
1
0
0
100
4
0
0
1
0
0
0
1
0
0
1
0
010
2
0
1
1
0
0
0
1
1
0
1
1
011
3
1
0
1
0
1
0
1
0
1
0
0
100
4
1
1
1
0
1
0
1
1
1
0
1
101
5
0
0
1
1
0
0
1
1
0
1
1
011
3
0
1
1
1
0
1
1
0
1
0
0
100
4
1
0
1
1
1
0
1
1
1
0
1
101
5
1
1
1
1
1
1
1
0
1
1
0
110
6
Каскад полных сумматоров позволяет построить цепь для сложения двух
n
-битовых
целых. Пример для
n
= 3
приведен на рисунке ниже.
Здесь два трехбитовых целых числа представлены в виде
x
=
x
2
x
1
x
0
и
y
=
y
2
y
1
y
0
.
Аналогично может быть построена цепь вычисления произвольной функции.
В классическом компьютере NOT и NAND-гейты осуществляются транзисторами,
например, как показано на рис. 6.1.
52
рис. 6.1.
Минимальная свободная энергия, которая расходуется на то чтобы работал идеальный
компьютер зависит от набора и числа примитивных элементов. Например, на гейте NAND,
выходящая линия
c
0
принимает одно из двух значений и при этом энтропия изменяется на
ln 2
единицы. Теоретический минимум количества теплоты, которое рассеивается в пространство
на одном элементарном шаге составляет
kT
ln 2
(здесь
k
–
постоянная Больцмана,
T
–
абсолютная температура). Фактически в реальных вычислительных устройствах происходит
диссипация энергии порядка
∼
10
10
kT
. Физически это связано с тем, что для изменения
потенциала (напряжения) проводника он сначала заземляется через сопротивление, а затем
через сопротивление заряжается.
Однако было установлено
, что предел
kT
ln 2
не является абсолютным, так как нет
необходимости использовать в вычислительном устройстве необратимые гейты. Оказалось,
что все операции, требующиеся для проведения вычислений могут быть проведены
обратимым образом, а следовательно без диссипации энергии (в соответствии с законами
термодинамики).
рис.6.2.
Классические компьютеры построены
на электрических цепях, содержащих
миллионы
транзисторов.
На
рисунке
6.2.
приведены
результаты
оценки
изменения числа примесей в основаниях
биполярных транзисторов, требующихся
для формирования логических операций
в
зависимости
от
времени
развития
полупроводниковых технологий.
По
сути
график
отражает
число
электронов, необходимых для хране-
ния
одного
бита
информации.
В
соответствии с этими данными ясно,
что технология достигает субатомные
расстояния и фактически переходит на
построение компьютеров на атомном
и молекулярном уровне, что приводит
к необходимости учета и включения
квантово-механических свойств вещества. Как будет показано ниже, на квантовых
компьютерах программы выполняются посредством организации унитарной эволюции
входных данных на квантовых объектах. А так как унитарные преобразования обратимы, то
цепь логических гейтов должна основываться на обратимых операциях.
1
R. Landaner. IBM. J.Res. Develop. 3, p.183 (1961)
2
R.W. Keyes. IBM. J.Res. Develop. 32, 24 (1988)
53
6.3
Обратимые логические гейты
Условием
обратимости
детерменированных
устройств
является
возможность
восстановления входных и выходных данных друг из друга единственным образом. Если
в дополнение к логической обратимости устройство может функционировать в обратном
направлении по времени, тогда оно называется физически обратимым и второй закон
термодинамики гарантирует, что оно не рассеивает теплоту.
При построении логических цепей с обратимыми логическими элементами можно
использовать три обратимых гейта
: NOT, CNOT, CCNOT, определение которых имеет
следующий вид:
а.
NOT-гейт
. Стандартный NOT-гейт, очевидно не теряет информации и является
обратимым. Обращение достигается повторным действием NOT-гейта.
б.
CNOT-гейт
(CNOT
≡
CONTROLLED NOT
≡
контролируемое "не").
Данный гейт определяется следующей диаграммой и таблицей истинности
рис. 6.3.
a
b
a
0
b
0
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
Гейт CNOT имеет две входящие линии
a
и
b
(два входных бита) и две выходящие линии
(две результирующих бита). Бит
a
0
всегда тот же, что и
a
, а соответствующая линия
называется контролирующей (или контрольной) линией. Если контролирующая линия
активирована (
a
= 1
), тогда выходной бит
b
0
есть NOT от
b
. В противном случае (
a
= 0
)
b
0
=
b
:
b
0
=
(
N OT b,
если
a
= 1
b,
если
a
= 0
.
(6.14)
Используя определение гейта CNOT видно, что:
–
действие данного гейта обращается простым повторением
рис. 6.4.
a
b
a
0
b
0
a
00
b
00
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
0
1
1
3
T. To
ff
oli. Math. Syst. Theory 14, 13-23, 1981
54
–
величина
b
0
является симметричной функцией
a
и
b
и является гейтом XOR
(исключающее или)
a
или
b
, но не оба. Данная операция является операцией
суммирования
a
и
b
по модулю 2, что символически можно записать в виде
XOR
: (
x, y
)
→
(
x, x
⊕
y
)
.
(6.15)
Соответственно символическое обозначение гейта CNOT допустимо писать в виде:
CN OT
: (
a, b
)
→
(
a, a
⊕
b
)
≡
(
a, XOR
: (
a, b
))
.
(6.16)
Подчеркнем также, что сам по себе гейт XOR не является обратимой логической
операцией, так как, например, если результирующее значение гейта XOR равно 0, то
нельзя определить из какого входного наборов битов
(
a, b
) = (0
,
0)
или
(
a, b
) = (1
,
1)
оно произошло.
Соответственно гейт CNOT сохраняет линию
a
=
a
0
, что и устраняет неопределенность
гейта XOR.
–
гейт CNOT обеспечивает гейт FANOUT, так как при
b
= 0
,
a
копируется на линию
b
0
.
F AN OU T
≡
;
или
F AN OU T
≡
CN OT
: (
a,
0)
.
(6.17)
Иногда функция копирования обозначается специальным символом COPY.
–
гейт CNOT обеспечивает гейт EXCHANGE (или SWAP)
EXCHAN GE
≡
в. Гейт CCNOT
≡
(CONTROLLED CONTROLLED NOT)
≡
(контролируемое
контролируемое "не"). Данный гейт определяется следующей диаграммой и таблицей
истинности:
рис. 6.5.
a
b
c
a
0
b
0
c
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
55
Гейт CCNOT
–
содержит три линии из которых две линии
a
и
b
являются контрольными
и остаются неизменными на выходе, а выход третьей линии
c
0
=
N OT c
, если обе
контрольные линии активированы (
a
=
b
= 1
), в противном случае
c
0
=
c
.
Из определения гейта CCNOT следует, что
–
если на входе третьей линии
c
= 0
, то
c
0
= 1
только при условии
a
= 1
и
b
= 1
, в
противном случае
a
= 0
или
b
= 0
или
a
=
b
= 0
на выходе третьей линии получим
c
0
= 0
. Таким образом в этом случае (
c
= 0
) гейт определяет (функцию) гейт AND, что
символически можно записать следующим образом:
CCN OT
: (
a, b,
0)
→
(
a, b, AN D
(
a, b
))
.
(6.18)
Три комбинации входных битов
(
a, b
)
, а именно
(0
,
0)
,
(0
,
1)
,
(1
,
0)
, приводят к одному
выходному биту логической функции AND
(
a, b
) = 0
. Следовательно для устранения
неоднозначности требуется помнить оба входных бита или иметь две контролируемые
линии.
Сохранение этих битов на линиях
a
,
b
на выходе позволяет обратить действие гейта.
–
повторное выполнение операции CCNOT обращает результат первой операции CCNOT
рис. 6.6.
a
b
c
a
0
b
0
c
0
a
00
b
00
c
00
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
Из определения CCNOT-гейта (или Тоффоли-гейта) видно, что выход этого гейта может
быть разложен в различные гейты
c
⊕
a
∧
b
=
a
∧
b,
для
c
= 0
(
AND-гейт
)
a
⊕
c,
для
b
= 1
(
XOR-гейт
)
c,
для
a
=
b
= 1
(
NOT-гейт
)
a,
для
b
= 1
, c
= 0
(
FANOUT-гейт
)
(6.19)
То есть данный гейт является универсальным, поскольку он выполняет AND, XOR, NOT и
FANOUT, в зависимости от того, что имеется на входе.
Комбинируя обратимые логические элементы можно составить любую логическую схему
и построить универсальный компьютер. Например, используя последовательность CCNOT и
CNOT можно составить полусумматор (HA) рис. 6.7.
56