САМОПРОВЕРЯЕМЫЙ СПЕЦИАЛИЗИРОВАННЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ

Предлагаемое устройство относится к вычислительной технике и может быть использовано для достоверной параллельной реализации систем булевых функций в средствах криптографической защиты информации, искусственного интеллекта, системах автоматизированного проектирования интегральных схем и др.

Известно вычислительное устройство, включающее в себя сумматор, выход которого подключен к второму входу регистра результата, регистра для хранения булевых переменных, выход которого подключен к блоку конъюнкций, регистры для фиксации очередных строк матриц, описывающих структуру соответствующих конъюнкций, выходы которых подключены также к блоку конъюнкций, выход которого подключен к третьему входу регистра результата, выход которого является шиной выдачи результата вычислений (Малюгин, В.Д. Параллельные логические вычисления посредством арифметических полиномов. / В.Д.Малюгин. - М.: Физматлит, 1997. - С.156-157).

Недостаток известного устройства - отсутствие функциональной возможности контроля ошибок логических вычислений.

Наиболее близким по сущности технического решения заявленному устройству является вычислительное устройство, содержащее блок конъюнкций, входы которого являются входами устройства для подачи n булевых переменных, выходы подключены к первому и второму блокам памяти, предназначенным для хранения коэффициентов первого и второго полиномов избыточной модулярной числовой нормальной формы соответственно, два сумматора, блок вычисления остатка по модулю, элемент ИЛИ-НЕ, элемент И, регистр памяти, выходы которого являются выходами значений d булевых функций (пат. РФ 2417405, МПК G06F 7/57. Самопроверяемый модулярный вычислитель систем логических функций [Текст] / О.А.Финько, С.М.Сульгин, А.В.Щербаков; заявитель и патентообладатель О.А.Финько, С.М.Сульгин, А.В.Щербаков. - №2009121955; заявл. 08.06.09; зарегистр.27.04.11, - 18 с.: ил.).

Недостаток известного устройства - большая длительность вычислений.

Цель изобретения - уменьшение длительности вычислений.

Поставленная цель достигается тем, что в самопроверяемый специализированный вычислитель систем булевых функций, содержащий блоки памяти, предназначенные для хранения коэффициентов полиномов избыточной числовой нормальной формы, входы которых являются входами устройства, к которым подключена шина подачи n булевых переменных, выходы которых соединены со входами многоместных сумматоров, выходы которых соединены с информационными входами многоканальных мультиплексоров, выходы первого мультиплексора подключены к (s+1)-му, (s+2)-му, …, (d+s)-му входам (d - количество реализуемых булевых функций, составляющих информационные разряды разделенного AN-кода, s - количество избыточных булевых функций, соответствующих избыточным разрядам разделенного AN-кода) блока вычисления остатка по модулю и информационным входам регистра памяти, выходы которого являются выходами устройства выдачи значений d булевых функций, выходы второго мультиплексора подключены к 1-му, 2-му, …, s-му входам блока вычисления остатка по модулю, выходы которого подключены к входам элемента ИЛИ-НЕ, выход которого подключен к первому входу элемента И, второй вход которого подключен к входу подачи синхроимпульсов устройства, а выход подключен к синхровходу регистра памяти, с целью уменьшения длительности вычислений введены шина подачи коэффициентов полиномов избыточной числовой нормальной формы, подключенная к входам блоков памяти, многоканальные мультиплексоры выделения информационных разрядов реализуемых и избыточных булевых функций, блок памяти хранения адресов информационных разрядов, к входу которого подключена шина адреса, выход которого подключен к адресным входам мультиплексоров.

Структурная схема предлагаемого устройства дана на фиг.1.

Известно, что булеву функцию (БФ) можно представить посредством линейных числовых полиномов (ЛЧП) (Финько, О.А. Модулярная арифметика параллельных логических вычислений [Текст] / О.А.Финько. - М.: ИПУ РАН, 2003. - 224 с.).

Например: пороговая БФ как класс булевых функций, которая определяется отношением:

где ; x_i∈{0,1} - булевы переменные; i=1, 2, …, n; 1≤p≤n, р - порог функции , в базисе Ω={∨,∧,¬} может быть выражена дизъюнктивной формулой:

где; K_i - элементарные конъюнкции длины р; 1≤p≤n.

Любую пороговую БФ можно представить с помощью ЛЧП вида:

где c∈Z, Z - множество целых неотрицательных чисел, и удовлетворяет условию:

где • - наименьшее целое число ≥•.

Большой интерес также представляет возможность реализации не только пороговых, но и БФ других классов с помощью одного ЛЧП. Однако задача представления БФ общего вида с помощью одного ЛЧП в настоящее время остается нерешенной. В то же время можно определить условие существования ЛЧП (2), с помощью которого можно реализовать БФ общего вида.

Пусть дана произвольная БФ типовых криптопримитивов, имеющая представление в виде таблицы истинности (табл.1).

Таблица 1 Таблица истинности заданной БФ № x1 x2 xn 0 0 0 0 1 0 0 1 2n-1 1 1 1

где j=0, 1, …, 2ⁿ-1.

Данную БФ можно представить с помощью ЛЧП:

полученного посредством алгоритма проверки представимости БФ общего вида одним ЛЧП:

где |•|_m - наименьший неотрицательный вычет числа • по модулю m; 0≤a_i<m; i=1,2,…, n+1; m=2^t, t∈Z.

Значение БФ может быть вычислено по формуле:

где • - наибольшее целое число, не превосходящее •.

Пусть дана система БФ:

где ; x_i∈{0,1} - булевы переменные; i=1, 2, …, n.

Представим таблицу истинности реализуемой системы БФ в следующем виде (табл.2), где - значения, принимаемые j-й БФ на i-м наборе переменных, - целые неотрицательные числа:

Таблица 2 Таблица истинности заданной системы БФ № x1 х2 xn 0 0 0 0 1 0 0 1 2n-1 1 1 1

Обозначим вычисленные значения БФ (3) как y₁=, y₂=, …, y_d=, а числом Y⁽ⁱ⁾ обозначим двоичное представление:

Представим каждую БФ системы (3) посредством ЛЧП:

где ∈Z, i=1, 2, …, n+1, j=1, 2, …, d.

ЛЧП для системы (3) вычисляется по формуле:

где i=1, 2, …, n; j=1, 2, …, d.

Значение соответствует -му разряду двоичного представления результата вычисления .

Однако представленный алгоритм не позволяет контролировать ошибки, которые возникают при вычислении системы БФ.

Для обеспечения контроля логических вычислений дополним реализуемую систему БФ избыточными БФ и получим избыточную систему где s - количество избыточных БФ.

Так же как и для системы БФ значение которой интерпретируется в виде целых неотрицательных чисел, избыточная система БФ представляется как

где - значения, принимаемые j-и БФ на i-м наборе переменных, Y^*(i) - целые неотрицательные числа.

Рассмотрим полученную избыточную систему БФ по правилу задания разделимого AN-кода (Дадаев, Ю.Г. Арифметические коды, исправляющие ошибки / Ю.Г.Дадаев. - М.: Советское радио, 1969. - 168 с.), где кодовое слово R формируется из выражения:

где Y - исходное число, здесь - вектор значений реализуемых БФ, S=|-2^aY|_A - информационная часть кода, I=2^aY - проверочные символы кодовой комбинации, 2 - основание системы счисления, а - количество двоичных разрядов, необходимое для записи чисел, не превосходящих генератора кода А.

Получим:

Отсюда:

где d - количество информационных символов кодового слова (количество реализуемых булевых функций), s - количество проверочных символов (количество избыточных булевых функций), причем количество проверочных символов зависит от выбора численного значения генератора и определяется следующим образом:

l=log₂AY+1, s=l-d,

где l - общая длина кодовой комбинации.

Таким образом, требуется реализовать таблицу истинности, представленную в табл.3.

Таблица 3 Таблица истинности для избыточной системы БФ № Булевы переменные Система БФ R проверочные информационные х1 xn 0 0 0 R(0) 1 0 1 R(1) 2n-1 1 1 R(2n-1)

Используя преобразование (5), (6) построим полиномы избыточной числовой AN-формы:

Как известно, выбор генератора А арифметического AN-кода определяет арифметическое расстояние кода D и его корректирующие свойства. Таким образом, код с D=2 гарантировано обнаруживает однократную ошибку (в одной БФ).

В процессе реализации систем БФ выполняется классическая процедура контроля ошибок в соответствии со свойствами и выбранными параметрами AN-кода.

Принцип контроля заключается в выполнении следующего правила:

что соответствует правильному результату, а выражение является признаком ошибки.

Пример

Пусть дана таблица истинности системы БФ, представленная в табл.4.

Таблица 4 Пример таблицы истинности системы БФ х1 x2 x3 0 0 0 0 1 1 0 0 1 1 0 2 0 1 0 1 0 2 0 1 1 0 1 1 1 0 0 1 0 2 1 0 1 1 0 2 1 1 0 0 1 1 1 1 1 1 0 2

Полином (6) примет вид:

=27x₁+37х₂+41x₃+43.

Применим арифметический разделимый AN-код с генератором А=5, построим избыточную систему БФ в соответствии с табл.3 и получим табл.5.

Таблица 5 Пример таблицы истинности избыточной системы БФ, реализуемой полиномами и Булевы переменные R х1 x2 x3 0 0 0 0 1 0 1 5 0 0 1 1 0 1 0 10 0 1 0 1 0 1 0 10 0 1 1 0 1 0 1 5 1 0 0 1 0 1 0 10 1 0 1 1 0 1 0 10 1 1 0 0 1 0 1 5 1 1 1 1 0 1 0 10

В соответствии с (6) получим полиномы (9) и (10):

=27x₁+37x₂+41х₃+43,

=12x₁+15x₂+20x₃+59.

Пример обнаружения однократной ошибки (звездочкой * обозначается функция, значение которой содержит ошибку) продемонстрируем в табл.6.

Таблица 6 Пример обнаружения однократной ошибки R Результат контроля 0 1 0 1 5 «верно» 0 0* 0 1 1 «ошибка» 0* 0 1 0 2 «ошибка» 0 1 0 0* 4 «ошибка» 1 0 0* 0 8 «ошибка» 1 0 1 0 10 «верно» 1* 1 0 1 13 «ошибка» 1 1* 1 0 14 «ошибка» 1 0 0* 0 8 «ошибка» 0 1 0 0* 4 «ошибка» 1 0 1 0 10 «верно» 1* 1 0 1 13 «ошибка» 1 1* 1 0 14 «ошибка» 1 0 0* 0 8 «ошибка» 0 1 0 0* 4 «ошибка» 0 1 0 1 5 «верно» 1 0 0* 0 8 «ошибка» 1 0 1 1* 11 «ошибка» 1* 1 0 1 13 «ошибка» 0 0* 0 1 1 «ошибка»

На чертежах представлено:

на фиг.1 изображен самопроверяемый специализированный вычислитель систем булевых функций;

на фиг.2 изображен многоместный пирамидальный сумматор;

на фиг.3 изображен график выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом;

на фиг.4 изображен график зависимости выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом от возрастания количества n булевых переменных.

Предлагаемое устройство содержит: шину 9 подачи значений n булевых переменных x₁, x₂, …, x_n шину 10 подачи коэффициентов полиномов избыточной числовой нормальной формы, блоки памяти 1.1 и 1.2, блок памяти 2 хранения адресов информационных разрядов, шину адреса 11, многоместные сумматоры 3.1 и 3.2, многоканальные мультиплексоры 4.1 и 4.2, блок 5 вычисления остатка по модулю, элемент ИЛИ-НЕ 6, регистр памяти 7, элемент И 8, выходы 12.1, …, 12.d выдачи значений булевых функций …, соответственно, вход 13 шины подачи синхроимпульсов.

Шина 9 подачи значений n булевых переменных x₁, x₂, …, x_n и шина 10 подачи коэффициентов полиномов избыточной числовой нормальной формы, являются входами блоков памяти 1.1 и 1.2, предназначенных для их хранения, выходы которых соединены со входами многоместных сумматоров 3.1 и 3.2, выходы которых соединены с информационными входами многоканальных мультиплексоров 4.1 и 4.2, выходы мультиплексора 4.1 подключены к (s+1)-му, (s+2)-му, …, (d+s}-му входам (старшие разряды слева) блока 5 вычисления остатка по модулю и информационным входам регистра памяти 7, выходы которого являются выходами устройства выдачи значений d булевых функций: …, , выходы мультиплексора 4.2 подключены к 1-му, 2-му, …, s-му входам блока 5 вычисления остатка по модулю, выходы которого подключены к входам элемента 6 ИЛИ-НЕ, выход которого подключен к первому входу элемента 8 И, второй вход которого соединен с входом 13 подачи синхроимпульсов устройства, а выход 8 подключен к синхровходу регистра памяти 7.

Многоместный сумматор как в случае прототипа, так и в случае предлагаемого устройства имеет наиболее типичную - пирамидальную структуру, представленную на фиг.2.

Предлагаемое устройство работает следующим образом. В исходном состоянии в блоки 1.1 и 1.2 памяти занесены по шине 10 коэффициенты: a₁, a₂, …, a_n+1; полиномов избыточной числовой нормальной формы (9) и (10), соответственно полученных в результате преобразований (5), (6), регистр 7 памяти обнулен. В момент времени, соответствующий началу преобразования, на входы блоков 1.1 и 1.2 памяти из шины 9 поступают значения булевых переменных x₁, x₂,…, x_n С выходов блоков 1.1 и 1.2 памяти на входы многоместных сумматоров 3.1 и 3.2 поступают произведения a_i·(x₁, x₂, …, x_n), где i=1, 2, …, n+1 и ·( x₁, x₂, …, x_n), где i=1, 2, …, n+1. С выходов многоместных сумматоров 3.1 и 3.2 значения произведений поступают на информационные входы многоканальных мультиплексоров 4.1 и 4.2, предназначенных для выделения группы значений информационных разрядов, в зависимости от адресов, поступивших на их адресные входы с выходов блока 2 памяти адресов, к входу которого подсоединена шина 11 адреса. С выходов мультиплексора 4.1 на (s+1)-й,(s+2)-й,…,(d+s)-й входы (старшие разряды слева) блока 5 вычисления остатка по модулю и на информационные входы регистра памяти 7 поступает числовой результат вычисления полинома , с выходов мультиплексора 4.2 на 1-й, 2-й, …, s-й входы (старшие разряды слева) блока 5 вычисления остатка по модулю поступает числовой результат вычисления полинома . С выходов блока 5 вычисления остатка по модулю на входы элемента 6 ИЛИ-НЕ поступает результат вычисления . На выходе элемента 6 ИЛИ-НЕ образуется сигнал «1» при выполнении равенства (11) (ошибки нет) и «0» в противном случае. Синхроимпульс с входа 13 устройства через элемент 8 И поступает на синхровход регистра 7 памяти при отсутствии ошибок вычислений в соответствии с (11). Таким образом, при отсутствии ошибок вычислений в регистр 7 памяти записывается численный результат вычисления полинома , интерпретируемый как результат реализации системы БФ, соответствующий размещению от младшего разряда справа к старшим разрядам слева .

Предлагаемое устройство имеет глубину в 6 ступеней преобразования: 1-я ступень - блоки памяти 1.1 и 1.2, предназначенные для хранения коэффициентов полиномов и ; 2-я ступень - многоместные сумматоры 3.1 и 3.2 и блок 2 памяти, предназначенный для хранения адресов информационных разрядов; 3-я ступень - многоканальные мультиплексоры 4.1 и 4.2, предназначенные для выделения информационных разрядов; 4-я ступень - блок 5 вычисления остатка по модулю; 5-я ступень - элемент 6 ИЛИ-НЕ; 6-я ступень - элемент 8 И и регистр 7 памяти. Прототип имеет такую же глубину: 1-я ступень - блок конъюнкций; 2-я ступень - блоки памяти; 3-я ступень - сумматоры; 4-я ступень - блок вычисления остатка по модулю; 5-я ступень - элемент ИЛИ-НЕ; 6-я ступень - элемент И, регистр памяти. Однако наиболее существенный вклад в длительность преобразования как предлагаемого устройства, так и прототипа вносит многоместный арифметический сумматор, длительность его функционирования определяется глубиной его функционирования, которая определяется формулой:

где t - количество входов сумматора. Учитывая то, что в устройстве-прототипе сумматор содержит 2ⁿ входов, а в предлагаемом устройстве - n+1 входов, то соответственно глубина схемы в первом случае составит: log₂(2ⁿ) ступеней, а во втором: log₂(n+1) ступеней. Таким образом, глубина сумматора, используемого в предлагаемом устройстве в

раз меньше по сравнению с прототипом (во столько же раз выше его быстродействие), где T_∑прот - длительность функционирования многоместного сумматора прототипа, а Т_∑заяв - длительность функционирования многоместного сумматора предлагаемого устройства. Например, для различных значений n значения выигрыша представлены в табл.7.

В целом выигрыш в быстродействии предлагаемого устройства составит:

учитывая, что формула (14) примет вид:

Более высокое быстродействие предлагаемого устройства выгодно отличает его от прототипа.

Оценка выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом представлена на фиг.3, 4.

Таким образом, полученные результаты дают научный и инженерный инструментарий для реализации гарантировано достоверной обработки логической информации и обеспечивают необходимые условия для создания перспективных средств криптографической защиты информации.