Полный текст

Введение. Квантовые компьютеры, квантовая логика уже настойчиво стучатся в наши двери [1-3]. Видимо, пришла пора предметно знакомить студентов с основами новой логики как в дисциплинах «Дискретная математика», «Математическая логика и теория алгоритмов», так и в «Схемотехнике», да и в других дисциплинах. В таких вузах, как, например, ИТМО давно изданы соответствующие учебники [4]. Тематика квантовых элементов включается в студенческие работы Московского автомобильно-дорожного государственного технического университета (МАДИ) [5]. Обратимые вычисления дают новый толчок теории автоматов (клеточные автоматы), теории алгоритмов, теории вычислимости и др. [6, 7]. Особое внимание уделяется новым логическим элементам [8-9]. Рис. 1. Томаззо Тоффоли (р. 1943), американско-итальянский ученый, профессор Бостонского университета Такие элементы призваны резко снизить энергозатраты, ибо в них на вычисления выделяются определенные кванты энергии, которые иногда образно называют «биллиардными шарами», а сам компьютер - механическим, биллиардным компьютером. Сами вычисления производятся по простым правилам, и, может быть, самое главное, они могут быть «повернуты вспять», т.е., всегда можно однозначно по результату восстановить исходное состояние, если, конечно, в устройстве нет неисправностей. Один из первых элементов такой логики - управляемый инвертор [10], предложенный Т. Тоффоли (рис. 1) в 1980 г. Элемент Тоффоли (рис. 2) в случае, если С=В=1 (это управляющие входы), выполняет инверсию входа А, иначе сигналы С, В, А проходят на выход без изменения. a б в Рис. 2. Элемент Тоффоли: а - таблица истинности; б - биекция вход-выход; в - условное обозначение Удивительным является тот факт, что количество входов равно количеству выходов и два выхода просто повторяют входы. Анализ таблицы истинности элемента Тоффоли позволяет установить реализуемую систему логических функций: (1) В элементе Тоффоли биекция не сохраняет четность (см. рис. 2). Предположительно в 1983 г. Эдвард Фредкин (рис. 3) совместно с Тоффоли предложил элемент, имеющий несколько измененную биекцию вход-выход (рис. 4). Рис. 3. Эдвард Фредкин (р.1934) в 60-е гг. ХХ в., профессор университета Карнеги Меллона Элемент Фредкина [11,12] имеет взаимно-однозначное соответствие трех его входов A,B,C (управляющий только С) и трех выходов F1,F2,F3, сохраняющее четность: a б в Рис. 4. Элемента Фредкина: а - таблица истинности; б - биекция вход-выход; в - условное обозначение При С=1 информация на входах В и А меняется местами с информацией на выходах (swap). Взаимно-однозначное соответствие означает, что по выходам элемента всегда можно определить значение входов. Поэтому и получается обратимая логика: элемент работает как в прямом, так и в обратном направлении. Применяется терминология «биллиардных» шаров, под которыми можно понимать q-биты и просто биты. То есть «шары» (например, единицы, ноль означает «шара» нет) могут катиться и туда, и обратно [11, 12]. Анализ таблицы истинности элемента Фредкина позволяет установить реализуемую систему логических функций: (2) Можно показать, что при определенных условиях (настройке) элемент Фредкина может реализовать функционально полную систему логических функций: И, ИЛИ, НЕ. Синтезу схем, в том числе с памятью, из таких элементов посвящено достаточно много работ [13-18]. Однако подробное, пошаговое описание, пригодное для использования на занятиях с младшими курсами, автором найдено не было. Обратимый подход также полезен и в области контроля и диагностики, обеспечения надежности [16]. 1. Прямое вычисление суммы и выходного переноса. Рассмотрим реализацию полного сумматора [11] двух бинарных входов p=1 и q=1 с входным переносом r = 1 (рис. 5). Рис. 5. Исходное состояние одноразрядного полного сумматора из пяти элементов Фредкина перед началом вычислений p+q+r; p=1, q=1,r=1 Имеется пять линий (рядов) для движения разноцветных «шаров», символизирующих единицы информации. Дополнительные входы 0 и 1 - это константы. Разветвления не допускаются, ибо количество «шаров» не может увеличиваться. Необходимо определить сумму (sum, parity) и выходной перенос (carry). На первом шаге срабатывает первый элемент и на выходе появляется сигнал (рис. 6), т.е. выход повторяет вход, но это не результат вычислений. Сигнал с входа константы 1 появляется на втором выходе первого элемента. Соответственно сигнал с входа константы 0 появляется на третьем выходе. Поскольку это ноль, то «шара» нет. Рис. 6. Первый шаг: срабатывает первый элемент На втором шаге срабатывает второй элемент, и синий шар опять перемещается на пятую линию (рис. 7). Рис. 7. Второй шаг: срабатывает второй элемент Но затем, на третьем шаге, после срабатывания третьего элемента синий шаг перемещается на четвертую линию (рис. 8). Рис. 8. Третий шаг: срабатывает третий элемент Теперь на четвертом шаге этот синий «шар» находится на управляющем входе четвертого элемента, соответственно, красный «шар» перемещается на пятую линию (рис. 9). Рис. 9.Четвертый шаг: срабатывает четвертый элемент Этот синий «шар» появляется на выходе суммы sum, parity, все верно, 1+1+1 - это 1. А перенос (carry) формируется на пятом шаге (рис. 10). Рис. 10. Пятый шаг: срабатывает пятый элемент Вычисления закончены. На выходе имеем результаты и исходные данные. Кроме того, один из выходов g как бы «лишний». Легко увидеть, что при нулевых операндах константа 1 с пятого входа как раз и пройдёт на этот выход g. 2. Обратное вычисление. На самом деле выход g совсем не лишний. Без него обратные вычисления при нулевых операндах не пройдут. Итак, повернем процесс «вспять», справа-налево. На первом обратном шаге срабатывает пятый элемент (рис. 11). Красный «шар» переноса уходит на пятую линию (см. рис. 11). Аналогично рассуждая и выполняя ещё четыре обратных шага, получим в конце концов исходные данные (рис. 12). Рис. 11. Первый шаг обратного вычисления, срабатывает пятый элемент справа-налево а б в г Рис. 12. Обратное вычисление: а - второй обратный шаг, срабатывает четвертый элемент; б - третий обратный шаг, срабатывает третий элемент; в - четвертый обратный шаг, срабатывает второй элемент; г - пятый обратный шаг, срабатывает первый элемент, исходное состояние 3. Реализация дешифратора. Очевидно, что элемент Фредкина осуществляет дешифрацию сигнала на управляющем входе С, если на одном из информационных входов В,А задать константу 1, например, на В (А=0), так, как указано на рис. 13, 14. Получили дешифратор одного разряда. Очевидно, что обратное вычисление реализуется. Для реализации дешифратора двух разрядов, например Х1Х2, придётся входной сигнал повторить (рис. 15). а б Рис.13. Дешифрация нуля, выход F2 а б Рис.14. Дешифрация единицы, выход F3 Рис. 15. Дешифрация x2=0x1=0 Для формализации синтеза таких схем целесообразно применить разложение Шеннона [19]. 4. Реализация памяти. Для реализации памяти вводится петля обратной связи (рис. 16). а б в Рис. 16. Элемент памяти: а - исходное состояние; б - запоминание; в - хранение Сброс осуществляется, например, так, как указано на рис. 17: а б Рис. 17. Сброс памяти: а - поступление управляющего сигнала справа; б - возврат в исходное состояние 5. Моделирование. Предложим элемент Фредкина на основе элемента LUTFPGA [19]. Выполним моделирование элемента Фредкина в системе схемотехнического моделирования NI Multisim 10 фирмы National Instruments Electronics Workbench Group [20, 21] (рис. 18). а Рис. 17. Моделирование элемента Фредкина: а - С=1, В=1,А=0, F1=1,F2=0,F3=1; б - С=1, В=0,А=1, F1=1,F2=1,F3=0; в - С=0, В=1,А=0, F1=0, F2=1, F3=0; г - С=0, В=0,А=1, F1=0, F2=0, F3=1 б в Рис. 17. Продолжение г Рис. 17. Окончание Моделирование подтверждает правильность функционирования предложенного элемента. Выводы. Таким образом, подробно рассмотрены примеры функционирования обратимых схем на основе элемента Фредкина, используемых в «биллиардном» компьютинге: полного сумматора, дешифратора, элемента памяти. Рассмотренные примеры можно использовать как на лекционных, так и на практических занятиях. Моделированию элемента целесообразно посвятить лабораторную работу. В дальнейшем необходимо разработать двунаправленный элемент и реализовать моделирование работы в двух режимах.

Об авторах

С. Ф Тюрин

Пермский национальный исследовательский политехнический университет; Пермский государственный национальный исследовательский университет

Список литературы

Статистика

Просмотры

Аннотация - 53

PDF (Russian) - 30

Ссылки

• Ссылки не определены.