НЕЙРОННАЯ СЕТЬ С ПОРОГОВОЙ (k, t) СТРУКТУРОЙ ДЛЯ ПРЕОБРАЗОВАНИЯ ОСТАТОЧНОГО КОДА В ДВОИЧНЫЙ ПОЗИЦИОННЫЙ КОД Российский патент 2010 года по МПК G06N3/04 

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

Известно устройство для преобразования кода из системы остаточных классов в двоичный позиционный код (А.С. 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) структурой для преобразования остаточного кода в двоичный рассмотрим на принципе безопасного хранения криптографических ключей, так как функционирование этой сети в случае использования ее для преобразования остаточного кода в двоичный при локализации искаженных разрядов осуществляется аналогично.

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

Принцип разделения секрета основан на применении Китайской теоремы об остатках (КТО).

КТО представляет собой схему разделения секрета без всяких модификаций. Пусть р₁,р₂,…,р_t попарно простые положительные целые числа и . Рассмотрим теперь КТО для целых чисел относительно этих модулей. Предположим, что мы имеем секрет, который является целым числом s с 0≤s≤Р. Секрет s может быть разделен среди t сторон следующим образом. Пусть р₁,р₂,…,р_t обозначают t сторон, которые собираются разделить секрет. Мы даем р_i остаток s_i=smodp_i как секретную информацию, которая известна только р_i. КТО t частей информации s_i является достаточным для определения первоначального секрета s, но любой набор с меньшим чем t числом остатков s_i не могут определить оригинал s. Это схема разделения секрета, но не пороговая схема.

(k,t) - Пороговая схема разделения секрета определена следующим образом. Пусть t сторон р_i разделяют секрет s со следующими свойствами:

каждая сторона имеет часть s_i о секрете s, который не известен другой стороне;

секрет s может быть «легко» вычислен из любых k частей s_i;

k-1 частей s_i не дают никакой информации о секрете s.

В терминах информационной терминологии вышеупомянутое второе условие означает, что взаимная информация между s и любыми k остатками s_i является равной самой информации s, то есть , где 1≤i₁<i₂<…<i_k≤t. Общепринятое определение для требования во втором условии - существование полиномиального алгоритма для вычисления s из любых k частей s₁. Вышеупомянутое третье условие говорит о том, что взаимная информация между s и любыми k-1 частями равна нулю, то есть где 1≤i₁<i₂<…<i_k-1≤t.

Рассмотрим принцип восстановления ключа в пороговых криптосистемах.

Пусть К - ключ, который требуется сохранить в распределенной системе обработки информации, состоит из n компонентов. Под компонентами подразумеваются: аппаратные средства - ЭВМ, программное обеспечение, данные и пользователи. При этом требуется, чтобы любые L пользователей из тех n (n>L), которые получили информацию о ключе, могли бы вместе восстановить ключ, но никакая группа из L - 1 пользователей или менее не могла этого сделать.

Для решения этой задачи сформулируем условия выбора оснований СОК, которые распределены между пользователями криптосистемы. Выберем упорядоченный вектор оснований СОК q<p₁<р₂<…<р_n. Числа р_i для i=1,2,…,n взаимно простые, т.е. (р_i,p_j)=1 для i≠j. Каждому пользователю криптосистемы приписывается свое большое число р_i(i=1,2,…n). Выберем q<К такое, что (q,p_j)=1 для всех i=1,2,…n. Произведение L наименьших чисел р_i, т.е. р₁,р₂…p_L>qp_n-L+2p_n-L+2…p_n. Если R=p₁p₂…p_L, тогда должно быть больше, чем произведение любых

L-1 чисел р_i.

Выберем случайное число r в интервале и вычислим К′=К+rq, чтобы K′ попало в интервал [0,R-1]. Для восстановления ключа К пользователю необходима информация в виде r и К_i≡К′ modp_i, i=1,2,…n.

Центр распределения ключей генерирует по идентификатору, поступившему от любого пользователя, случайное числа r и вычисляет К′. Если один из пользователей сети хочет узнать ключ сеанса связи каких-либо пользователей, то он может получить его на основании r и К′, полученных от центра распределения ключей.

Информация, полученная от центра распределения ключей, должна быть аутентифицирована с помощью его собственного ключа. Передающая и принимающая сторона восстанавливают ключ, который знают только один. Для этой цели центр распределения ключей по запросу пользователя вычисляет и передает числа r и К′, по которому пользователь определяет ключ сеанса связи, используемый только в одном случае.

Пример 1. Для простоты вычислений будем использовать небольшие числа, хотя на практике применяются очень большие числа. Пусть ключ К=9, число пользователей сети L=2, число всех пользователей n=3. Выберем взаимно простые числа q=13, р₁=17,

р₂=19, р₃=23. Проверим условие R=p₁p₂>qp₃=17·19>13·23=323>299, условие выполняется. Выберем случайное число r в интервале , например r=2. Найдем К′=K+qr=9+2·13=35. Распределяемые числа r и передаются всем пользователям, которые определяются как K_i≡K′_I mod p_i,i=1,2,…,n. Итак, К_i≡35mod17=1, K₂≡35mod19=16, К₃≡35mod23=12. По любым двум их этих чисел можно восстановить ключ К, а в общем случае количество выборок определяется сочетанием из n элементов по L - подмножество мощности L исходного конечного множества мощности n. Число сочетаний из n элементов по L обозначается и равно .

Например, для K₁ и К₃ имеем K′₁≡1(mod17), K′₃≡12(mod17). На основании Китайской теоремы об остатках восстановим К и определим ключ

Используя метод ортогональных базисов, восстановим ключ К. Вначале определим К′≡(К₁В₁+K₁B₃)mod(p₁p₃), где B₁ и В₃ - ортогональные базисы. По определению ортогональные базисы могут быть представлены в виде: B₁=m₁p₃,B₃=m₃p₁, где m₁ и m₃ - веса базисов соответственно B₁ и B₃. Причем m₁ и m₃ выбираются из сравнений m₁p₃=1modp₁,m₃p₁=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 могут быть представлены с помощью L цифр со смешанными основаниями. Отображение из СОК в обобщенную позиционную систему счисления (ОПСС) может быть определено рекурсивно с помощью операций по малым модулям р_i.

Для перехода от вычислений по модулю к вычислению по модулям р_i предлагается метод восстановления чисел на основе совместного использования КТО и ОПСС.

Пусть задана система оснований p₁,p₂,…p_n с диапазоном Р=p₁·p₂·…·p_n и ортогональными базисами B₁, В₂,…,В_n, веса которых m₁,m₂,…,m_n, которые определяются как

где m_i - веса ортогональных базисов.

Тогда КТО можно представить в виде

где α - остатки (вычеты) числа Х по mod p_i; R(x) - ранг числа.

Представим ортогональные базисы B_i в ОПСС, тогда

b_ij- коэффициенты ОПСС; i,j=1,2,…,n.

На основании (4) запишем Х_ОПСС выражение (3) в виде

Так как B_i mod p_i=0, ∀j>i, то перед первым значащим разрядом будет i-1 нулей.

Для удобства вычислений базисы можно представить в виде матрицы

При использовании традиционной вычислительной базы произведения α_ib_ij mod p_i, можно поместить в память, а адресами будут являться остатки α′₁.

Если вычислительная база представлена в нейросетевом базисе, тогда в качестве весовых коэффициентов нейронной сети будут выступать b_ij, а в качестве входных сигналов - остатки α′_i.

Для выборки всех цифр ОПСС требуется две операции: одна операция выборки из памяти и одна операция для суммирования. По сравнению с известным методом Гарнера выигрыш определяется выражением Для реализации этого метода в нейропроцессоре необходимо иметь средства для выполнения модульных операций, например, нейронные сети конечного кольца по р_i основаниям, где i=1,2,…n.

Пример 2. Пусть основания системы p₁=3, р₂=5, р₃=7, p₄=2. Дано число х=(2,3,0,1), представленное в СОК по выбранным модулям. Найти представление этого числа в ОПСС, то есть х=[α′₁,α′₂,α′₃,α′₄]. На основании выражения (5) определим ортогональные базисы СОК: B₁=70, В₂=126, В₃=120, B₄=105. Представим базисы B_i в ОПСС, тогда b_ij:

В связи с тем, что константы b_ij определяются выбором системы

модулей СОК, то их с учетом переноса в 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=1,2,…,n) числа подаются падаются параллельно через входной слой нейронов на входы всех НСКК р_i, которые имеют n² синаптических весов. Подключения синаптических весов на чертеже показаны точками. НСКК p_i реализует треугольную матрицу (9) путем сложения цифр в представлении ОПС, описанному выше, т.е. данные в i-канале будут суммироваться с учетом переносов в канале по модулю р_i в представлении ОПСС. Перенос представляет собой число раз, превышающее величину модуля р_i, который поступает к (i+1) каналу. Поскольку в каждой строке имеется (i-1) нулей перед первым значащим элементом, а сумма чисел может переноситься (n-1) раз, то абсолютная величина каждого переноса ограничивается величиной (n-1)

где w_ij=b_ij.

Для восстановления ключа, представленного в позиционной системе счисления, используется реконфигурационная структура, которая определяется конфигурацией используемых каналов на данной сети. При формировании структуры, когда происходит реконфигурация сети, возникают две задачи: первая задача связана с исключением i-каналов, а вторая - с коррекцией весовых коэффициентов w_ij. Структура нейронной сети зависит от номеров исключаемых каналов и адаптируется к нему посредством загрузки весовых коэффициентов w_ij. В то время когда часть сети остается неактивной (исключаемой из системы), весовые коэффициенты между нейронами входного слоя и нейронами скрытого слоя НСКК не используются нейронной сетью и равны нулю. Весовые коэффициенты между нейронами скрытого слоя и нейронами выходного слоя НСКК не активизированных нейронов также равны нулю, а нейроны выходного слоя не активированной части нейронной сети имеют высокое значение (преимущественно ∞), т.е. можно считать, что они исключаются из общей системы.

Посредством коммутации весовых коэффициентов нейронная сеть осуществляет реконфигурацию системы и ее настройку в соответствии с изменением констант СОК. Определенные активированные части нейронной сети активируют другие части, при этом весовые коэффициенты определены из новых констант СОК. В процессе реконфигурации активные нейроны целенаправленно активируют определенные части нейронной сети, просто и быстро приспосабливаясь к определенным внешним параметрам. Таким образом, в процессе вычисления весовые коэффициенты активированной части нейронной сети адаптируются к требованиям внешних параметров. Исходя из этого вычисления нейронная сеть не содержит каких-либо сложных условий реконфигурации системы и вследствие этого происходит быстрое определение значений величины выбранного варианта сети.

Функционирование нейронной сети зависит от весовых коэффициентов между слоями, которые определяются заранее и хранятся в ПЗУ_ф формирования весовых коэффициентов.

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

Весовые коэффициенты определяются заранее и помещаются в ПЗУ_ф формирования весовых коэффициентов при реконфигурации, и в зависимости от поступающих сигналов выдаются необходимые весовые коэффициенты для конкретных вариантов, соответственно определяя структуру нейронной сети, в которой при определенных внешних параметрах достигается надежное и быстрое вычисление двоичного кода ключа.

НСКК p_i преобразуют числа , представленные в остаточном коде в код ОПСС, при этом число представляется в виде, соответствующем ОПСС, следующим образом , где - называется коэффициентом ОПСС, причем 0≤≤р_i. Весовой коэффициент, связанный с каждой цифрой ОПСС равен p₁p₂…p_i-1. Такая система имеет тот же диапазон представления, что и СОК

Р=р₁р₂…р_n. Коэффициенты кода ОПСС являются адресами памяти, где хранятся значения произведений p₁p₂…p_i-1. Двоичные эквиваленты значений p₁p₂…p_i-1, хранящиеся в памяти, поступают на вход сумматора, где по остаткам восстанавливается двоичное число. Для определения кода ключа на вход сумматора поступает поправка, представляющая произведение чисел - rq, которая формируется ПЗУ_n, а адресом является число r.

Распределенные числа , представленные в СОК своими остатками (вход 1), по модулям p_i (i=1,2,…,L) поступают на входной слой нейронов 2, а число r 11 поступает на адресные входы ПЗУ_n. Выбранный вариант реконфигурации определяется сигналом реконфигурации 10, подаваемым на вход ПЗУ_ф. Входной слой связан с L НСКК. При выбранных модулях СОК структура нейронной сети зависит от одного внешнего параметра и адаптируется к нему посредством загрузки весовых коэффициентов w=w_ij=b_ij7, определенных выражением (4, 6). НСКК_Pi i=1,L реализуют вычислительную модель (7), на выходах которых формируются коэффициенты ОПСС числа х. Коэффициенты являются входными адресами ПЗУ p_i 4, где хранятся двоичные эквиваленты K_ip₁p₂…p_i-1. Считанные из ПЗУ p_i двоичные коды, соответствующие произведению K_ip₁p₂…p_i-1, суммируются взвешенным сумматором 5, на выходе которого формируется двоичный код 6. Время преобразования кода определяется L-тактами синхронизации. Структура преобразователя, реализованная на СБИС, требует n - НСКК по модулям p_i, каждое из которых хранит p_i слов разрядностью, эквивалентной числу (p_i-1)p₁p₂…p_i-1, и одного параллельного сумматора с ускоренным переносом. Сумматор может быть реализован по типу дерева, тогда время преобразования определяется выражением [logn]+1, где n - число модулей СОК.

Кроме того, на вход сумматора подается число - rq в дополнительном коде, выбранном по адресу r 11 из ПЗУ_n. Дополнительный код использован для замены операции вычитания операцией сложения при реализации модели (1).

Рассмотрим числовую интерпретацию примера 1, реализованную архитектурой, приведенной на чертеже. Число всех пользователей n=3, а число пользователей сети

L=1. При этом распределяемые числа поступают на вход нейронов входного слоя, а r - на вход ПЗУ_n в качестве адресных входов. На вход ПЗУ_ф поступает сигнал реконфигурации. В соответствии с =1, =12 ПЗУ_ф осуществляет конфигурацию нейронной сети путем подачи соответствующих весовых коэффициентов, которые определяются на основе значений , где L=2,3,…, n-1; j∈{2,3,…,L}; L⊂n;

- число сочетаний из n по L. На основе (4) определим b_ij, тогда b₁₁=1, b₁₃=4 и b₂₁=0, b₂₃=19. Представим b_ij в виде таблицы на основе (6), тогда

Выражение для данной конфигурации системы K^'=b₁+b₂17, тогда получим значения для коэффициентов ОПСС

Итак, K^'=1+2·17=35.

Значения X_опс=[1, 2] являются адресными входами ПЗУ₁ и ПЗУ₃. На выходе ПЗУ₁ формируется число, равное 1, а на выходе ПЗУ₃ - число, равное 2·17=34. В сумматоре эти значения суммируются 1+34=35, из которого вычисляется значение rq=2·13=26. Все операции в сумматоре выполняются в дополнительном коде. Так как используются положительные целые числа, то дополнительный код числа равен самому числу. Итак, код ключа равен К=35-26=9.

Нейронная сеть с пороговой (n, t) структурой для преобразования остаточного кода в двоичный позиционный код работает следующим образом.

Входное число 1, представленное в СОК своими остатками по модулям p_i(i=1,2,…,n), поступает на входной слой 2. Входной слой связан с n НСКК в соответствии с заданной реконфигурацией, которая зависит от одного внешнего параметра и адаптируется к нему посредством загрузки весовых коэффициентов w 7, формируемых ПЗУ_ф 8 по сигналу реконфигурации 10 и определяемых выражением (4). НСКК p_i 3 реализует вычислительную модель (7), на выходе которых формируются коэффициенты ОПСС числа x. Коэффициенты являются адресными входами ПЗУ_pi 4, где хранятся двоичные эквиваленты . Считанные из ПЗУ_pi двоичные коды, соответствующие произведениям суммируются взвешенным сумматором 5 с учетом поправки - rq, формируемой ПЗУ_n 9 по сигналу поправки 11. На выходе 6 формируется двоичный код ключа. Время преобразования определяется n+1 тактами синхронизации. Структура нейронной сети с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код требует n - НСКК по модулям р_i, n - ПЗУ_pi, каждое из которых хранит р_i слов разрядностью, эквивалентной числу p_i-1p₁p₂…p_i-1, одного параллельного сумматора с ускоренным переносом, одного постоянного запоминающего устройства формирования весовых коэффициентов при реконфигурации, хранящего весовых коэффициентов, и постоянного запоминающего устройства формирования поправки, емкость которого определяется произведением .

Изобретение относится к нейронной сети с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код, которая является схемой восстановления позиционного числа по сокращенной системе модулей остаточных классов независимо от того, что часть модулей искажена и они отбрасываются либо часть модулей просто игнорируется. Техническим результатом является расширение функциональных возможностей преобразователя остаточного кода в двоичный позиционный код. Для этого нейронная сеть с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код содержит входной слой нейронов, n - нейронных сетей конечного кольца для преобразования остаточного кода в код обобщенной позиционной системы счисления, n - постоянных запоминающих устройств для хранения двоичных эквивалентов коэффициентов обобщенной позиционной системы счисления, параллельный сумматор, постоянное запоминающее устройство формирования весовых коэффициентов для выбора необходимой конфигурации нейронных сетей конечного кольца и постоянное запоминающее устройство для формирования поправки выходного двоичного кода. 1 ил.

Нейронная сеть с пороговой (k, t) структурой для преобразования остаточного кода в двоичный позиционный код, содержащая входной слой нейронов, n нейронных сетей конечного кольца (НСКК), предназначенных для формирования коэффициентов обобщенной позиционной системы счисления (ОПСС), n постоянных запоминающих устройств для хранения двоичных эквивалентов значений α'_i р₁ р₂…р_i-1 (i=1, 2, …, n) и сумматор, причем входной слой нейронов связан n нейронными сетями конечного кольца, выходы которых связаны с адресными входами упомянутых n постоянно запоминающих устройств для хранения двоичных эквивалентов, причем сумматор предназначен для суммирования двоичных эквивалентов, считанных из n постоянно запоминающих устройств, и формирования на своих выходах двоичного позиционного кода, отличающаяся тем, что в нее введены постоянное запоминающее устройство формирования весовых коэффициентов при реконфигурации нейронных сетей конечного кольца, причем на вход упомянутого постоянного запоминающего устройства формирования весовых коэффициентов поступает выбранный вариант реконфигурации а на выходах постоянного запоминающего устройства формирования весовых коэффициентов формируется набор весовых коэффициентов, которые поступают на НСКК для выбора конфигурации из L НСКК в соответствии с конкретной выборкой сочетаний где L - подмножество конечного множества n, и постоянное запоминающее устройство формирования поправки rq выходного двоичного кода, r - случайное число поправки, q - модуль системы остаточных классов, при этом на вход упомянутого постоянного запоминающего устройства поправки rq поступает случайное число r, а сумматор осуществляет упомянутое суммирование двоичных эквивалентов, считанных из n постоянно запоминающих устройств, с учетом поправки rq, формируемой постоянным запоминающим устройством формирования поправки rq выходного двоичного кода.