ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 101
Скачиваний: 1
Семинар 6. Общие принципы вычислений
6.1 Основные понятия алгебры логики
Алгебра логики — раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических (истина или ложь) значений, и логические операции над ними.
Алгебралогикивозниклавсередине19векавработахДж.БуляибыларазвитаЧ.Пирсом
(C.S. Peirs),П.С.Порецким,Б.Расселом(B.Russel),Д.Гильбертом(D.Hilbert)идр.
Высказываниемназываютсяпредложения,которыемогутбытьохарактеризованыпонятием—истинаилиложь.Использованиелогическихсвязок"и","или","если...то","эквивалентно",частица"не"ит.д.позволяетстроитьновые,болеесложные,высказыванияиззаданных.Истинностьилиложностьсложныхвысказыванийзависитотистинностиилиложностиисходныхвысказываний.Дляобозначенияистинностивводятсятождественныесимволы:
Истина ≡ И ≡ True ≡ T ≡ 1. (6.1)
Для обозначения ложности высказывания вводятся следующие тождественные символы
Ложь ≡ Л ≡ False ≡ F ≡ 0. (6.2)
Соответственно для логических связок приняты следующие обозначения:
"и"(конъюнкция) ≡ & ≡∧≡ AND ≡∩"или"(дизъюнкция) ≡∨≡ OR"если...то"(импликация)≡→"эквивалентность" ≡∼
"отрицание"
≡
черта
над высказыванием ≡¬≡
NOT
⎫
⎬
(6.3)
Связкиичастицы"не"рассматриваютсявалгебрелогикикакоперациинадвеличинами,принимающиедвазначения0и1,авысказыванияспроизвольнымивысказываниямиисвязкамиобразуютформулы.Приэтомвысказывания,образующиеформулу,рассматриваютсявкачествепеременных,асвязкивкачествефункций.ФормулыAиBназываютсяравными(A=B),еслиониреализуютравныефункции.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для задания функций алгебры логики, используются таблицы, содержащие все наборы значений переменных и значений функций: такие таблицы называются таблицами истинности. Пример таблицы истинности для NOT, AND, OR, импликации и эквивалентности приведены ниже |
a
b
NOT a
a ∧ b
a ∨ b
a → b
a ∼ b
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1
Сложные формулы в алгебре логики могут быть преобразованы. Для преобразования формул основную роль играют следующие законы:
– закон коммутативности
a ∨ b = b ∨ a; a ∧ b = b ∧ a; (6.4)
– закон ассоциативности
(a ∧ b) ∧ c = a ∧ (b ∧ c);(a∨ b) ∨ c = a ∨ (b ∨ c);(6.5)
– закон поглощения
a ∧ (a ∨ b)=a;a∨ (a ∧ b)=a;(6.6)
– закон дистрибутивности
a ∧ (b ∨ c)=(a∧ b) ∨ (a ∧ z);a∨ (b ∧ c)=(a∨ b) ∧ (a ∨ c);(6.7)
– закон противоречия
a ∧ a = 0; (6.8)
– закон исключения третьего
a ∨ a = 1; (6.9)
a → b = a ∨ b; a ∼ b =(a ∧ b) ∨ (a ∧ b) (6.10)
Множество всех формул, в построении которых учавствуют переменные высказывания, символы ∧, ∨, →, ∼, ¬, константы 0 и 1 называются языком над данными символами. Равенство (6.4)–(6.10) означают, что для всякой формулы в языке над ∧, ∨, →, ∼, ¬, 0, 1 найдется равная ей формула в языке над ∧, ∨,,0,1.
¬
Алгебралогикиразвиваласьподвлияниемприкладныхзадач,средикоторыхприложениектеорииэлектрическихсхемиграетсамоеважноезначение.Валгебрелогикиставитсязадачаминимизациифункцииприводязаданнуюфункциюкфункцииимеющейнаименьшеечислосомножителей,тоестьминимальнуюсложность.Такиефункцииназываютсяминимальными.
Вязыкенад ∧, ∨, →, ∼, 0, 1, ⊕,где ⊕ – используетсядляобозначениясложенияпомодулю 2 устанавливаются следующие соотношения:
a ∨ b = ((a ∧ b)+a)+b(6.11)a→ b = a ∧ b; a ∼ b=(a+b)+1;(6.12)a+b=(a∧ b) ∨ (a ∧ b);1=a∨ a. (6.13)
6.2 Классические универсальные машины и логические гейты
Универсальный компьютер — это логическое устройство, реализованное в виде сложной сети взаимосвязанных примитивных (основных) элементов. Для классического компьютера можно представить, что взаимосвязь элементов осуществляется идеальными проводниками, передающими одно из двух стандартных напряжений, представляющих локально один бит информации — 1 или 0. Сами примитивные элементы — или гейты реализуют функции преобразования, использующиеся в алгебре логики.
Классическийкомпьютеросуществляетвычислениефункцийпозаданнымвходнымn-битам,располагаярезультатвычислениявm-битах.Функциясm-битамизначенийэквивалентнаm-функциям,каждаяизкоторыхимеетоднобитовоезначениевкачестверезультата.Вычислениекаждойизэтихфункцийможетбытьсведенокпоследовательностиэлементарныхлогическийопераций(гейтов).
Символически гейты и биты, "соединенные проводами", изображаются рисунками.
Так на рисунке представлен примитивный элемент сети, в которой над битом выполняется логическая операция отрицания (NOT)
Нарисункеуказано,чтобитaпроходитчерезгейтNOT,которыйпереворачиваетбит,превращая1в0и0в1.ЛиниидоипослегейтаNOTслужатдляпереносабитакгейтуиудалениеегопослепреобразования.Данныелинии(провода)могутпредставлятькакпереносбитаизоднойточкипространствавдругую,такиразвитиесостояниябитавовремени.ГейтNOTимеетодинвходнойбитиодинбитнавыходе.Фактически,выходнойбитвычисляетфункциюf(a)=1⊕ a.
При построении сети предполагается, что сеть не содержит замкнутых петель.
|
|
|
|
||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Имеетсямногоиныхэлементарныхлогическихгейтов,полезныхдляорганизациипроцессавычисления,которыеимеютдвабитавкачествеисходныхданныхиодинрезультирующийбит.Геометрическиеизображения,алгебраическиеформулывбинарнойарифметикеитаблицыистинности,которыхприведеныниже |
a
b
c
0
0
0
;
c ≡ a ∧ b = a · b
0 1
1 0
0 0
1
1
1
|
|
|
|
||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
б. OR-гейт |
a
b
c
0
0
0
;
c ≡ a ∨ b = a + b − a · b
0 1
1 0
1 1
1
1
1
в.
XOR-гейт
(исключающее или ≡
"или",
но не оба)
ab
00
; c ≡ aXORb=a(1− b)+b(1− a) 01
10 11
г.
NAND-гейт
≡
(NOT
AND-гейт)
ab
00 ; c =1 − ab 01
·
10
11 д. NOR-гейт
≡
(NOT
OR-гейт)
ab
00
; c = (1 − a)(1− b) 01 10 11
0 1 1 0
c
1 1 1 0
c
1 0 0 0
Любоевычислениеможетбытьзаписановтерминахбулевскоговыражения,илюбоебулевскоевыражениеможетбытьпостроеноизфиксированногонаборалогическихгейтов.Такойнабор(например,AND,ORилиNOT)называетсяуниверсальным.Вдействительностиможнообойтисьтолькодвумягейтами,такимикакANDиNOT,илиORиNOT,илиANDиXOR.Устройство,котороеможетисполнитьпроизвольныекомбинациилогическихгейтовизуниверсальногонабора,являетсяуниверсальнымкомпьютером.
Хотяприведенныевышегейтыдостаточныдляматематическогоаппаратаалгебрылогики,онинедостаточныдляреализациипрактическойвычислительноймашины.ВреальномустройстветребуютсяещедвагейтаFANOUT(разворачивание)иERASE(стирание).
FANOUT-гейтдублируетвходнойбит,агейтERASE–уничтожаетвходнойбит.ПосутиFANOUT-гейттребуетсядляорганизациивычислений,аERASEдляочисткиячеекпамятикомпьютера.
|
|
|
|
||||||||||
|
|
||||||||||||
|
|
|
|
a 0 0 1 1
b
0 1 0 1
50
a�
b�
0
0
1
0
0
1
1
1
Для примера рассмотрим цепь, которая суммирует два целых числа, имеющих длину nбит. Базовым элементом в этой цепи является "ячейка" сети известная как полусумматор (half-adder ≡ HA). На вход полусумматора подаются два бита x и y, а на выходе получается сумма битов x ⊕ y по модулю 2 и перенос (carry) бита в состоянии 1, если x и y оба 1, или 0 во всех остальных случаях.
Схема сети полусумматора имеет вид:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица
истинности полусумматора: |
x
y
0
0
0
1
1
0
1
1
перенос
0
0
0
1
x ⊕ y
0 1 1 0
двоичное
число
00 01 01 10
Перенос бита позволяет перейти на следующий разряд, если складывается 1+1=0. Каскад из 2-х полусумматоров (HA) образует полный сумматор (full-adder ≡ FA)
Полныйсумматоримееттрибитанавходе,гдеx,y–данныедлясложения,c–переносбитаспредыдущегоэтапавычисленийидвабитанавыходе.Одинвыходнойбитявляетсясуммойпомодулю2x⊕ y ⊕ cвсехтрехвходящихбитов,авторойвыходнойбитc�–естьпереносбита,которыйравен1,еслидваилибольшевходныхбитаравны1,иравен0впротивномслучае.
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
x
y
c
x
y
c
x
y
c
перенос
x ⊕ y ⊕ c
число
0 0 1 1
0 1 0 1
0 0 0 0
0 0 0 1
0 1 1 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 1 0
0 0 0 1
0 1 1 0
00 01 01 10
0 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
0 1 1 0
1 1 1 1
0 0 0 1
0 1 1 0
1 0 0 1
0 1 1 1
1 0 0 1
01 10 10 11
x1
x0
y1
y0
x1
x0
y1
y0
c
x0
y0
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=x2x1x0иy=y2y1y0.Аналогичноможетбытьпостроенацепьвычисленияпроизвольнойфункции.
В классическом компьютере NOT и NAND-гейты осуществляются транзисторами, например, как показано на рис. 6.1.
рис. 6.1.
Минимальнаясвободнаяэнергия,котораярасходуетсянаточтобыработалидеальныйкомпьютерзависитотнабораичислапримитивныхэлементов.Например,нагейтеNAND,выходящаялинияc�принимаетодноиздвухзначенийиприэтомэнтропияизменяетсянаln2единицы.Теоретическийминимумколичестватеплоты,котороерассеиваетсявпространствонаодномэлементарномшагесоставляетkTln2(здесьk–постояннаяБольцмана,T–абсолютнаятемпература).Фактическивреальныхвычислительныхустройствахпроисходитдиссипацияэнергиипорядка∼ 1010 kT . Физически это связано с тем, что для изменения потенциала (напряжения) проводника он сначала заземляется через сопротивление, а затем через сопротивление заряжается.
Однако было установлено1, что предел kT ln2 не является абсолютным, так как нет необходимости использовать в вычислительном устройстве необратимые гейты. Оказалось, что все операции, требующиеся для проведения вычислений могут быть проведены обратимым образом, а следовательно без диссипации энергии (в соответствии с законами термодинамики).
Классические компьютеры построены на электрических цепях, содержащих миллионы транзисторов. На рисунке
6.2.
приведены результаты2
оценки
изменения числа примесей в основаниях
биполярных транзисторов, требующихся
для формирования логических операций
в зависимости от времени развития
полупроводниковых технологий.
По сути график отражает число электронов, необходимых для хранения одного бита информации. В соответствии с этими данными ясно, что технология достигает субатомные расстояния и фактически переходит на построение компьютеров на атомном и молекулярном уровне, что приводит к необходимости учета и включения
квантово-механических свойств вещества. Как будет показано ниже, на квантовых компьютерах программы выполняются посредством организации унитарной эволюции входных данных на квантовых объектах. А так как унитарные преобразования обратимы, то цепь логических гейтов должна основываться на обратимых операциях.
1R.
Landaner. IBM. J.Res. Develop. 3, p.183 (1961)
2R.W.
Keyes. IBM. J.Res. Develop. 32, 24 (1988)
6.3 Обратимые логические гейты
Условием обратимости детерменированных устройств является возможность восстановления входных и выходных данных друг из друга единственным образом. Если в дополнение к логической обратимости устройство может функционировать в обратном направлении по времени, тогда оно называется физически обратимым и второй закон термодинамики гарантирует, что оно не рассеивает теплоту.
При построении логических цепей с обратимыми логическими элементами можно использовать три обратимых гейта 3: NOT, CNOT, CCNOT, определение которых имеет следующий вид:
а. NOT-гейт. Стандартный NOT-гейт, очевидно не теряет информации и является обратимым. Обращение достигается повторным действием NOT-гейта.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
б. CNOT-гейт
(CNOT ≡
CONTROLLED
NOT ≡
контролируемое
"не"). |
a
b
a�
b�
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
ГейтCNOTимеетдвевходящиелинииaиb(двавходныхбита)идвевыходящиелинии(дверезультирующихбита).Битa�всегдатотже,чтоиa,асоответствующаялинияназываетсяконтролирующей(иликонтрольной)линией.Есликонтролирующаялинияактивирована(a=1),тогдавыходнойбитb�естьNOTотb.Впротивномслучае(a=0)b�=b:
NOT b, если a =1
b� = (6.14)
b, если a =0.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Используя определение гейта CNOT видно, что: |
– действие данного гейта обращается простым повторением
– величина b� является симметричной функцией a и b и является гейтом XOR (исключающее или) a или b, но не оба. Данная операция является операцией суммирования a и b по модулю 2, что символически можно записать в виде
a
b
a�
b�
a��
b��
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
0
1
1
54
XOR:(x,y)→ (x,x⊕ y).(6.15)
Соответственно символическое обозначение гейта CNOT допустимо писать в виде:
CNOT:(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�,чтоиустраняетнеопределенностьгейтаXOR.
– гейтCNOTобеспечиваетгейтFANOUT,таккакприb=0,aкопируетсяналиниюb�.
FANOUT
;
или FANOUT ≡
CNOT:(a,0).(6.17)
≡
Иногда функция копирования обозначается специальным символом COPY.
– гейтCNOTобеспечиваетгейтEXCHANGE(илиSWAP)
в. Гейт CCNOT (CONTROLLED CONTROLLED NOT) (контролируемое
≡ ≡
контролируемое "не"). Данный гейт определяется следующей диаграммой и таблицей истинности:
abc a� b� c�
000
000001
001010
010011
011100
100101
101110
111111
110 ГейтCCNOT–содержиттрилинииизкоторыхдвелинииaиbявляютсяконтрольнымииостаютсянеизменныминавыходе,авыходтретьейлинииc�=NOTc,еслиобеконтрольныелинииактивированы(a=b=1),впротивномслучаеc�=c.
Из определения гейта CCNOT следует, что
– еслинавходетретьейлинииc=0,тоc�=1толькоприусловииa=1иb=1,впротивномслучаеa=0илиb=0илиa=b=0навыходетретьейлинииполучимc�=0.Такимобразомвэтомслучае(c=0)гейтопределяет(функцию)гейтAND,чтосимволическиможнозаписатьследующимобразом:
CCNOT:(a,b,0)(a,b,AND(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�
b�
c�
a��
b��
c��
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-гейт)(6.19)
c,дляa=b=1(NOT-гейт)a,дляb=1,c=0(FANOUT-гейт)
Тоестьданныйгейтявляетсяуниверсальным,посколькуонвыполняетAND,XOR,NOTиFANOUT,взависимостиоттого,чтоимеетсянавходе.
Комбинируя обратимые логические элементы можно составить любую логическую схему и построить универсальный компьютер. Например, используя последовательность CCNOT и CNOT можно составить полусумматор (HA) рис. 6.7.
рис. 6.7.
Полныйсумматор(FA),которыйиспользуетпереносc(отпредыдущегосуммирования)искладываетегосдвумябитами(линиями)aиb,акрометого,содержитдополнительнуюdсравнымнулюбитомнавхадеможнопостроитьнаосновечетырехгейтов(рис.6.8.)
рис. 6.8.
Помимо полной суммы трех битов a ⊕ b ⊕ cпомодулю2ипереносабитавполномсумматоре(рис.6.8.)присутствуютещедвасообщенияналинияхaиb.Приэтомaa,
→
b → s� = a ⊕ b–промежуточнаясумма.Этообстоятельствоявляетсятипичнымдляорганизациилогикивычисленийнаобратимыхгейтах.Каквидно,навыходеполучаетсянетолькото,чтотребовалосьполучить(Sumипереносбита),ноиопределенноеколичествопромежуточнойинформации,которуюпринятоназывать"мусором".Наличиемусоравтакихцепяхявляетсяпроблемой,таккакразрастаниецепейдомиллионовгейтовозначаетнеобходимостьхраненияогромногоколичестваненужнойинформацииинеэффективноеиспользованиетехнологическихэлементовкомпьютера.Поэтомуприорганизациипроцессавычислениянаобратимыхэлементахнеобходимоещерешатьзадачуборьбысмусором.Вконкретномслучае,представленномнарис.6.8.,мусорможетбытьсведенвточностиктому,чтоимеетсянавыходе,есликблокуFAдобавитьдополнительноCNOTнадвеверхниелинии.
Действительно, если a =0, то s� = a ⊕ b = b и в соответствии с определением гейта CNOT (т.к. линия a не активизирована) b�� = b. Во втором возможном случае a =1, s� =1 ⊕ b. При этом:
1, если b =0
s� = (6.20)
0, если b =1.
В силу того, что линия a =1 (активизирована), результат действия гейта CNOT на линии b ≡ s� будет равен:
b�� = NOTs�=0,еслиb=0= b. (6.21)
NOTs�=1,еслиb=1
Практически аналогично мусор может быть удален во всех иных схемах логических цепей. В общем случае схема, представленная на рис. 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)–большоечислодополнительныхмусорныхбитов.
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
Беннет решил эту проблему, путем стирания мусорных битов обратимым образом на промежуточных шагах вычисления. Идея решения проблемы состоит в использовании следующей процедуры: |
||
Напервомшагевычисляетсяfиприэтомполучаютсямусорныебитыj(a)иискомыйрезультат (6.23).
НавторомшагеприменяетсяFANOUT-гейтдлядублированиявыходногорезультата
f(a)вfc(a)
FANOUT:(a,j(a),f(a))→(a,j(a),f(a),fc(a)).
(6.24)
3. На третьем этапе выполняется операция обратная вычислению функции f
f−1:(a,j(a),f(a),f(a))→(a,fc(a)).
(6.25)
Обратнаяоперацияудаляеткакмусорныебиты,такибитыпервоначальновычисленноговыходногорезультатаf(a),нетрогаяприэтомкопиювыходногорезультатаfc(a).
Такимобразом,впамятимашиныостаетсятольконаборначальныхданныхaикопиянаборабитоввычисленнойфункцииf(a).ПриэтомиспользованияпримитивногоERASEнепотребовалось
.