Полный текст

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

Об авторах

С. Ф Тюрин

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

М. С Никитин

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

К. А Никитина

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

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

Статистика

Просмотры

Аннотация - 26

PDF (Russian) - 13

Ссылки

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