САМОПРОВЕРЯЕМЫЙ СПЕЦИАЛИЗИРОВАННЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ
SELF-CHECKING SPECIAL-PURPOSE COMPUTER OF BOOLEAN FUNCTION SYSTEMS

Предлагаемое устройство относится к вычислительной технике и может быть использовано для достоверной параллельной реализации систем булевых функций в средствах криптографической защиты информации, искусственного интеллекта, системах автоматизированного проектирования интегральных схем и др.
Известно вычислительное устройство, включающее в себя сумматор, выход которого подключен к второму входу регистра результата, регистра для хранения булевых переменных, выход которого подключен к блоку конъюнкций, регистры для фиксации очередных строк матриц, описывающих структуру соответствующих конъюнкций, выходы которых подключены также к блоку конъюнкций, выход которого подключен к третьему входу регистра результата, выход которого является шиной выдачи результата вычислений (Малюгин, В.Д. Параллельные логические вычисления посредством арифметических полиномов. / В.Д.Малюгин. - М.: Физматлит, 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 с.).
Например: пороговая БФ  как класс булевых функций, которая определяется отношением:
i
где ; x∈{0,1} - булевы переменные; i=1, 2, …, n; 1≤p≤n, р - порог функции , в базисе Ω={∨,∧,¬} может быть выражена дизъюнктивной формулой:
i
где; K - элементарные конъюнкции длины р; 1≤p≤n.
Любую пороговую БФ можно представить с помощью ЛЧП вида:
где c∈Z, Z - множество целых неотрицательных чисел, и удовлетворяет условию:
где • - наименьшее целое число ≥•.
Большой интерес также представляет возможность реализации не только пороговых, но и БФ других классов с помощью одного ЛЧП. Однако задача представления БФ общего вида с помощью одного ЛЧП в настоящее время остается нерешенной. В то же время можно определить условие существования ЛЧП (2), с помощью которого можно реализовать БФ общего вида.
Пусть дана произвольная БФ типовых криптопримитивов, имеющая представление в виде таблицы истинности (табл.1).
Таблица 1
Таблица истинности заданной БФ
№
x<sub>1</sub>
x<sub>2</sub>
<img file="00000010.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
x<sub>n</sub>
<img file="00000011.tif" he="6" wi="9" img-content="undefined" img-format="tif" />
0
0
0
<img file="00000012.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
0
<img file="00000013.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
1
0
0
<img file="00000012.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000014.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000015.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
<img file="00000016.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
<img file="00000016.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
<img file="00000016.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
<img file="00000016.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
<img file="00000016.tif" he="4" wi="1" img-content="undefined" img-format="tif" />
2<sup>n</sup>-1
1
1
<img file="00000012.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000017.tif" he="8" wi="19" img-content="undefined" img-format="tif" />
n
где  j=0, 1, …, 2-1.
Данную БФ можно представить с помощью ЛЧП:
полученного посредством алгоритма проверки представимости БФ общего вида одним ЛЧП:
m
i
t
где |•| - наименьший неотрицательный вычет числа • по модулю m; 0≤a<m; i=1,2,…, n+1; m=2, t∈Z.
Значение БФ  может быть вычислено по формуле:
где • - наибольшее целое число, не превосходящее •.
Пусть дана система БФ:
i
где ; x∈{0,1} - булевы переменные; i=1, 2, …, n.
Представим таблицу истинности реализуемой системы БФ в следующем виде (табл.2), где  - значения, принимаемые j-й БФ на i-м наборе переменных, - целые неотрицательные числа:
Таблица 2
Таблица истинности заданной системы БФ
№
x<sub>1</sub>
х<sub>2</sub>
<img file="00000027.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
x<sub>n</sub>
<img file="00000028.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000029.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000031.tif" he="6" wi="11" img-content="undefined" img-format="tif" />
<img file="00000032.tif" he="6" wi="9" img-content="undefined" img-format="tif" />
0
0
0
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
0
<img file="00000033.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000034.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000035.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000036.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
1
0
0
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000037.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
<img file="00000038.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000039.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
<img file="00000040.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
<img file="00000041.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000042.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
2<sup>n</sup>-1
1
1
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000043.tif" he="8" wi="18" img-content="undefined" img-format="tif" />
<img file="00000044.tif" he="8" wi="18" img-content="undefined" img-format="tif" />
<img file="00000030.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000045.tif" he="8" wi="18" img-content="undefined" img-format="tif" />
<img file="00000046.tif" he="8" wi="18" img-content="undefined" img-format="tif" />
1
2
d
(i)
Обозначим вычисленные значения БФ (3) как y=, y=, …, y=, а числом Y обозначим двоичное представление:
Представим каждую БФ системы (3) посредством ЛЧП:
где ∈Z, i=1, 2, …, n+1, j=1, 2, …, d.
ЛЧП для системы (3) вычисляется по формуле:
где  i=1, 2, …, n; j=1, 2, …, d.
Значение  соответствует -му разряду двоичного представления результата вычисления .
Однако представленный алгоритм не позволяет контролировать ошибки, которые возникают при вычислении системы БФ.
Для обеспечения контроля логических вычислений дополним реализуемую систему БФ  избыточными БФ  и получим избыточную систему  где s - количество избыточных БФ.
Так же как и для системы БФ  значение которой интерпретируется в виде целых неотрицательных чисел, избыточная система БФ  представляется как
*(i)
где  - значения, принимаемые j-и БФ на i-м наборе переменных, Y - целые неотрицательные числа.
Рассмотрим полученную избыточную систему БФ по правилу задания разделимого AN-кода (Дадаев, Ю.Г. Арифметические коды, исправляющие ошибки / Ю.Г.Дадаев. - М.: Советское радио, 1969. - 168 с.), где кодовое слово R формируется из выражения:
a
a
A
где Y - исходное число, здесь - вектор значений реализуемых БФ, S=|-2Y| - информационная часть кода, I=2Y - проверочные символы кодовой комбинации, 2 - основание системы счисления, а - количество двоичных разрядов, необходимое для записи чисел, не превосходящих генератора кода А.
Получим:
Отсюда:
где d - количество информационных символов кодового слова (количество реализуемых булевых функций), s - количество проверочных символов (количество избыточных булевых функций), причем количество проверочных символов зависит от выбора численного значения генератора и определяется следующим образом:
2
l=logAY+1, s=l-d,
где l - общая длина кодовой комбинации.
Таким образом, требуется реализовать таблицу истинности, представленную в табл.3.
Таблица 3
Таблица истинности для избыточной системы БФ
№
Булевы переменные
Система БФ
R
проверочные
информационные
х<sub>1</sub>
<img file="00000067.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
x<sub>n</sub>
<img file="00000068.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000069.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000071.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000072.tif" he="6" wi="13" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000073.tif" he="6" wi="11" img-content="undefined" img-format="tif" />
0
0
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
0
<img file="00000074.tif" he="7" wi="15" img-content="undefined" img-format="tif" />
<img file="00000075.tif" he="7" wi="15" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000076.tif" he="7" wi="15" img-content="undefined" img-format="tif" />
<img file="00000077.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000078.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
R<sup>(0)</sup>
1
0
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000079.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000080.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000081.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
<img file="00000082.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000083.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
R<sup>(1)</sup>
<img file="00000084.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
<img file="00000085.tif" he="5" wi="2" img-content="undefined" img-format="tif" />
2<sup>n</sup>-1
1
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
1
<img file="00000086.tif" he="6" wi="16" img-content="undefined" img-format="tif" />
<img file="00000087.tif" he="6" wi="16" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000088.tif" he="6" wi="16" img-content="undefined" img-format="tif" />
<img file="00000089.tif" he="6" wi="15" img-content="undefined" img-format="tif" />
<img file="00000070.tif" he="2" wi="5" img-content="undefined" img-format="tif" />
<img file="00000090.tif" he="8" wi="18" img-content="undefined" img-format="tif" />
R<sup>(2n-1)</sup>
Используя преобразование (5), (6) построим полиномы избыточной числовой AN-формы:
Как известно, выбор генератора А арифметического AN-кода определяет арифметическое расстояние кода D и его корректирующие свойства. Таким образом, код с D=2 гарантировано обнаруживает однократную ошибку (в одной БФ).
В процессе реализации систем БФ выполняется классическая процедура контроля ошибок в соответствии со свойствами и выбранными параметрами AN-кода.
Принцип контроля заключается в выполнении следующего правила:
что соответствует правильному результату, а выражение  является признаком ошибки.
Пример
Пусть дана таблица истинности системы БФ, представленная в табл.4.
Таблица 4
Пример таблицы истинности системы БФ
х<sub>1</sub>
x<sub>2</sub>
x<sub>3</sub>
<img file="00000095.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000096.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000097.tif" he="6" wi="9" img-content="undefined" img-format="tif" />
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) примет вид:
1
2
3
=27x+37х+41x+43.
Применим арифметический разделимый AN-код с генератором А=5, построим избыточную систему БФ в соответствии с табл.3 и получим табл.5.
Таблица 5
Пример таблицы истинности избыточной системы БФ, реализуемой полиномами <img file="00000099.tif" he="6" wi="9" img-content="undefined" img-format="tif" /> и <img file="00000100.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
Булевы переменные
<img file="00000101.tif" he="6" wi="9" img-content="undefined" img-format="tif" />
<img file="00000102.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
R
х<sub>1</sub>
x<sub>2</sub>
x<sub>3</sub>
<img file="00000068.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000069.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000103.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000104.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
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):
1
2
3
=27x+37x+41х+43,
1
2
3
=12x+15x+20x+59.
Пример обнаружения однократной ошибки (звездочкой * обозначается функция, значение которой содержит ошибку) продемонстрируем в табл.6.
Таблица 6
Пример обнаружения однократной ошибки
<img file="00000106.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000107.tif" he="7" wi="11" img-content="undefined" img-format="tif" />
<img file="00000108.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
<img file="00000109.tif" he="6" wi="10" img-content="undefined" img-format="tif" />
R
<img file="00000110.tif" he="6" wi="6" img-content="undefined" img-format="tif" />
Результат контроля
0
1
0
1
5
<img file="00000111.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«верно»
0
0<sup>*</sup>
0
1
1
<img file="00000112.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
«ошибка»
0<sup>*</sup>
0
1
0
2
<img file="00000113.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
0
1
0
0<sup>*</sup>
4
<img file="00000114.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
1
0
0<sup>*</sup>
0
8
<img file="00000115.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
1
0
1
0
10
<img file="00000116.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«верно»
1<sup>*</sup>
1
0
1
13
<img file="00000117.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
1
1<sup>*</sup>
1
0
14
<img file="00000118.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
1
0
0<sup>*</sup>
0
8
<img file="00000119.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
0
1
0
0<sup>*</sup>
4
<img file="00000114.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
1
0
1
0
10
<img file="00000120.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«верно»
1<sup>*</sup>
1
0
1
13
<img file="00000121.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
1
1<sup>*</sup>
1
0
14
<img file="00000122.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
1
0
0<sup>*</sup>
0
8
<img file="00000123.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
0
1
0
0<sup>*</sup>
4
<img file="00000114.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
0
1
0
1
5
<img file="00000111.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«верно»
1
0
0<sup>*</sup>
0
8
<img file="00000124.tif" he="7" wi="14" img-content="undefined" img-format="tif" />
«ошибка»
1
0
1
1<sup>*</sup>
11
<img file="00000125.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
1<sup>*</sup>
1
0
1
13
<img file="00000126.tif" he="7" wi="16" img-content="undefined" img-format="tif" />
«ошибка»
0
0<sup>*</sup>
0
1
1
<img file="00000127.tif" he="7" wi="13" img-content="undefined" img-format="tif" />
«ошибка»
На чертежах представлено:
на фиг.1 изображен самопроверяемый специализированный вычислитель систем булевых функций;
на фиг.2 изображен многоместный пирамидальный сумматор;
на фиг.3 изображен график выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом;
на фиг.4 изображен график зависимости выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом от возрастания количества n булевых переменных.
1
2
n
Предлагаемое устройство содержит: шину 9 подачи значений n булевых переменных x, x, …, x шину 10 подачи коэффициентов полиномов избыточной числовой нормальной формы, блоки памяти 1.1 и 1.2, блок памяти 2 хранения адресов информационных разрядов, шину адреса 11, многоместные сумматоры 3.1 и 3.2, многоканальные мультиплексоры 4.1 и 4.2, блок 5 вычисления остатка по модулю, элемент ИЛИ-НЕ 6, регистр памяти 7, элемент И 8, выходы 12.1, …, 12.d выдачи значений булевых функций  …,  соответственно, вход 13 шины подачи синхроимпульсов.
1
2
n
Шина 9 подачи значений n булевых переменных x, x, …, x и шина 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
2
n+1
1
2
n
i
1
2
n
1
2
n
Предлагаемое устройство работает следующим образом. В исходном состоянии в блоки 1.1 и 1.2 памяти занесены по шине 10 коэффициенты: a, a, …, a;  полиномов избыточной числовой нормальной формы (9) и (10), соответственно полученных в результате преобразований (5), (6), регистр 7 памяти обнулен. В момент времени, соответствующий началу преобразования, на входы блоков 1.1 и 1.2 памяти из шины 9 поступают значения булевых переменных x, x,…, x С выходов блоков 1.1 и 1.2 памяти на входы многоместных сумматоров 3.1 и 3.2 поступают произведения a·(x, x, …, x), где i=1, 2, …, n+1 и ·( x, x, …, x), где 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-я ступень - элемент И, регистр памяти. Однако наиболее существенный вклад в длительность преобразования как предлагаемого устройства, так и прототипа вносит многоместный арифметический сумматор, длительность его функционирования определяется глубиной его функционирования, которая определяется формулой:
n
n
2
2
где t - количество входов сумматора. Учитывая то, что в устройстве-прототипе сумматор содержит 2 входов, а в предлагаемом устройстве - n+1 входов, то соответственно глубина схемы в первом случае составит: log(2) ступеней, а во втором: log(n+1) ступеней. Таким образом, глубина сумматора, используемого в предлагаемом устройстве в
∑прот
∑заяв
раз меньше по сравнению с прототипом (во столько же раз выше его быстродействие), где T - длительность функционирования многоместного сумматора прототипа, а Т - длительность функционирования многоместного сумматора предлагаемого устройства. Например, для различных значений n значения выигрыша представлены в табл.7.
Таблица 7
Значения выигрыша по сравнению с сумматором прототипа
n
2
3
4
5
6
7
8
9
10
11
K<sub>выигр</sub>
1
1.5
1.4
1.667
2
2.333
2
2.25
2.5
2.75
В целом выигрыш в быстродействии предлагаемого устройства составит:
учитывая, что  формула (14) примет вид:
Более высокое быстродействие предлагаемого устройства выгодно отличает его от прототипа.
Оценка выигрыша в скорости функционирования заявленного устройства по сравнению с прототипом представлена на фиг.3, 4.
Таким образом, полученные результаты дают научный и инженерный инструментарий для реализации гарантировано достоверной обработки логической информации и обеспечивают необходимые условия для создания перспективных средств криптографической защиты информации.