ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 188
Скачиваний: 1
рис. 6.7.
Полный сумматор (FA), который использует перенос
c
(от предыдущего суммирования) и
складывает его с двумя битами (линиями)
a
и
b
, а кроме того, содержит дополнительную
d
с равным нулю битом на вхаде можно построить на основе четырех гейтов (рис. 6.8.)
рис. 6.8.
Помимо полной суммы трех битов
a
⊕
b
⊕
c
по модулю 2 и переноса бита в полном
сумматоре (рис. 6.8.) присутствуют еще два сообщения на линиях
a
и
b
. При этом
a
→
a
,
b
→
s
0
=
a
⊕
b
–
промежуточная сумма. Это обстоятельство является типичным для
организации логики вычислений на обратимых гейтах. Как видно, на выходе получается не
только то, что требовалось получить (
Sum
и перенос бита), но и определенное количество
промежуточной информации, которую принято называть "мусором". Наличие мусора в
таких цепях является проблемой, так как разрастание цепей до миллионов гейтов означает
необходимость хранения огромного количества ненужной информации и неэффективное
использование технологических элементов компьютера. Поэтому при организации процесса
вычисления на обратимых элементах необходимо еще решать задачу борьбы с мусором. В
конкретном случае, представленном на рис. 6.8., мусор может быть сведен в точности к тому,
что имеется на выходе, если к блоку FA добавить дополнительно CNOT на две верхние линии.
рис. 6.9.
57
Действительно, если
a
= 0
, то
s
0
=
a
⊕
b
=
b
и в соответствии с определением гейта CNOT
(т.к. линия
a
не активизирована)
b
00
=
b
. Во втором возможном случае
a
= 1
,
s
0
= 1
⊕
b
. При
этом:
s
0
=
(
1
,
если
b
= 0
0
,
если
b
= 1
.
(6.20)
В силу того, что линия
a
= 1
(активизирована), результат действия гейта CNOT на линии
b
≡
s
0
будет равен:
b
00
=
(
N OT s
0
= 0
,
если
b
= 0
N OT s
0
= 1
,
если
b
= 1
=
b.
(6.21)
Практически аналогично мусор может быть удален во всех иных схемах логических
цепей. В общем случае схема, представленная на рис. 6.9. может быть упрощена, но для
иллюстрации принципов это не существенно.
Таким образом, составляя различные цепи из комбинаций обратимых гейтов, можно
построить общий логический блок, который преобразует
n
-битов обратимым образом. Если
сама решаемая задача обратима, тогда может не быть мусорной информации, но в общем
случае необходимы дополнительные линии (или биты), которые требуются для обращения
выполняемой операции. В этом смысле мусор содержит информацию, необходимую для
обращения процесса вычисления.
Ранее (формула (6.17) и обратимость гейта CNOT) было показано, что гейт FANOUT
является обратимым. Очевидно, что гейт FANOUT не разрушает информацию, поэтому
возможна его обратимость.
Теперь
рассмотрим
операцию
ERASE,
которая,
как
кажется,
требуется
для
периодической "очистки" (обнуления) памяти компьютера. Интересно, что один тип стирания
может быть осуществлен обратимым образом. Действительно, если есть продублированная
копия некоторого бита, то можно стереть добавочную копию (или копию) путем операции
обратной FANOUT-гейту.
Проблема возникает, когда стирается имеющаяся последняя копия, в этом случае говорят
о так называемом примитивном стирании. К счастью гейт примитивный ERASE не является
абсолютно необходимым в вычислениях.
Действительно, вычисление произвольной функции
f
(
a
)
может быть воспроизведено
взаимно однозначным соответствием с ее агрументом в результате сохранения копии входных
данных
a
:
f
:
a
→
(
a, f
(
a
))
(6.22)
Процедура вычисления приводит к прямой проблеме из-за отсутствия примитивного
ERASE. Чем больше гейтов используется, тем больше мусорных битов накапливается, так
как в каждом гейте сохраняются входные биты для обеспечения обратимости. Таким образом,
компьютер, построенный из логически обратимых гейтов ведет себя следующим образом:
f
:
a
→
(
a, j
(
a
)
, f
(
a
))
,
(6.23)
где
j
(
a
)
–
большое число дополнительных мусорных битов.
58
Беннет решил эту проблему, путем стирания мусорных битов обратимым образом на
промежуточных шагах вычисления. Идея решения проблемы состоит в использовании
следующей процедуры:
1. На первом шаге вычисляется
f
и при этом получаются мусорные биты
j
(
a
)
и искомый
результат (6.23).
2. На втором шаге применяется FANOUT-гейт для дублирования выходного результата
f
(
a
)
в
f
c
(
a
)
F AN OU T
: (
a, j
(
a
)
, f
(
a
))
→
(
a, j
(
a
)
, f
(
a
)
, f
c
(
a
))
.
(6.24)
3. На третьем этапе выполняется операция обратная вычислению функции
f
f
−
1
: (
a, j
(
a
)
, f
(
a
)
, f
(
a
))
→
(
a, f
c
(
a
))
.
(6.25)
Обратная операция удаляет как мусорные биты, так и биты первоначально вычисленного
выходного результата
f
(
a
)
, не трогая при этом копию выходного результата
f
c
(
a
)
.
Таким образом, в памяти машины остается только набор начальных данных
a
и копия
набора битов вычисленной функции
f
(
a
)
. При этом использования примитивного ERASE не
потребовалось.
59