CHECKING TREE OF A FREDKIN GATE

Abstract


Recently, research has intensified in the field of so-called reversible computing, especially in connection with the development of quantum computers and the development of energy-saving approaches in electronics. There are two main directions here. Within the framework of "billiard" computing, a certain number of energy quanta ("billiard" balls) are allocated for calculations, which move according to certain rules from the input of the circuit to the output, without "multiplying" or "disappearing". The rules are determined by special elements, for example, Fredkin's elements. “Balls” “pumped out” to the exit can be returned back according to the same rules, and this is the reversibility of calculations. There are a lot of publications devoted to these approaches, however, the issues of diagnostics of such schemes have not been fully considered. Purpose of the study: development of checking tests for the Fredkin binary element and construction of the corresponding checking tree. Methods: analysis of tables of failure functions of a given element, construction of an optimal test, according to the number of sets fed to an element, finding Boolean derivatives of logical functions that describe an element. Results: A table of functions of Fredkin's element failures was built, an optimal test set of four binary vectors, a control tree was built. The obtained test sets and the checking tree can be used to diagnose binary reversible circuits. Practical significance: The performed calculations, including the obtained Boolean derivatives, can be used in diagnostic support of quantum computers, as well as examples in practical classes in the disciplines "Circuitry", "Operations Research".

Full Text

Введение «Квант-ютинг» (Quant-uting, термин автора), т.е. квантовые вычисления активно развиваются [1-2]. Особенные надежды исследователей возлагаются на криптографические применения [3], однако и эффективное решение многих «переборных» задач не остаётся в стороне и ждёт своего воплощения в Q-битах и Q-байтах, что может смягчить так называемое «проклятие размерности». Идет негласное соревнование «у кого больше кубитов», речь даже идет и о квантовом превосходстве и не много-не мало чуть ли не о квантовой холодной войне [4]! В этой области новое дыхание получили так называемые клеточные автоматы (QCA-Quantum-dot cellular automata) [5]. По всей видимости, на наших глазах начинается новая технологическая революция, соединяющая наноэлектронику и квантовую механику. Но пока этого не произошло, весьма актуальны исследования в области так называемых обратимых вычислений [6], основанных на соответствующих элементах, которые и предполагается использовать в квантовых компьютерах, но в бинарном исполнении. Обратимость означает возможность по результатам вычислений однозначно восстановить исходное положение и исходные данные, что обеспечивает новый уровень контролепригодности и надёжности. С другой стороны, это позволяет получить новый уровень энергоэффективности, когда выделенная для вычислений энергия может быть возвращена ее источнику (так называемая адиабатическая логика) [7, 8]. Предложенные логические обратимые элементы [9-13] являются, по существу, элементарными обратимыми квантовыми автоматами. Наиболее интересным и функциональным представляется так называемый элемент Фредкина [12], предложенный в начале 80-х гг. ХХ в. Элемент Фредкина [12], имеет биективное соответствие трех его входов A,B,C (управляющий вход С) и трех выходов F1, F2, F3, сохраняющее четность: A, B, C могут быть входами соответствующих кубитов (так же, как и выходы F1, F2, F3), но мы ограничимся их бинарной интерпретацией. В соответствии с рис. 1, а элемент Фредкина реализует следующую систему логических функций [11, 12]: (1) a б Рис. 1. Бинарный элемент Фредкина: а - взаимно-однозначное соответствие «вход-выход»; б - условное обозначение В соответствии с моделью так называемого «биллиардного» компьютера [12] на входы поступают «биллиардные» шары, символизирующие кубиты или просто биты. Процесс вычислений сводится к «перекатыванию» этих «квантов» энергии со входов на выходы. Причем, если есть «шар» на входе С, то шары со входов В и А катятся «крест-накрест». Если шара на входе С нет, то они катятся «прямо» (рис. 2). a б в г Рис. 2. Функционирование элемента Фредкина: а - исходное положение 1; б - смена мест 1 (swap); в - исходное положение 2; г - параллельное движение Предложены транзисторные реализации элемента Фредкина, в том числе в ПЛИС [14, 15], кроме того, разработаны соответствующие обратимые элементы памяти [16]. Активно разрабатываются методы синтеза таких схем [17]. Однако в элементе могут возникнуть неисправности [18-19]. Тогда система функций (1) изменится. Как таковое тестирование элемента Фредкина в доступных автору работах найдено не было. В работах [14, 20] рассматриваются вопросы надёжности таких схем с точки зрения контролепригодности, однако тестирование самого элемента Фредкина не приведено. В работе [21] рассматриваются сбоеустойчивые обратимые схемы, но сам процесс тестирования отдельного элемента не приведен. В то же время для тестирования обратимых схем необходимо иметь представление о тестировании каждого отдельного элемента и выявить соответствующие закономерности. Для этого целесообразно получить так называемый контрольный тест элемента Фредкина [19, 22], дающий ответ на вопрос, работоспособно ли это устройство или нет. Получение булевых производных логических функций элемента Фредкина Построим оптимальный тест и дерево контроля такого элемента. Применяются диагностический анализ [19, 22] работы бинарного элемента Фредкина в условиях заданной модели однократных константных отказов и математический аппарат булевых производных. Для этого необходимо для выбранной модели отказов (неисправностей) получить дефектные функции и построить таблицу функций отказов. Далее требуется получить оптимальное покрытие этой таблицы (оптимальное, т.е. кратчайшее покрытие всех неисправностей тестовыми наборами) и построить дерево контроля, один из листов которого содержит состояние без наличия неисправностей. Последовательная подача таких наборов позволяет выявить техническое состояние элемента. Получим функции, реализуемые при однократных константных отказах входов [19, 22]: (2) Получим булевы производные первого порядка [22]. (3) Полученные производные позволяют определить тестовые наборы. Используя (2)-(3), получим таблицу функций отказов элемента Фредкина (табл. 1), используя [22]. Таблица 1 Таблица функций отказов элемента Фредкина № Входы Выходы при отсутствии отказов (состояние S0) Отказы входа С Отказы входа В C B A F1 F2 F3 F1(C1) F1(C0) F2(C1) F2(C0) F3(C1) F3(C0) F1(B1) F1(B0) F2(B1) F2(B0) F3(B1) F3(B0) 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 2 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 3 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 4 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 5 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 6 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 7 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 Продолжение табл. 1 № Входы Выходы при отсутствии отказов (состояние S0) Отказы входа А Покрытие C B A F1 F2 F3 F1(A1) F1(A0) F2(A1) F2(A0) F3(A1) F3(A0) 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 * 2 0 1 0 0 1 0 0 0 1 1 1 0 * 3 0 1 1 0 1 1 0 0 1 1 1 0 4 1 0 0 1 0 0 1 1 1 0 0 0 5 1 0 1 1 1 0 1 1 1 0 0 0 * 6 1 1 0 1 0 1 1 1 1 0 1 1 * 7 1 1 1 1 1 1 1 1 1 0 1 1 Визуальный анализ таблицы позволяет получить, например, тест контрольный: (5) Запишем выражение теста контрольного (6) Упрощаем: (7) Так и есть, получаем минимум четыре тестовых набора: (8) Построим дерево контроля (рис. 3). Рис. 3. Дерево контроля элемента Фредкина Таким образом, за четыре такта можно выяснить техническое состояние элемента. Получение оптимального теста с учетом модифицированной таблицы функций отказов элемента Фредкина Но отказы типа «появление» шара (например, F1(C1)) представляются совершенно невероятными в «биллиардном» компьютинге. Другое дело, если шар как бы «застревает», например F1(A0). Получим более реалистичную таблицу функций отказов элемента Фредкина (табл. 2), используя [22-25]. Таблица 2 Модифицированная таблица функций отказов элемента Фредкина № Входы Выходы при отсутствии отказов (состояние S0) Отказы входа С Отказы входа В C B A F1 F2 F3 F1(C0) F2(C0) F3(C0) F1(B0) F2(B0) F3(B0) 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 2 0 1 0 0 1 0 0 1 0 0 0 0 3 0 1 1 0 1 1 0 1 1 0 0 1 4 1 0 0 1 0 0 0 0 0 1 0 0 5 1 0 1 1 1 0 0 0 1 1 1 0 6 1 1 0 1 0 1 0 1 0 1 0 0 7 1 1 1 1 1 1 0 1 1 1 1 0 Продолжение табл. 2 № Входы Выходы при отсутствии отказов (состояние S0) Отказы входа А C B A F1 F2 F3 F1(A0) F2(A0) F3(A0) 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 2 0 1 0 0 1 0 0 1 0 3 0 1 1 0 1 1 0 1 0 4 1 0 0 1 0 0 1 0 0 5 1 0 1 1 1 0 1 0 0 6 1 1 0 1 0 1 1 0 1 7 1 1 1 1 1 1 1 0 1 Запишем выражение теста контрольного для реалистичной модели (9) Упростим выражение (9): (10) Получаем минимум 3 шага тестирования. Построим модифицированное дерево контроля (рис. 4). Рис. 4. Модифицированное дерево контроля элемента Фредкина Таким образом, за три такта можно выяснить техническое состояние элемента при указанной дискуссионной модели отказов (неисправностей). Заключение В статье получены булевы производные первого порядка для логических функций, реализуемых элементом Фредкина. Построены оптимальный тест, содержащий четыре тестовых набора, и дерево контроля. С учетом особенностей «биллиардного» вычисления получен оптимальный модифицированный контрольный тест, содержащий три тестовых набора. Результаты могут быть использованы при тестировании схем, построенных на элементах Фредкина, и на практических занятиях по изучению обратимой логики. Темой дальнейших исследований может быть диагностирование схем из элементов Фредкина, в том числе имеющих память.

About the authors

S. F Tyurin

Perm National Research Polytechnic University; Perm State University

M. S. Nikitin

Perm National Research Polytechnic University; PJSC «Perm Scientific-Industrial Instrument Making Company»

K. A. Nikitina

Perm National Research Polytechnic University; PJSC «Perm Scientific-Industrial Instrument Making Company»

References

  1. Ismaeel Salman Abu Aballi. Quantum computing. - URL: https://www.researchgate.net/publication/338828306_Quantum_computing (дата обращения: 12.03.2020).
  2. Чивилихин С.А. Квантовая информатика: учеб. пособие. - URL: https://books.ifmo.ru/file/pdf/626.pdf (дата обращения: 11.03.2020).
  3. Cryptography in Quantum Computing / Pam Choy, Dustin Cates, Florent Chehwan, [..], Charles C. Tappert. - URL: https://www.researchgate.net/publication/336496979_Cryptography_in_Quantum_Computing (дата обращения: 10.03.2020). doi: 10.1007/978-3-030-32520-6_30
  4. У кого кубитов больше. - URL: https://nplus1.ru/material/2019/ 11/07/quantum-advantage (дата обращения: 11.03.2020).
  5. Neeraj Kumar Misra. Quantum computing and QCA Computing.- URL: https://www.researchgate.net/publication/338282394_Quantum_computing_And_QCA_Computing (дата обращения: 11.03.2020). doi: 10.13140/RG.2.2.18869.01760
  6. Гуров С.И., Жуков А.Е. Обратимые вычисления: элементы теории и примеры применения. - URL: https://www.elibrary.ru/ download/elibrary_41315817_30296914.pdf (дата обращения: 11.03.2020).
  7. Адиабатическая реверсивная логика. - URL: https://postnauka.ru/video/57443 (дата обращения: 10.03.2020).
  8. Лосев В.В., Чаплыгин Ю.А., Крупкина Т.Ю. Новые методы построения микроэлектронных цифровых систем с низким энергопотреблением. - URL: http://www.kosrad.ru/conf/MEC/data/papers/m10-123-73541.pdf (дата обращения: 10.03.2020).
  9. Пронин Ц.Б., Остроух А.В. Квантовые логические элементы, результаты и анализ их влияния на квантовые цепи. - URL: https://naukaip.ru/ wp-content/uploads/2017/11/%D0%9A-67-%D0%A1%D0%B1%D0%BE%D1 %80%D0%BD%D0%B8%D0%BA%D0%A7%D0%B0%D1%81%D1%82%D1%8C-1.pdf (дата обращения: 11.03.2020).
  10. Quantum Gates. - URL: https://www.sciencedirect.com/topics/ engineering/quantum-gate (дата обращения: 07.12.2019).
  11. A quantum Fredkin gate / Raj B. Patel1, Joseph Ho, Franck Ferreyrol1, Timothy C. Ralph and Geoff J. Pryde. - URL: https://advances. sciencemag.org/content/2/3/e1501531 (дата обращения: 12.12.2019).
  12. Fredkin E., Toffoli T. Conservative logic // International Journal of Theoretical. Physics. - 1982. - 21, 3/4. - P. 219-253. - URL: http://web.archive.org/web/20061017232512/http://www.digitalphilosophy.org/download_documents/ConservativeLogic.pdf (дата обращения: 12.12.2019).
  13. Обратимые вычисления. Ч. II / С.И. Гуров, А.Е. Жуков, Д.В. Закаблуков, Г.В. Кормаков. - URL: https://tvim.info/files/journal/ tvim_2019_4.pdf (дата обращения: 10.03.2020).
  14. Prasanna M., Amudha S. Implementation of testable reversible sequential circuit on FPGA // International Conference on Innovations in Information, Embedded and Communication Systems, ICIIECS - 2015 (19-20 March 2015): proceedings. - Coimbatore, India: IEEE, 2015. - P. 145-150. doi: 10.1109/ICIIECS.2015.7192888
  15. Himanshu, Thapliyal, Vinod A.P. Design of Reversible Sequential Elements with Feasibility of Transistor Implementation // IEEE International Symposium on Circuits and Systems (27-30 May 2007): proceedings. - New Orleans, LA, USA: IEEE, 2007. - P. 121-126. doi: 10.1109/ISCAS.2007.378815
  16. Prashant R. Yelekar, Sujata S. Chiwande. Design of sequential circuit using reversible logic // IEEE-International Conference On Advances In Engineering, Science and Management, ICAESM - 2012 (30-31 March 2012): proceedings. - Nagapattinam, Tamil Nadu, India: IEEE, 2012. - P. 321-326.
  17. Закаблуков Д.В. Методы синтеза обратимых схем из функциональных элементов NOT, CNOT и 2-CNOT: автореф. дис. … канд. физ.-мат. наук. - URL: https://docplayer.ru/149126692-Zakablukov-dmitriy-vladimirovich-metody-sinteza-obratimyh-shem-iz-funkcionalnyh-elementov-not-cnot-i-2-cnot.html (дата обращения: 10.03.2020).
  18. ГОСТ 27.002-2015. Надежность в технике Основные понятия. Термины и определения. (Введ. 2017-03-01). - М.: Стандартинформ, 2016. - 23 с.
  19. ГОСТ 20911-89. Техническая диагностика. Термины и определения. - М.: Стандартинформ, 2009. - 11 с.
  20. Himanshu Thapliyal, Nagarajan Ranganathan, Saurabh Kotiyal. Design of Testable Reversible Sequential Circuits // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. - July 2013. - Vol. 21, № 7. - P. 1201-1209. doi: 10.1109/TVLSI.2012.2209688
  21. Гуров С.И., Кормаков Г.В., Жукова Т.Д. Сбоеустойчивые обратимые схемы. - URL: http://conf-symp.sfedu.ru/2018tMoryak.pdf (дата обращения: 10.03.2020).
  22. Тюрин С.Ф., Аляев Ю.А. Дискретная математика: практическая дискретная математика и математическая логика. - М.: Финансы и статистика, 2010. - 394 с.
  23. Тюрин С.Ф. Логика «биллиардного» компьютера // Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления. - 2020. - № 33. - С. 61-77.
  24. Тюрин С.Ф. «Биллиардное» моделирование универсальных логических модулей на основе элемента Фредкина для квант-ютинга // Прикладная математика и вопросы управления. - 2020. - № 2. - С. 55-72.
  25. Tyurin S.F. LUT based Fredkin gate // Radio Electronics, Computer Science, Control. - 2020. - № 1. - P. 44-53.

Statistics

Views

Abstract - 26

PDF (Russian) - 13

Refbacks

  • There are currently no refbacks.

Copyright (c) 2022 PNRPU Bulletin. Electrotechnics, Informational Technologies, Control Systems

This website uses cookies

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

About Cookies