НЕЙРОННАЯ СЕТЬ С ПОРОГОВОЙ (k, t) СТРУКТУРОЙ ДЛЯ ПРЕОБРАЗОВАНИЯ ОСТАТОЧНОГО КОДА В ДВОИЧНЫЙ ПОЗИЦИОННЫЙ КОД
NEURAL NETWORK WITH THRESHOLD (k, t) STRUCTURE FOR RESIDUAL CODE - BINARY POSITION CODE CONVERSION

Изобретение относится к вычислительной технике и может быть использовано в модулярных нейрокомпьютерах для реализации преобразования кодов.
Известно устройство для преобразования кода из системы остаточных классов в двоичный позиционный код (А.С. 813408, G06F 5/02), содержащее входной регистр, дешифратор, преобразователь кодов из системы остаточных классов в полиадический код, группу элементов ИЛИ, элементы задержки и сумматор. Недостатком устройства является его сложность.
Наиболее близкой по технической сущности к заявленному устройству является нейронная сеть для преобразования остаточного кода в двоичный позиционный код (патент RU 2318238 G06N 3/04, опубликовано 27.02.08, Бюл. №6), содержащая входной слой нейронов, n - нейронных сетей конечного кольца и сумматор.
Недостатком этой нейронной сети является ограниченное функциональное применение: достоверное преобразование из остаточного кода в двоичный позиционный код осуществляется только при правильных значениях всех разрядов остаточного кода.
Целью настоящего изобретения является расширение функциональных возможностей преобразователя остаточного кода в двоичный позиционный код.
Необходимо, чтобы сеть могла правильно преобразовать остаточный код в двоичный при наличии ошибочных разрядах, т.е. без их исправления, что ведет к увеличению скорости преобразования, так как из цикла обнаружения ошибок, их локализации, исправления и преобразования из системы остаточных классов в двоичный код исключается шаг исправления ошибки.
В пороговых (k, t) - схеме множество S делится на m - частей посредством таких алгебраических преобразований, что только по n≤m истинным частям можно восстановить S, где в качестве S используется либо ключ (секрет) в пороговых криптографических схемах, либо обычный кортеж числа, представленного в системе остаточных классов. Данное свойство схемы разделения секрета или кортежа числа дополняется следующим требованиям: если предъявлены k+j=t долей секрета (кортежа), из которых е<j могут отсутствовать или быть ложными (искаженными), то пороговая схема обеспечивает восстановление секрета (кортежа) по подлинным k+j - е частям, что дает возможность контроля над предоставлением полученного результата сторонам с ложными (искаженными) частями секрета (кортежа).
Поставленная цель достигается тем, что в преобразователь введены постоянное запоминающее устройство формирования весовых коэффициентов при реконфигурации нейронных сетей конечного кольца и постоянное запоминающее устройство формирования поправки выходного двоичного кода. Таким образом, нейронная сеть с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код будет состоять из входного слоя нейронных сетей, выполняющих роль регистров, параллельного преобразователя остаточного кода в полиадический, постоянных запоминающих устройств, параллельного взвешенного сумматора (Нейронная сеть для преобразования остаточного кода в двоичный позиционный код, RU, патент 2318238 C1 G06N 3/04), постоянного запоминающего устройства формирования весовых коэффициентов при реконфигурации нейронных сетей конечного кольца и постоянного запоминающего устройства формирования поправки выходного двоичного кода. Функционирование нейронной сети с пороговой (k, t) структурой для преобразования остаточного кода в двоичный рассмотрим на принципе безопасного хранения криптографических ключей, так как функционирование этой сети в случае использования ее для преобразования остаточного кода в двоичный при локализации искаженных разрядов осуществляется аналогично.
Использование криптографического разделения секрета позволяет конструировать ключ из отдельных элементов данных, имеющихся у различных участников или абонентов распределенной вычислительной системы. Секретный ключ восстанавливается путем сбора этих элементов, количество которых достаточно для восстановления исходного ключа.
Принцип разделения секрета основан на применении Китайской теоремы об остатках (КТО).
1
2
t
1
2
t
i
i
i
i
i
i
КТО представляет собой схему разделения секрета без всяких модификаций. Пусть р,р,…,р попарно простые положительные целые числа и . Рассмотрим теперь КТО для целых чисел относительно этих модулей. Предположим, что мы имеем секрет, который является целым числом s с 0≤s≤Р. Секрет s может быть разделен среди t сторон следующим образом. Пусть р,р,…,р обозначают t сторон, которые собираются разделить секрет. Мы даем р остаток s=smodp как секретную информацию, которая известна только р. КТО t частей информации s является достаточным для определения первоначального секрета s, но любой набор с меньшим чем t числом остатков s не могут определить оригинал s. Это схема разделения секрета, но не пороговая схема.
i
(k,t) - Пороговая схема разделения секрета определена следующим образом. Пусть t сторон р разделяют секрет s со следующими свойствами:
i
каждая сторона имеет часть s о секрете s, который не известен другой стороне;
i
секрет s может быть «легко» вычислен из любых k частей s;
i
k-1 частей s не дают никакой информации о секрете s.
i
1
2
k
1
1
2
k-1
В терминах информационной терминологии вышеупомянутое второе условие означает, что взаимная информация между s и любыми k остатками s является равной самой информации s, то есть , где 1≤i<i<…<i≤t. Общепринятое определение для требования во втором условии - существование полиномиального алгоритма для вычисления s из любых k частей s. Вышеупомянутое третье условие говорит о том, что взаимная информация между s и любыми k-1 частями равна нулю, то есть  где 1≤i<i<…<i≤t.
Рассмотрим принцип восстановления ключа в пороговых криптосистемах.
Пусть К - ключ, который требуется сохранить в распределенной системе обработки информации, состоит из n компонентов. Под компонентами подразумеваются: аппаратные средства - ЭВМ, программное обеспечение, данные и пользователи. При этом требуется, чтобы любые L пользователей из тех n (n>L), которые получили информацию о ключе, могли бы вместе восстановить ключ, но никакая группа из L - 1 пользователей или менее не могла этого сделать.
1
2
n
i
i
j
i
j
i
1
2
L
n-L+2
n-L+2
n
1
2
L
Для решения этой задачи сформулируем условия выбора оснований СОК, которые распределены между пользователями криптосистемы. Выберем упорядоченный вектор оснований СОК q<p<р<…<р. Числа р для i=1,2,…,n взаимно простые, т.е. (р,p)=1 для i≠j. Каждому пользователю криптосистемы приписывается свое большое число р(i=1,2,…n). Выберем q<К такое, что (q,p)=1 для всех i=1,2,…n. Произведение L наименьших чисел р, т.е. р,р…p>qpp…p. Если R=pp…p, тогда должно быть больше, чем произведение любых
i
L-1 чисел р.
i
i
Выберем случайное число r в интервале  и вычислим К′=К+rq, чтобы K′ попало в интервал [0,R-1]. Для восстановления ключа К пользователю необходима информация в виде r и К≡К′ modp, i=1,2,…n.
Центр распределения ключей генерирует по идентификатору, поступившему от любого пользователя, случайное числа r и вычисляет К′. Если один из пользователей сети хочет узнать ключ сеанса связи каких-либо пользователей, то он может получить его на основании r и К′, полученных от центра распределения ключей.
Информация, полученная от центра распределения ключей, должна быть аутентифицирована с помощью его собственного ключа. Передающая и принимающая сторона восстанавливают ключ, который знают только один. Для этой цели центр распределения ключей по запросу пользователя вычисляет и передает числа r и К′, по которому пользователь определяет ключ сеанса связи, используемый только в одном случае.
1
Пример 1. Для простоты вычислений будем использовать небольшие числа, хотя на практике применяются очень большие числа. Пусть ключ К=9, число пользователей сети L=2, число всех пользователей n=3. Выберем взаимно простые числа q=13, р=17,
2
3
1
2
3
i
I
i
i
2
3
р=19, р=23. Проверим условие R=pp>qp=17·19>13·23=323>299, условие выполняется. Выберем случайное число r в интервале , например r=2. Найдем К′=K+qr=9+2·13=35. Распределяемые числа r и  передаются всем пользователям, которые определяются как K≡K′mod p,i=1,2,…,n. Итак, К≡35mod17=1, K≡35mod19=16, К≡35mod23=12. По любым двум их этих чисел можно восстановить ключ К, а в общем случае количество выборок  определяется сочетанием из n элементов по L - подмножество мощности L исходного конечного множества мощности n. Число сочетаний из n элементов по L обозначается  и равно .
1
3
1
3
Например, для Kи К имеем K′≡1(mod17), K′≡12(mod17). На основании Китайской теоремы об остатках восстановим К и определим ключ
1
1
1
3
1
3
1
3
1
1
3
3
3
1
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
Используя метод ортогональных базисов, восстановим ключ К. Вначале определим К′≡(КВ+KB)mod(pp), где B и В - ортогональные базисы. По определению ортогональные базисы могут быть представлены в виде: B=mp,B=mp, где m и m - веса базисов соответственно B и B. Причем m и m выбираются из сравнений mp=1modp,mp=1modp. Ввиду малости величин оснований решим сравнения путем подбора m и m, m=3 и m=19. Тогда В=3·23=69, В=19·17=323, K′=1·16+12·323≡394mod391=35. Отсюда K=35-2·13=9. Таким образом, восстановленный ключ К=9.
Недостаток рассмотренного метода заключается в том, что приходится иметь дело с большими числами ,где i=[1,L] и, кроме того, действия сложения и умножения надо выполнять в позиционной системе счисления, а полученный результат необходимо вводить в диапазон вычитаемой величины, кратной .
i
Кроме того, применение КТО для восстановления числа требует сложных вычислений в модулярном нейрокомпьютере, так как элементарные процессоры выполняют операции по модулю р, где i=1,2,…n, а не по модулю  как требуется по КТО.
i
i
i
Для отображения К' необходимы сумматоры по модулю р. Эту нежелательную особенность можно обойти при помощи отображения СОК на ассоциированное представление со смешанным основанием, а затем и на двоичное представление. Коэффициенты К могут быть представлены с помощью L цифр со смешанными основаниями. Отображение из СОК в обобщенную позиционную систему счисления (ОПСС) может быть определено рекурсивно с помощью операций по малым модулям р.
i
Для перехода от вычислений по модулю  к вычислению по модулям р предлагается метод восстановления чисел на основе совместного использования КТО и ОПСС.
1
2
n
1
2
n
1
2
n
1
2
n
Пусть задана система оснований p,p,…p с диапазоном Р=p·p·…·p и ортогональными базисами B, В,…,В, веса которых m,m,…,m, которые определяются как
i
где m - веса ортогональных базисов.
Тогда КТО можно представить в виде
i
где α - остатки (вычеты) числа Х по mod p; R(x) - ранг числа.
i
Представим ортогональные базисы B в ОПСС, тогда
ij
b- коэффициенты ОПСС; i,j=1,2,…,n.
ОПСС
На основании (4) запишем Х выражение (3) в виде
i
i
Так как B mod p=0, ∀j>i, то перед первым значащим разрядом будет i-1 нулей.
Для удобства вычислений базисы можно представить в виде матрицы
i
ij
i
1
При использовании традиционной вычислительной базы произведения αbmod p, можно поместить в память, а адресами будут являться остатки α′.
ij
i
Если вычислительная база представлена в нейросетевом базисе, тогда в качестве весовых коэффициентов нейронной сети будут выступать b, а в качестве входных сигналов - остатки α′.
i
Для выборки всех цифр ОПСС требуется две операции: одна операция выборки из памяти и одна операция для суммирования. По сравнению с известным методом Гарнера выигрыш определяется выражением  Для реализации этого метода в нейропроцессоре необходимо иметь средства для выполнения модульных операций, например, нейронные сети конечного кольца по р основаниям, где i=1,2,…n.
1
2
3
4
1
2
3
4
1
2
3
4
i
ij
Пример 2. Пусть основания системы p=3, р=5, р=7, p=2. Дано число х=(2,3,0,1), представленное в СОК по выбранным модулям. Найти представление этого числа в ОПСС, то есть х=[α′,α′,α′,α′]. На основании выражения (5) определим ортогональные базисы СОК: B=70, В=126, В=120, B=105. Представим базисы B в ОПСС, тогда b:
ij
В связи с тем, что константы b определяются выбором системы
модулей СОК, то их с учетом переноса в i - разрядах можно поместить в память, тогда процесс преобразования можно представить в виде
Для определения всех цифр ОПСС требуются две операции: одна операция для выборки из памяти и одна операция для суммирования. По сравнению с последовательным итерационным процессом выигрыш равен n-1, где n - число модулей СОК.
i
Полученные значения коэффициентов ОПСС α′ числа х используем для образования двоичного кода.
На чертеже представлена нейронная сеть с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код.
Нейронная сеть с пороговой структурой (k, t) для преобразования остаточного кода в двоичный позиционный код содержит входной слой нейронов 2, n - нейронных сетей конечного кольца (НСКК), n - постоянных запоминающих устройств (ПЗУ) 4, сумматор 5 входной нейронной сети 1, выход нейронной сети 6, весовые коэффициенты w 7, постоянное запоминающее устройство формирования весовых коэффициентов при реконфигурации нейронных сетей конечного кольца 8, постоянное запоминающее устройство поправки выходного двоичного разряда 9, сигнала реконфигурации 10 и сигнала поправки 11.
Pi
Блок нейронных сетей конечного кольца (НСКК ) вычисляет разрядные цифры в представлении ОПС и состоит из n НСКК. Из чертежа видно, что остаточные числа
i
i
i
i
i
2
К' (i=1,2,…,n) числа подаются  падаются параллельно через входной слой нейронов на входы всех НСКК р, которые имеют n синаптических весов. Подключения синаптических весов на чертеже показаны точками. НСКК p реализует треугольную матрицу (9) путем сложения цифр в представлении ОПС, описанному выше, т.е. данные в i-канале будут суммироваться с учетом переносов в канале по модулю р в представлении ОПСС. Перенос представляет собой число раз, превышающее величину модуля р, который поступает к (i+1) каналу. Поскольку в каждой строке имеется (i-1) нулей перед первым значащим элементом, а сумма чисел может переноситься (n-1) раз, то абсолютная величина каждого переноса ограничивается величиной (n-1)
ij
ij
где w=b.
ij
ij
Для восстановления ключа, представленного в позиционной системе счисления, используется реконфигурационная структура, которая определяется конфигурацией используемых каналов  на данной сети. При формировании структуры, когда происходит реконфигурация сети, возникают две задачи: первая задача связана с исключением i-каналов, а вторая - с коррекцией весовых коэффициентов w. Структура нейронной сети зависит от номеров исключаемых каналов и адаптируется к нему посредством загрузки весовых коэффициентов w. В то время когда часть сети остается неактивной (исключаемой из системы), весовые коэффициенты между нейронами входного слоя и нейронами скрытого слоя НСКК не используются нейронной сетью и равны нулю. Весовые коэффициенты между нейронами скрытого слоя и нейронами выходного слоя НСКК не активизированных нейронов также равны нулю, а нейроны выходного слоя не активированной части нейронной сети имеют высокое значение (преимущественно ∞), т.е. можно считать, что они исключаются из общей системы.
Посредством коммутации весовых коэффициентов нейронная сеть осуществляет реконфигурацию системы и ее настройку в соответствии с изменением констант СОК. Определенные активированные части нейронной сети активируют другие части, при этом весовые коэффициенты определены из новых констант СОК. В процессе реконфигурации активные нейроны целенаправленно активируют определенные части нейронной сети, просто и быстро приспосабливаясь к определенным внешним параметрам. Таким образом, в процессе вычисления весовые коэффициенты активированной части нейронной сети адаптируются к требованиям внешних параметров. Исходя из этого вычисления нейронная сеть не содержит каких-либо сложных условий реконфигурации системы и вследствие этого происходит быстрое определение значений величины выбранного варианта сети.
ф
Функционирование нейронной сети зависит от весовых коэффициентов между слоями, которые определяются заранее и хранятся в ПЗУ формирования весовых коэффициентов.
Процесс вычисления коэффициентов ОПСС осуществляется активацией определенных входов НСКК, которые выбраны с помощью весовых коэффициентов. Таким образом, реконфигурация сети осуществляется весовыми коэффициентами нейронных связей на активированных входах нейронной сети.
ф
Весовые коэффициенты определяются заранее и помещаются в ПЗУ формирования весовых коэффициентов при реконфигурации, и в зависимости от поступающих сигналов выдаются необходимые весовые коэффициенты для конкретных вариантов, соответственно определяя структуру нейронной сети, в которой при определенных внешних параметрах достигается надежное и быстрое вычисление двоичного кода ключа.
i
i
1
2
i-1
НСКК p преобразуют числа , представленные в остаточном коде в код ОПСС, при этом число представляется в виде, соответствующем ОПСС, следующим образом , где  - называется коэффициентом ОПСС, причем 0≤≤р. Весовой коэффициент, связанный с каждой цифрой ОПСС  равен pp…p. Такая система имеет тот же диапазон представления, что и СОК
1
2
n
1
2
i-1
1
2
i-1
n
Р=рр…р. Коэффициенты кода ОПСС являются адресами памяти, где хранятся значения произведений pp…p. Двоичные эквиваленты значений pp…p, хранящиеся в памяти, поступают на вход сумматора, где по остаткам восстанавливается двоичное число. Для определения кода ключа на вход сумматора поступает поправка, представляющая произведение чисел - rq, которая формируется ПЗУ, а адресом является число r.
i
n
ф
ij
ij
Pi
i
i
1
2
i-1
i
i
1
2
i-1
i
i
i
1
2
i-1
Распределенные числа , представленные в СОК своими остатками  (вход 1), по модулям p (i=1,2,…,L) поступают на входной слой нейронов 2, а число r 11 поступает на адресные входы ПЗУ. Выбранный вариант реконфигурации  определяется сигналом реконфигурации 10, подаваемым на вход ПЗУ. Входной слой связан с L НСКК. При выбранных модулях СОК структура нейронной сети зависит от одного внешнего параметра и адаптируется к нему посредством загрузки весовых коэффициентов w=w=b7, определенных выражением (4, 6). НСКК i=1,L реализуют вычислительную модель (7), на выходах которых формируются коэффициенты ОПСС  числа х. Коэффициенты  являются входными адресами ПЗУ p 4, где хранятся двоичные эквиваленты Kpp…p. Считанные из ПЗУ p двоичные коды, соответствующие произведению Kpp…p, суммируются взвешенным сумматором 5, на выходе которого формируется двоичный код 6. Время преобразования кода определяется L-тактами синхронизации. Структура преобразователя, реализованная на СБИС, требует n - НСКК по модулям p, каждое из которых хранит p слов разрядностью, эквивалентной числу (p-1)pp…p, и одного параллельного сумматора с ускоренным переносом. Сумматор может быть реализован по типу дерева, тогда время преобразования определяется выражением [logn]+1, где n - число модулей СОК.
n
Кроме того, на вход сумматора подается число - rq в дополнительном коде, выбранном по адресу r 11 из ПЗУ. Дополнительный код использован для замены операции вычитания операцией сложения при реализации модели (1).
Рассмотрим числовую интерпретацию примера 1, реализованную архитектурой, приведенной на чертеже. Число всех пользователей n=3, а число пользователей сети
n
ф
ф
L=1. При этом распределяемые числа  поступают на вход нейронов входного слоя, а r - на вход ПЗУ в качестве адресных входов. На вход ПЗУ поступает сигнал реконфигурации. В соответствии с =1, =12 ПЗУ осуществляет конфигурацию нейронной сети путем подачи соответствующих весовых коэффициентов, которые определяются на основе значений , где L=2,3,…, n-1; j∈{2,3,…,L}; L⊂n;
ij
11
13
21
23
ij
- число сочетаний из n по L. На основе (4)  определим b, тогда b=1, b=4 и b=0, b=19. Представим b в виде таблицы на основе (6), тогда
'
1
2
Выражение для данной конфигурации системы K=b+b17, тогда получим значения для коэффициентов ОПСС
'
Итак, K=1+2·17=35.
опс
1
3
1
3
Значения X=[1, 2] являются адресными входами ПЗУ и ПЗУ. На выходе ПЗУ формируется число, равное 1, а на выходе ПЗУ - число, равное 2·17=34. В сумматоре эти значения суммируются 1+34=35, из которого вычисляется значение rq=2·13=26. Все операции в сумматоре выполняются в дополнительном коде. Так как используются положительные целые числа, то дополнительный код числа равен самому числу. Итак, код ключа равен К=35-26=9.
Нейронная сеть с пороговой (n, t) структурой для преобразования остаточного кода в двоичный позиционный код работает следующим образом.
i
ф
i
pi
pi
n
i
pi
i
i-1
1
2
i-1
Входное число  1, представленное в СОК своими остатками  по модулям p(i=1,2,…,n), поступает на входной слой 2. Входной слой связан с n НСКК в соответствии с заданной реконфигурацией, которая зависит от одного внешнего параметра и адаптируется к нему посредством загрузки весовых коэффициентов w 7, формируемых ПЗУ 8 по сигналу реконфигурации 10 и определяемых выражением (4). НСКК p 3 реализует вычислительную модель (7), на выходе которых формируются коэффициенты ОПСС  числа x. Коэффициенты  являются адресными входами ПЗУ 4, где хранятся двоичные эквиваленты . Считанные из ПЗУ двоичные коды, соответствующие произведениям  суммируются взвешенным сумматором 5 с учетом поправки - rq, формируемой ПЗУ 9 по сигналу поправки 11. На выходе 6 формируется двоичный код ключа. Время преобразования определяется n+1 тактами синхронизации. Структура нейронной сети с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код требует n - НСКК по модулям р, n - ПЗУ, каждое из которых хранит р слов разрядностью, эквивалентной числу ppp…p, одного параллельного сумматора с ускоренным переносом, одного постоянного запоминающего устройства формирования весовых коэффициентов при реконфигурации, хранящего  весовых коэффициентов, и постоянного запоминающего устройства формирования поправки, емкость которого определяется произведением .