ДЕРЕВО КОНТРОЛЯ ЭЛЕМЕНТА ФРЕДКИНА

  • Авторы: Тюрин С.Ф1,2, Никитин М.С1,3, Никитина К.А1,3
  • Учреждения:
    1. Пермский национальный исследовательский политехнический университет
    2. Пермский государственный национальный исследовательский университет
    3. ПАО «Пермская научно-производственная приборостроительная компания»
  • Выпуск: № 37 (2021)
  • Страницы: 90-103
  • Раздел: Статьи
  • URL: https://ered.pstu.ru/index.php/elinf/article/view/2445
  • DOI: https://doi.org/10.15593/2224-9397/2021.1.05
  • Цитировать

Аннотация


В последнее время активизировались исследования в области так называемых обратимых вычислений, особенно в связи с разработкой квантовых компьютеров и развитием энергосберегающих подходов в электронике. Здесь имеются два основных направления. В рамках «биллиардного» компьютинга на вычисления выделяется определенное количество квантов энергии («биллиардных» шаров), которые перемещаются по определённым правилам со входа схемы ее на выход, не «размножаясь» и не «исчезая». Правила определяются специальными элементами, например элементами Фредкина. «Шары», «выкаченные» на выход, могут быть возвращены обратно по тем же правилам, в этом и заключается обратимость вычислений. Имеется достаточно много публикаций, посвященных этим подходам, однако вопросы диагностики таких схем в полной мере не рассмотрены. Цели исследования: разработка контрольных тестов бинарного элемента Фредкина и построение соответствующего дерева контроля. Методы: анализ таблиц функций отказов заданного элемента, построение оптимального, по числу подаваемых на элемент наборов, теста, нахождение булевых производных логических функций, описывающих элемент. Результаты: построены таблица функций отказов элемента Фредкина, оптимальный тестовый набор из четырёх входных наборов, дерево контроля. Полученные тестовые наборы и дерево контроля могут быть использованы при диагностировании бинарных обратимых схем. Практическая значимость: выполненные вычисления, в том числе полученные булевы производные, могут быть использованы в диагностическом обеспечении квантовых компьютеров, а также в качестве примеров на практических занятиях по дисциплинам «Схемотехника», «Исследование операций».

Полный текст

Введение «Квант-ютинг» (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. Модифицированное дерево контроля элемента Фредкина Таким образом, за три такта можно выяснить техническое состояние элемента при указанной дискуссионной модели отказов (неисправностей). Заключение В статье получены булевы производные первого порядка для логических функций, реализуемых элементом Фредкина. Построены оптимальный тест, содержащий четыре тестовых набора, и дерево контроля. С учетом особенностей «биллиардного» вычисления получен оптимальный модифицированный контрольный тест, содержащий три тестовых набора. Результаты могут быть использованы при тестировании схем, построенных на элементах Фредкина, и на практических занятиях по изучению обратимой логики. Темой дальнейших исследований может быть диагностирование схем из элементов Фредкина, в том числе имеющих память.

Об авторах

С. Ф Тюрин

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

М. С Никитин

Пермский национальный исследовательский политехнический университет; ПАО «Пермская научно-производственная приборостроительная компания»

К. А Никитина

Пермский национальный исследовательский политехнический университет; ПАО «Пермская научно-производственная приборостроительная компания»

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

  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.

Статистика

Просмотры

Аннотация - 68

PDF (Russian) - 22

Ссылки

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

© Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления, 2022

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах