A “BILLIARDS” SIMULATION OF AN UNIVERSAL LOGIC MODULES BASED ON THE FREDKIN GATES FOR THE QUANT-UTING

Abstract


In the wave of the green computing trend, research has recently intensified on the so-called adiabatic logic, reversible computing, which is supposed to be the basis of quantum computers and bring to a new level of computing power, combined with low power consumption. The basis of this logic is special reversible gates, for example, Fredkin’s gates. Reversibility is a one-to-one correspondence (bijection) between the inputs and outputs of circuits, which means, on the one hand, the possibility of total control of the results of calculations, and on the other hand, the possibility of returning the obtained "energy" quanta for the perform calculations to their source. This approach can significantly reduce the power consumption of computers, as well as increase the reliability of calculations. There are a lot of publications on this topic, however, the development of universal logic modules on such a basis has not been fully considered. The aim of the study is the development and modeling of universal logic modules based on the Fredkin element. In this case, the methods of logical synthesis of a reversible scheme based on a binary Fredkin element, modeling and analysis of billiard calculations are used. The article presents the proposed schemes of the decoder and multiplexer based on the Fredkin element, the "billiard" simulation. The practical significance of the study lies in the fact that the obtained universal logic modules can be used in the synthesis of binary reversible circuits, for example, FPGAs. The performed simulation can be used as examples in practical exercises in the discrete mathematics, mathematical logic, mathematical modeling, and circuitry disciplines.

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

  1. Ismaeel Salman Abu Aballi. Quantum computing. - URL: https:// www.researchgate.net/publication/338828306_Quantum_computing (accessed 12 March 2020).
  2. Чивилихин С.А. Квантовая информатика: учеб. пособие / СПбГУИТМО. - СПб., 2009. - 80 с.
  3. Quantum Gates. - URL: https://www.sciencedirect.com/topics/engineering/quantum-gate (accessed 07 December 2019).
  4. A quantum Fredkin gate / R.B. Patel, J. Ho, F. Ferreyrol, T.C. Ralph, G.J. Pryde // Science Advances. - 2016. - Vol. 2, no. 3. - Art. e1501531. doi: 10.1126/sciadv.1501531
  5. Fredkin E., Toffoli T. Conservative logic // International Journal of Theoretical Physics. - 1982. - Vol. 21, no. 3/4. - P. 219-253.
  6. Гуров С.И., Жуков А.Е. Обратимые вычисления: элементы теории и примеры применения // ХХХ Крымская Осенняя матем. шк.-симп. по спектральным и эволюционным задачам: материалы междунар. конф. (КРОМШ-2019), г. Симферополь, 17-29 сентября 2019 г. - Симферополь: Полипринт Симферополь, 2019. - С. 293-295.
  7. Hosseini H., Dueck G.W. Toffoli gate implementation using the billiard ball model // 40th IEEE Int. Symp. on Multiple-Valued Logic, Barcelona, Spain, 26-28 May 2010. - Barcelona, Spain, 2010. - Р. 173-178. doi: 10.1109/ISMVL.2010.40
  8. Frank M.P. Asynchronous ballistic reversible computing // 2017 IEEE Int. Conf. on Rebooting Computing (ICRC), Washington, DC, USA, 8-9 Nov. 2017. - USA, 2017. doi: 10.1109/ICRC.2017.8123659
  9. Строгонов А., Цыбин С. Программируемая коммутация ПЛИС: взгляд изнутри // Компоненты и технологии. - 2010. - № 11. - С. 56-62.
  10. Тюрин С.Ф., Чудинов М.А. FPGA LUT с двумя выходами декомпозиции по Шеннону // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2019. - № 29. - С. 136-147.
  11. Improving of a circuit checkability and trustworthiness of data processing results in LUT-based FPGA components of safety-related systems / O. Drozd, M. Drozd, O. Martynyuk, M. Kuznietsov // Proceed. of the 13th Int. Conf. on ICT in Educ., Res. and Indust. Appl. Integration, Harmonization and Knowledge Transfer, Kyiv, Ukraine, 15-18 May 2017. - Kyiv, 2017. - P. 654-661 (CEUR Workshop Proceedings, Vol. 1844). - URL: http://ceur-ws.org/Vol-1844/10000654.pdf (accessed 26 March 2020).
  12. Tyurin S.F. LUT's Sliding Backup // IEEE Transactions on Device and Materials Reliability. - 2019. - Vol. 19, iss. 1. - P. 221-225. doi: 10.1109/TDMR.2019.2898724
  13. Сайт разработчика National Instruments. - URL: http://www.ni.com/ multisim/ (дата обращения: 21.02.2020).
  14. Speed-independent floating point coproceccor / Y.A. Stepchenkov, V.N. Zakharov, Y.V. Rogdestvenski [et al.] // Proceed. of IEEE East-West Design & Test Symposium (EWDTS’2015), Batumi, Georgia, 26-29 September 2015. - Batumi, Georgia: IEEE, 2015. - P. 111-114. doi: 10.1109/EWDTS.2015.7493110
  15. Automating the design of asynchronous logic control for AMS electronics / D. Sokolov, V. Khomenko, A. Mokhov [et al.] // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2020. - Vol. 39, iss. 5. - P. 952-965. doi: 10.1109/TCAD.2019.2907905

Statistics

Views

Abstract - 48

PDF (Russian) - 14

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies