Самопроверяемый специализированный вычислитель систем булевых функций
Владельцы патента RU 2579991:
федеральное государственное казенное военное образовательное учреждение высшего образования "Краснодарское высшее военное училище имени генерала армии С.М. Штеменко" Министерства обороны Российской Федерации (RU)
Изобретение относится к вычислительной технике и может быть использовано для параллельной реализации систем булевых функций с функцией обеспечения контроля ошибок вычислений в средствах криптографической защиты информации. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения возможности достоверного вычисления двоичных псевдослучайных последовательностей, идентичных псевдослучайным последовательностям, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига. Устройство обеспечивает вычисление системы булевых функций, представленной в числовой форме, посредством применения избыточных модулярных кодов и дополнительно содержит регистр памяти, блок памяти хранения оснований системы, блоки вычисления наименьших неотрицательных вычетов числа по основаниям системы, множители, многоместные сумматоры, блок решения системы сравнений с одним неизвестным, блок сравнения, блок оператора маскирования. 7 ил.
Предлагаемое устройство относится к вычислительной технике и может быть использовано для параллельной реализации систем булевых функций с функцией обеспечения контроля ошибок вычислений в средствах криптографической защиты информации.
Известно вычислительное устройство, содержащее шифраторы, выходы которых подключены к входам устройств сравнения, выходы которых подключены к входам устройства управления, выходы которого подключены к постоянным запоминающим устройствам (ПЗУ), предназначенным для хранения констант ортогональных базисов и общего модуля системы, выходы которых подключены к входам умножителей, к которым также подключены выходы шифраторов, на входы которых поступают значения наименьших неотрицательных вычетов по системе попарно простых и упорядоченных модулей системы, значения первого из которых поступают на вход первого умножителя и входы устройств сравнения. Выходы умножителей и выход ПЗУ, предназначенного для хранения констант общего модуля системы, подключены к входам сумматора по общему модулю, выход которого является шиной выдачи результата вычислений (Финько, О.А. Контроль и реконфигурация аналого-цифровых устройств, функционирующих в системе остаточных классов / О.А. Финько // Электронное моделирование. Том №22.4.2000. - С. 92-103).
Недостаток известного устройства - отсутствие функциональных возможностей безошибочного (достоверного) вычисления двоичных псевдослучайных последовательностей, идентичных псевдослучайным последовательностям, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига.
Наиболее близким по сущности технического решения заявленному устройству является вычислительное устройство, включающее в себя блоки памяти, предназначенные для хранения коэффициентов полиномов избыточной числовой нормальной формы, входы которых являются входами устройства, к которым подключена шина подачи булевых переменных, выходы которых соединены с входами многоместных сумматоров, выходы которых соединены с информационными входами многоканальных мультиплексоров, выходы первого мультиплексора подключены к входам блока вычисления остатка по модулю и информационным входам регистра памяти, выходы которого являются выходами устройства выдачи значений булевых функций, выходы второго мультиплексора подключены к входам блока вычисления остатка по модулю, выходы которого подключены к входам элемента ИЛИ-НЕ, выход которого подключен к первому входу элемента И, второй вход которого подключен к входу подачи синхроимпульсов устройства, а выход - подключен к синхровходу регистра памяти; шина подачи коэффициентов полинома избыточной числовой нормальной формы подключена к входам блоков памяти; блок памяти хранения адресов информационных разрядов, к входу которого подключена шина адреса, выход которого подключен к адресным входам мультиплексоров (Пат. 2485575 Российская Федерация, МПК12 G06F 7/57. Самопроверяемый специализированный вычислитель систем булевых функций [Текст] / О.А. Финько, С.А. Диченко, А.К. Вишневский. - №2012120739; заявл. 18.05.2012; зарегистр. 20.06.2013 - 14 с.: ил.).
Недостаток известного устройства - отсутствие функциональных возможностей безошибочного (достоверного) вычисления двоичных псевдослучайных последовательностей, идентичных псевдослучайным последовательностям, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига.
Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения возможности безошибочного (достоверного) вычисления двоичных псевдослучайных последовательностей, идентичных псевдослучайным последовательностям, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига.
Поставленная цель достигается тем, что в самопроверяемый специализированный вычислитель систем булевых функций, содержащий шину подачи τ булевых переменных, блок памяти, предназначенный для хранения коэффициентов линейного числового полинома, к входу которого подключена шина подачи коэффициентов; дополнительно введены регистр памяти, входы которого являются входами устройства, к которым подключена шина подачи τ булевых переменных; блок памяти, предназначенный для хранения оснований системы, к входу которого подключена шина подачи оснований системы, выходы которого вместе с выходами блока памяти хранения коэффициентов линейного числового полинома подключены к входам блоков вычисления наименьших неотрицательных вычетов числа (коэффициентов линейного числового полинома) по основаниям системы, выходы которых вместе с выходами регистра памяти подключены к входам множителей, выходы которых подключены к входам многоместных сумматоров, выходы которых подключены к входам блока решения системы сравнений с одним неизвестным, выход которого подключен к входам блока сравнения и блока оператора маскирования, выход блока сравнения подключен ко второму входу блока оператора маскирования, выходы которого являются выходами устройства выдачи значений τ булевых функций.
Структурная схема предлагаемого устройства дана на фиг. 1.
Предлагаемое устройство предназначено для вычисления двоичных псевдослучайных последовательностей (ПСП), идентичных ПСП, получаемым посредством классических генераторов на линейных рекуррентных регистрах сдвига (ЛРРС), с функцией осуществления контроля ошибок вычислений. Работа устройства основана на представлении систем рекурсивных характеристических уравнений линейными числовыми полиномами (ЛЧП).
Алгоритмы и устройства генерации ПСП, основанные на использовании рекуррентных логических выражений и неприводимых полиномов, наиболее простым по структуре из которых является ЛРРС (фиг. 2), считаются наиболее распространенными и проверенными практикой (Бабаш, А.В. Криптография / А.В. Бабаш, Г.П. Шанкин. - М.: СОЛОН-Р, 2002. - 575 с.).
Структура ЛРРС определяется образующим многочленом:
где τ, ti∈N (i=1, 2, …, l), а также полученным на его основе характеристическим уравнением:
где xp, 
, cj∈{0, 1}; р∈N; j=0, 1, …, τ-1; 
.
В терминах линейной алгебры очередной элемент ПСП хр+τ вычисляется произведением (Песошин, В.А. Генераторы псевдослучайных и случайных чисел на регистрах сдвига: моногр. / В.А. Песошин, В.М. Кузнецов. - Казань: Казан. гос. техн. ун-т, 2007. - 296 с.):
Для осуществления контроля ошибок вычислений в области цифровой схемотехники известны решения, основанные на использовании методов избыточного модулярного кодирования (Согомонян, Е.С. Самопроверяемые устройства и отказоустойчивые системы [Текст] / Е.С. Согомонян, Е.В. Слабаков. - М.: Радио и связь, 1989. - 208 с.). Для применения этих методов к генераторам ПСП необходимо предварительно решить задачу распараллеливания процесса вычислений ПСП.
Решение задачи основано на применении классических параллельных алгоритмов вычисления рекурсий (Ортега, Дж. Введение в параллельные и векторные методы решения линейных систем [Текст] / Дж. Ортега. - М.: Мир, 1991. - 365 с.). Так, например, информационные связи рекурсии (1) можно представить графической зависимостью (фиг. 3).
В частности, ЛРРС длины τ , реализующий данный метод, имеет r ячеек памяти, значения которых совместно образуют (начальное) состояние (xq-1,0, …, xq-1,t, …, xq-1,τ-1). После первого такта работы ЛРРС выдаст xq-1,0 и перейдет в состояние (xq-1,1, …, xq,0), где xq,0=xq-1,0 ⊕ xq-1,t. Продолжая таким образом, ЛРРС генерирует ПСП. Общий вид данного ЛРРС представлен на фиг. 4.
Так, например, для характеристического уравнения:
где xp+τ, xp+t, xp∈{0,1}, соответствующего триному D(x)=χτ+χt+1 (где τ - степень тринома; τ, t∈N; τ≥3; 1≤t≤τ-1), информационные связи рекурсии (2) характеризуются графической зависимостью, представленной на фиг. 5, в соответствии с которой можно построить систему характеристических уравнений (3):
Реализация системы (3) позволяет одновременно получить q-й блок ПСП, состоящий из τ элементов. Выразим правые части системы (3) через заданные начальные условия и представим ее как систему τ булевых функций (БФ)(4) от τ переменных:
где 
- вектор начальных условий.
Используем правило представления БФ fj ЛЧП (Малюгин, В.Д. Параллельные логические вычисления посредством арифметических полиномов [Текст] / В.Д. Малюгин. - М.: Наука. Физматлит, 1997. - 190 с.):
где результат вычисления БФ fj(x1, …, xn) соответствует значению младшего разряда двоичного представления результата вычисления Lj(x1, …, xn).
Получим систему ЛЧП:
Получим общий ЛЧП:
где 
, k=1, 2, …, τ-1; hj∈Z, или
(5)
Окончательный результат образуется путем реализации оператора маскирования 
. Оператор маскирования 
служит для определения значения t-й БФ представления, U=(a
r…a
t…a
2
a
1)2 (запись (…)2 означает запись в 2-ичной системе счисления), то есть 
(Шмерко, В.П. Теоремы Малюгина: новое понимание в логическом управлении, проектировании СБИС и структурах данных для новых технологий [Текст] / В.П. Шмерко // Автоматика и телемеханика. - 2004. - №6. - С. 104-112). Граф вычисления ЛЧП (5) представлен на фиг. 6.
Таким образом, полученный ЛЧП (5) позволяет реализовать q-й блок ПСП длины τ. Значения полученного блока ПСП будут являться начальным заполнением для ЛЧП, реализующего следующий блок последовательности длиной, равной τ.
Пример 1. На фиг. 7 представлен 22-разрядный ЛРРС, структура которого определяется образующим триномом D(χ)=χ22+χ+1 и характеристическим уравнением х22=x0⊕x1. Система уравнений участка ПСП длины τ=22 имеет вид:
Запишем систему характеристических уравнений как систему БФ:
Получим систему ЛЧП:
Получим общий ЛЧП:
где запись (…)16 означает запись в 16-ричной системе счисления.
Пусть xq-1,0=1, xq-1,1=0, xq-1,2=0, xq-1,3=0, xq-1,4=0, xq-1,5=1, xq-1,6=0, xq-1,7=0, xq-1,8=0, xq-1,9=0, xq-1,10=0, xq-1,11=0, xq-1,12=1, xq-1,13=0, xq-1,14=0, xq-1,15=0, xq-1,16=1, xq-1,17=0, xq-1,18=0, xq-1,19=0, xq-1,20, xq-1,21=1, тогда
Таким образом, посредством одного ЛЧП получим g-блок ПСП длины τ=22.
В модулярной арифметике (МА) целое неотрицательное число А может быть однозначно представлено набором остатков по основаниям МА р1<р2<…<рη<pη+1<…<pk:
где Рη=p1p2…рη>А; 
; 
- наименьший неотрицательный вычет числа · по модулю p; p1<p2<…<pη<pη+1<…<pκ - попарно простые; j=1, 2, …, η, η+1, …, κ (Акуш-ский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).
При этом остатки МА α1, α2, …, … αη считаются информационными, a αη+1, …, ακ - контрольными (избыточными). Сама МА является в этом случае расширенной, где Рκ=Pηpη+1…pκ, и охватывает полное множество состояний, представляемых всеми к вычетами. Эта область будет являться полным диапазоном МА [0, Рκ) и состоять из рабочего диапазона [0, Pη), где Pη=p1p2…pη, определяемого неизбыточными основаниями МА, и диапазона, определяемого избыточными основаниями [Рη, Рκ), представляющего недопустимую область. Это означает, что операции над числом А выполняются в диапазоне [0, Рκ). Поэтому, если результат операции МА выходит за пределы Pη, то делается вывод об ошибке вычислений. Полученные числа, меньшие Pη, будем называть правильными, равные или большие Pη - неправильными (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).
Для осуществления контроля ошибок арифметических вычислений при реализации ЛЧП (5) рассмотрим систему, заданную основаниями p1, p2, …, pη, …, pκ. Представим каждый коэффициент hi ЛЧП (5) в виде (6), построим систему малоразмерных ЛЧП вида:
Малоразмерность ЛЧП системы (7) будет обеспечиваться малой величиной коэффициентов 
, определяемых выбранными основаниями системы p1, …, pη, …, рκ.
Подставив в (7) значения остатков системы по соответствующим основаниям для каждого коэффициента hi ЛЧП (5), а также значения переменных xq-1,0, …, xq-1,τ-1, получим избыточный модулярный код (МК), представленный системой ЛЧП (7):
(u(1), u(2), …, u(η), …, u(κ))МК,
где u(1), u(2), …, u(η), …, u(κ) - целые числа.
Решим систему выражений с одним неизвестным:
Так как основания р1, р2, …, pη, …, рκ попарно просты, то в соответствии с известными положениями теории чисел единственным решением системы (8) является выражение:
где 
, 
.
Вхождение результата вычисления (9) в рабочий диапазон (контрольное выражение):
означает отсутствие обнаруживаемых ошибок вычислений.
Пример 2. Пусть q-й блок участка ПСП представлен одним ЛЧП вида:
L(Xq-1)=65xq-1,0+69xq-1,1+20xq-1,2+80xq-1,3.
Выберем основания системы: p1=2, р2=3, p3=5, p4=11, p5=13, где р5 - контрольное основание.
Рабочий и полный диапазоны системы в этом случае равны: Р4=p1p2p3p4=330 и Р5=Р4р5=4290 соответственно.
Представим каждый коэффициент ЛЧП в виде набора остатков по выбранным основаниям системы:
h1=65=(1, 2, 0, 10, 0)МА,
h2=69=(1, 0, 4, 3, 4)МА,
h3=20=(0, 2, 0, 9, 7)МА,
h4=80=(0, 2, 0, 3, 2)МА.
Построим систему (7):
Пусть xq-1,0=xq-1,1=xq-1,3=1, xq-1,2=0, тогда u(1)=2, u(2)=4, u(3)=4, u(4)=16, u(5)=6, получим избыточный МК: (2, 4, 4, 16, 6)МК.
Решим систему (8):
в соответствии с (9) получим: U=214.
Так как результат вычисления U удовлетворяет 0≤U<330, то будем считать, что при вычислениях ошибка допущена не была либо произошла необнаруживаемая ошибка.
На чертежах представлено:
на фиг. 1 изображен самопроверяемый специализированный вычислитель систем булевых функций;
на фиг. 2 изображен общий вид ЛРРС;
на фиг. 3 изображена структурная схема информационных связей рекурсии (1);
на фиг. 4 изображен общий вид ЛРРС (частный случай: образующий полином - трином);
на фиг. 5 изображена структурная схема информационных связей рекурсии (2);
на фиг. 6 изображена структурная схема информационных связей ЛЧП (5);
на фиг. 7 изображена структурная схема 22-х разрядного ЛРРС.
Предлагаемое устройство содержит: шину 10 подачи значений τ булевых переменных xq-1,0, xq-1,0, …, xq-1,τ-1, шину 11 подачи коэффициентов h1, …, hτ ЛЧП, шину 12 подачи оснований системы (информационные: р1, …, pη; контрольные: pη+1, …, pκ), регистр памяти 1, блок памяти 2 коэффициентов h1, …, hτ ЛЧП, блоки 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3.η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы, множители 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4.η.τ, …, 4.κ.1, …, 4.κ.τ, блок памяти 5 оснований р1, …, pη, pη+1, …, рκ системы, многоместные сумматоры 6.1, …, 6.η, …, 6.κ, блок 7 решения системы сравнений с одним неизвестным, блок сравнения 8, блок оператора маскирования 9, выходы 13.1, …, 13.τ выдачи значений τ БФ fq,0(Xq-1), …, fq,τ-1(Xq-1) соответственно.
Шина 10 подачи значений τ булевых переменных xq-1,0, xq-1,1, …, Xq-1,τ-1 является входом регистра памяти 1, шина 11 подачи коэффициентов ЛЧП является входом блока памяти 2 коэффициентов h1, …, hτ ЛЧП, предназначенного для их хранения, шина 12 подачи оснований системы является входом блока памяти 5 оснований р1, …, pη, pη+1, …, рκ системы, предназначенного для их хранения, выходы блоков памяти 2 и 5 являются входами блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3.η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по соответствующим основаниям системы, выходы которых вместе с выходами регистра памяти 1 являются входами множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4.η.τ, …, 4.κ.1, …, 4.κ.τ, выходы которых являются входами многоместных сумматоров 6.1, …, 6.η, …, 6.κ, выходы которых являются входами блока 7 решения системы сравнений с одним неизвестным, выход которого подключен к входам блока сравнения 8 и блока оператора маскирования 9, выход блока сравнения 8 является вторым входом блока оператора маскирования 9, выходы которого являются выходами устройства выдачи значений τ БФ fq,0(Xq-1), …, fq,τ-1(Xq-1) соответственно.
Предлагаемое устройство работает следующим образом.
В исходном состоянии в блоки 2 и 5 памяти занесены по шинам 11 и 12 коэффициенты h1, …, hτ ЛЧП и основания р1, …, pη, pη+1, …, pk системы соответственно, с их выходов на входы блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3.η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы поступают коэффициенты ЛЧП (5) и основания системы. В момент времени, соответствующий началу преобразований, на входы регистра памяти 1 из шины 10 поступают значения булевых переменных xq-1,0, xq-1,1, …, Xq-1,τ-1. С выходов регистра памяти 1 и блоков 3.1.1, …, 3.1.τ, …, 3.η.1, …, 3.η.τ, …, 3.κ.1, …, 3.κ.τ вычисления наименьших неотрицательных вычетов числа (коэффициентов ЛЧП) по основаниям системы на входы множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4.η.τ, …, 4.κ.1, …, 4.κ.τ поступают наименьшие неотрицательные вычеты 
и значения булевых переменных xq-1,0, xq-1,1, …, Xq-1,τ-1. С выходов множителей 4.1.1, …, 4.1.τ, …, 4.η.1, …, 4.η.τ, …, 4.κ.1, …, 4.κ.τ на входы многоместных сумматоров 6.1, …, 6.η, …, 6.κ поступают произведения 
. С выходов многоместных сумматоров 6.1, …, 6.η, …, 6.κ на входы блока 7 решения системы сравнений с одним неизвестным поступают числовые результаты вычисления ЛЧП u(1), …, u(η), …, u(κ). Значения u(1), …, u(η), …, u(κ) являются избыточным МК, представленным системой ЛЧП (7): (u(1), u(2), …, u(η),u(η+1))МК, где u(1), …, u(η), …, u(κ) - целые числа. С выхода блока 7 решения системы сравнений с одним неизвестным на входы блока сравнения 8 и блока оператора маскирования 9 поступает числовой результат вычисления (9). Вхождение результата вычисления (9) в рабочий диапазон (контрольное выражение): 0≤U<Рη означает отсутствие обнаруживаемых ошибок вычислений. Таким образом, при отсутствии ошибок вычислений с блока сравнения 8 на вход блока оператора маскирования 9 поступает сигнал, разрешающий выполнять операцию маскирования, в противном случае - запрещающий. С выхода блока оператора маскирования 9 получим значения БФ fq,0(Xq-1), …, fq,τ-1(Xq-1), которые соответствуют элементам g-го блока ПСП xq,0, xq,1, …, xq,τ-1.
Самопроверяемый специализированный вычислитель систем булевых функций, содержащий шину подачи τ булевых переменных, блок памяти, предназначенный для хранения коэффициентов линейного числового полинома, к входу которого подключена шина подачи коэффициентов; отличающийся тем, что введены регистр памяти, входы которого являются входами устройства, к которым подключена шина подачи τ булевых переменных; блок памяти, предназначенный для хранения оснований системы, к входу которого подключена шина подачи оснований системы, выходы которого вместе с выходами блока памяти хранения коэффициентов линейного числового полинома подключены к входам блоков вычисления наименьших неотрицательных вычетов числа (коэффициентов линейного числового полинома) по основаниям системы, выходы которых вместе с выходами регистра памяти подключены к входам множителей, выходы которых подключены к входам многоместных сумматоров, выходы которых подключены к входам блока решения системы сравнений с одним неизвестным, выход которого подключен к входам блока сравнения и блока оператора маскирования, выход блока сравнения подключен ко второму входу блока оператора маскирования, выходы которого являются выходами устройства выдачи значений τ булевых функций.
