Full Text

Введение Недалек тот день, когда квант-ютинг (quant-uting - термин автора), т.е. квантовые вычисления [1, 2] будут обычным явлением. В таких вычислениях используются специальные, так называемые обратимые элементы, например элемент Фредкина [3-6]. Элемент Фредкина [3-6] имеет взаимно-однозначное соответствие трех его входов A, B, C (управляющий только С) и трех выходов F1, F2, F3, сохраняющее четность (рис. 1). a б Рис. 1. Бинарный элемент Фредкина: а - биекция «вход-выход»; б - условное обозначение Легко видеть из рис. 1, а, что элемент Фредкина реализует следующую систему логических функций: (1) Обратимость означает возможность проведения вычислений как по системе (1), так и по системе (2): (2) Очевидно, что элемент Фредкина (без учета выхода F1) представляет собой мультиплексор на одну переменную, но с двумя выходами (F2, F3) (рис. 2). Рис. 2. Элемент Фредкина: а - условное обозначение; б - исходное положение при Х = 0, d0 = d1 = 1; в - результат при Х = 0, d0 = d1 = 1; г - исходное положение при Х = 1, d0 = d1 = 1; д - результат при Х = 1, d0 = d1 = 1 На рис. 2 кружки означают так называемые шары в «биллиардном» компьютере [7, 8], имеющие смысл квантов энергии, выделенной на производство вычислений. Получаем реализацию выражения реализации любой функции одной переменной (а также вырожденных функций - констант): (3) Рис. 2 показывает, что элемент Фредкина может работать как слева-направо, так и справа-налево (обратимость). При этом если активирован верхний вход (выход), то два других меняются местами (swap). «Шары» могут рассматриваться в качестве так называемых Q-битов (кубиты). Но возможна и более простая, битовая интерпретация. Таким образом, элемент Фредкина может рассматриваться как элементарный мультиплексор 2-1. А именно из них строятся так называемые Look up Table (LUT - генераторы логических функций на основе мультиплексоров как универсальных логических модулей) программируемых логических интегральных схем (ПЛИС) типа FPGA (Field-Programmable Gate Array) [9-12]. Автором предложен элемент Фредкина как обратимый дублированный 1-LUT и выполнено соответствующее моделирование (рис. 3). Рис. 3. Моделирование обратимого элемента Фредкина в системе Малтисим [13] (Forward - вход управления направлением передачи сигнала) Однако для реализации логических функций необходимы элементы большей размерности, поэтому актуально рассмотрение вопросов разработки и моделирования универсальных логических модулей размерностей 2, 3. 1. Моделирование универсального логического модуля-мультиплексора на две и три переменные В схемах на основе элементов Фредкина запрещены разветвления. Ввиду этого, в отличие от LUT FPGA, необходимы так называемые повторители. Предлагаемый мультиплексор на две переменные, реализующий сумму по модулю 2 двух переменных, представлен на рис. 4. На рис. 4 Х2 = Х1 = 0, d0 = d3 = 0, d1 = d2 = 1. Первый слева элемент Фредкина играет роль повторителя Х1. Рис. 4 показывает исходное положение перед вычислениями. На нулевом наборе (Х2 = Х1 = 0) получаем 0. На первом шаге (см. рис. 4, б) срабатывает первый элемент-повторитель. Поскольку на его управляющем входе нет шара, шар-константа появляется на третьем выходе и далее не используется (это так называемый мусорный выход). На рис. 4, б сразу указан и второй шаг, когда срабатывают два «настроечных» элемента (второй и третий), и, поскольку у них тоже не активированы управляющие входы (первые входы, входы С), шары настройки на заданную функцию переносятся на соответствующие им выходы. Следует отметить, что выходом является Z (X2, X1, d), второй выход последнего элемента Фредкина не используется, так же как и второй выход остальных элементов. Такие выходы называют «мусорными», без них в обратимой логике никак не обойтись, но при синтезе схем стремятся к их минимизации. Продолжим моделирование: на наборе (Х2 = 1, Х1 = 0) получаем 1 (рис. 5). Исходное положение, изображенное на рис. 5, а отличается от изображения на рис. 4, а наличием шара на входе Х2 (последний элемент). На первом шаге (см. рис. 5, б) срабатывает первый элемент-повторитель. Поскольку на его управляющем входе нет шара, шар-константа появляется на третьем выходе и далее не используется (мусорный выход). Далее, на втором шаге, срабатывают два «настроечных» элемента и, поскольку у них тоже не активированы управляющие входы (первые входы, входы С), шары настройки на заданную функцию переносятся на соответствующие им выходы. На рис. 5, б также показано выполнение сразу первого и второго шагов. На третьем шаге (см. рис. 5, в) срабатывает последний элемент, но, поскольку его управляющий вход активирован шаром Х2, шар настройки d2 появляется на выходе Z (X2, X1, d). Действительно, на этом наборе сумма по модулю 2 равна единице. Рассмотрим обратные вычисления для исходного состояния, изображенного на рис. 5, в (рис. 6). а б в Рис. 4. Мультиплексор на две переменные на базе элемента Фредкина, реализующий сумму по модулю 2 при Х2 = Х1 = 0: а - исходное положение; б - первый и второй шаги; в - третий шаг а б в Рис. 5. Мультиплексор на две переменные на базе элемента Фредкина, реализующий сумму по модулю 2 при Х2 = 1; Х1 = 0: а - исходное положение; б - первый и второй шаги; в - третий шаг а б Рис. 6. Обратные вычисления с исходного, изображенного на рис. 5, в: а - первый шаг обратных вычислений; б - второй шаг обратных вычислений а Рис. 7. Мультиплексор на две переменные на базе элемента Фредкина, реализующий сумму по модулю 2 при Х2 = 1; Х1 = 1: а - исходное положение б в г Рис. 7. Окончание: б - первый шаг; в - второй шаг; г - третий шаг Видим, что за два шага «биллиардных» вычислений система вернулась в исходное положение (см. рис. 5, а). Моделирование на наборе (Х2 = Х1 = 1) демонстрирует рис. 7. Рассмотрим обратные вычисления для исходного состояния, изображенного на рис. 7, г (рис. 8). а б в Рис. 8. Обратные вычисления с исходного, изображенного на рис. 7, г: а - первый шаг обратных вычислений; б - второй шаг обратных вычислений; в - третий шаг обратных вычислений Видим, что система вернулась в исходное положение (см. рис. 7, а). Аналогично можно проверить правильность вычислений на наборе (Х2 = 0, Х1 = 1). Таким образом, получили реализацию выражения (4) Разработанный универсальный логический модуль-мультиплексор на три переменные изображен на рис. 9. Рис. 9. Предлагаемый универсальный логический модуль-мультиплексор на три переменные Такой универсальный модуль обладает обратимостью и может в зависимости от настройки d0-d7 реализовать любую логическую функцию трех переменных: (5) 2. Моделирование универсального логического модуля-дешифратора на основе элементов Фредкина Очевидно, что элемент Фредкина при обратном вычислении (справа-налево) выполняет роль универсального логического модуля на одну переменную. Действительно, из выражения (2) можно получить систему, описывающую дешифрацию: (6) где Х - дешифрируемое значение; d - данные. В выражении (3) лишние члены, возникающие вследствие несущественности F3 удалены, т.е. при Х = 0 шар d появляется на выходе z0, иначе - на выходе z1 (рис. 10). Используя такой подход, получим дешифратор на две переменные (рис. 11). Пример: вычисление на наборе (Х2 = Х1 = 0) (рис. 12). а б в г д Рис. 10. Дешифрация одного разряда на основе элемента Фредкина: а - условное обозначение; б - исходное при Х = 1, d = 1; в - результат при Х = 1, d = 1; г - исходное при Х = 0, d = 1; д - результат при Х = 0, d = 1 Рис. 11. Дешифратор на две переменные а б в Рис. 12. Дешифратор на две переменные, дешифрация набора (Х2 = Х1 = 0): а - первый шаг; б - второй шаг; в - третий шаг Набор (Х2 = Х1 = 0) дешифрирован, шар появляется на выходе z0. Аналогично можно выполнить моделирование на других наборах и обратные вычисления. Таким образом, получаем реализацию системы (7) Объединяя по ИЛИ конституенты выражения (7) с помощью соответствующей настройки элементов Фредкина (на дизъюнкцию, например, ), можно получить реализацию не одной функции, а системы логических функций двух переменных. Аналогично строятся универсальные логические модули на большее число переменных. Выводы Таким образом, выполнено «биллиардное» моделирование предложенных универсальных логических модулей на основе обратимых элементов - элементов Фредкина. Моделирование подтвердило работоспособность предложенных моделей, которые могут быть использованы в обратимых ПЛИС. Кроме того, рассмотренные модели могут быть использованы в качестве примеров на практических занятиях по дисциплинам «Дискретная математика», «Математическая логика», «Схемотехника». Предметом дальнейшего исследования могут быть вопросы синхронизации «биллиардных» вычислений и моделирование при использовании кубитовых «шаров» вместо бинарных. В этом плане особый интерес представляет использование самосинхронного подхода [14, 15], развиваемого Институтом проблем информатики Российской академии наук Федерального исследовательского центра «Информатика и управление» Российской академии наук, с которым автор поддерживает творческие связи уже более 25 лет.

About the authors

S. F Tiurin

Perm National Research Polytechnic University; Perm State University

References

Statistics

Views

Abstract - 44

PDF (Russian) - 12

Refbacks

• There are currently no refbacks.