НЕЙРОННАЯ СЕТЬ ДЛЯ ОБНАРУЖЕНИЯ, ЛОКАЛИЗАЦИИ И ИСПРАВЛЕНИЯ ОШИБОК В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ Российский патент 2007 года по МПК G06F11/08 G06N3/06 

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

Известно устройство для контроля и исправления ошибок в избыточном модулярном коде (патент №2022472, кл. Н03М 13/00, RU, 1999), состоящее из входного преобразователя кода, выходного преобразователя, блока группы элементов сравнения, блока группы элементов ИЛИ, блока элементов И.

Однако данное устройство обладает следующими недостатками:

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

Наиболее близким по технической сущности к заявленному устройству является устройство для обнаружения и исправления ошибок в системе остаточных классов (А.С. №714399, G06F 11/08, 1980), содержащее два блока модульной свертки, причем первый выход регистра соединен со входом первого и второго блоков модульной свертки и с первым входом третьего сумматора, выходы первого и второго блоков модульной свертки соединены соответственно с первыми входами первого и второго сумматоров, второй и третий выходы регистра соединены соответственно со вторыми входами первого и второго сумматоров и со вторым и третьим входами третьего сумматора, выход блока памяти соединен с четвертым входом третьего сумматора, выход которого является выходом устройства.

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

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

Поставленная цель достигается тем, что устройство содержит нейронную сеть 8, состоящую из нейронных сетей конечного кольца 4, 5 и 6 и нейронных сетей конечного кольца 27, 28, которые формируют остатки по контрольным модулям системы остаточных классов, выходы 9 которых соединены с первыми входами нейронных сетей конечного кольца 10, 11 вычисления синдрома ошибки, вторые входы которых соединены с выходами нейронов 23 избыточных модулей α_n+1 и α_n+2, выходы нейронных сетей конечного кольца 10, 11, шины 12 и 13 связаны со входами блока памяти 14 для выбора из нее констант ошибок, выходы 15, которые поступают на шины 16, 17 и 18, определяющие номер неисправного модуля (канала), и на вход элемента ИЛИ 19, выход 20 которого определяет наличие ошибки, кроме того, выходы блока памяти 14 поступают на первые входы нейронных сетей конечного кольца 21, а на вторые входы которых поступают остатки неправильного числа α₁, α₂,...,α_n. Исправленное число с выходов нейронных сетей конечного кольца 21 поступает на выходы 22 устройства.

Рассмотрим метод коррекции ошибок.

Пусть дано контролируемое число А=(α₁, α₂,...,α_n, α_n+1, α_n+2), где

α_i=Amodp_i∀i=1, 2,..., n+2, р₁,р₂,...,р_n,р_n+1,р_n+2 - основания СОК с двумя избыточными основаниями р_n+1, р_n+2.

Принцип обнаружения, локализации и исправления ошибки основан на функциональном объединении всех трех операций в одну операцию. Данный метод основан на определении цифр по избыточным основаниям на основании цифр по рабочим основаниям и сравнении их с изначально известными цифрами по избыточным основаниям. Если вычисленные цифры α'_n+1 и α'_n+2 по контрольным разрядам равны исходным цифрам α_n+1 и α_n+2 этих разрядов, то ошибки нет, если они не равны, то необходимо определить синдром ошибки, равный разности этих цифр δ₁=(α_n+1-α'_n+1)mod p_n+1 и δ₂=(α_n+2-α'_n+2)mod p_n+2, по значениям которых определяется константа ошибки. Далее суммируя константу ошибки с неправильным числом, которая подобрана таким образом, что неявное место ошибки в числе устраняется. Для локализации ошибки необходимо поразрядно сравнить откорректированное число с ошибочным, и в случае, если α_i-α_i'≠0, определяется ошибочный разряд. Изложенный метод позволяет обнаружить, локализовать и исправить ошибку по одному из информационных каналов.

Вычисление α'_n+1 и α'_n+2 проведем на основе метода расширения системы оснований, который базируется на использовании китайской теоремы об остатках и обобщенной позиционной системе счисления. Рассмотрим вначале расширение на одно основание, а затем обобщим расширение на два основания.

Пусть задана система оснований р₁, р₂,..., р_n с диапазоном Р=р₁·p₂·...·р_n, ортогональными базисами В₁, В₂,...,В_n, веса которых m₁, m₂,..., m_n и определяются из сравнения Расширим систему оснований, добавляя основание р_n+1, тогда диапазон системы станет P_n+1=p_n+1·P, ортогональные базисы системы их веса причем Задача состоит в определении цифры α_n+1 числа А по основанию р_n+1.

Тогда число А в системе оснований р₁, р₂,..., р_n, р_n+1 будет иметь вид

где - диапазон расширенной системы оснований;

- ортогональные базисы расширенной системы оснований.

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

где - коэффициенты ОПСС;

i, j=1,2,...,n.

На основании (2) запишем выражение (1) в виде

Из выражения (3) можно определить коэффициенты α_i числа А, тогда

где α_i - вычеты числа А по mod p_i;

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

Цифры α_i в представлении ОПСС получаются суммированием по модулю p_i всех произведений и переносом, генерируемым при формировании α_i-1. Перенос генерируется как число раз, когда сумма цифр в ОПСС переполняется по модулю p_i. Этот перенос используется для формирования цифр α_i+1. Последний перенос, генерируемый при получении последней цифры числа в ОПСС, отбрасывается. Предлагаемый метод выполняется в параллельном режиме. Выигрыш в быстродействии данного метода с итеративным методом очевиден, поскольку он уменьшает время преобразования с 2(n+1) циклов синхронизации до трех циклов.

Цифры α_i, принимают значения от 0 до p_i-1, причем являются константами, поэтому произведение α_i можно поместить в ПЗУ или в весовые коэффициенты связей между нейронами. Адресами произведений α_i являются вычеты α_i числа А по модулю p_i.

Пример 1. Пусть р₁=2, р₂=3, р₃=5, p₄=7, P_n+1=2·3·5·7=210, B₁=105, B₂=70, B₃=126, В₄=120.

Тогда на основании (2) определим :

Рассмотрим перевод числа из СОК в ОПСС.

Пусть А=11=(1, 2, 1, 4). Тогда в ПЗУ поместим значения α_i, :

Преобразование числа A из СОК в ОПСС имеет вид

При сложении цифр по каждому модулю с учетом переноса получим число А, представленное в ОПС как А=[1,2,1,0].

Рассмотрим метод определения вычета по расширенному основанию. Пусть СОК состоит из оснований р₁, р₂,...,p_n. Объем диапазона этой системы будет Добавим к числу оснований СОК новое основание p_n+1. Объем диапазона этой системы Тогда любое число А из диапазона [0, Р_n+1] в обобщенной позиционной системе счисления можно представить в виде

Если число А будет лежать в первоначальном диапазоне [0; Р], то в ОПСС цифра α_n+1=0. Если α_n+1≠0, тогда значение числа А выходит за пределы динамического диапазона. Факт α_n+1=0 используется для получения остатка (вычета) от деления числа А на новое основание СОКр_n+1.

Пусть число А имело представление (α₁, α₂,..., α_n) по основаниям р₁, p₂,..., р_n. Добавляем новое основание p_n+1, тогда число в системе оснований p₁, р₂,..., р_n, p_n+1, где - остаток от деления числа А на р_n+1, т.е. искомая цифра по новому основанию.

Для определения этой цифры используем метод перевода числа из СОК в ОПСС, включая неизвестную цифру в проводимые операции. При этом мы параллельно получим цифры ОПСС α₁, α₂,...,α_n и выражение для цифры α_n+1. Но так как по условию число А∈[0;P], то цифра α_n+1=0.

Из полученного соотношения и определяем искомую цифру

Пример 2. Пусть задана система модулей р₁=2, р₂=3, p₃=5, тогда P=2·3·5=30. И пусть задано число А=11=(1, 2, 1). Расширим систему оснований, добавляя р₄=7. Тогда А=11=(1, 2, 1, |А|₇) в системе оснований p₁=2, р₂=3, р₃=5, р₄=7.

Набор констант b_ij приведен в (5) и задается матрицей

Процесс решения задачи приведен в таблице 1.

Таблица 1Вычеты числа А по модулю p_iМодулиp₁=2p₂=3p₃=5p₄=7111232042410014|A|₇0004·|х|₇Коэффициенты ОПСС числа A1215+4·|х|₇

После сложения цифр по модулю p_i получим А=[1, 2, 1, 5+4|A|₇], но так как α₄=|5+4·|А|₇|₇, но по условию α₄=0, т.е. 4·|А|₇=-5 или . Мультипликативная обратная величина , и так как число 5 отрицательное, возьмем его дополнение по модулю 7. Итак, вычет числа А по модулю 7 определяется выражением |А|₇=2·(7-5)=4.

Тогда расширенное представление числа будет A=11=(1, 2, 1, 4). Так как результат образования цифры в СОК по новому основанию р_n+1 зависит только от информационных разрядов, то операцию расширения вычетов можно проводить сразу по нескольким дополнительно введенным основаниям.

Пример 3. Пусть задана система оснований (модулей) СОК р₁=2, р₂=3, р₃=5. Расширим систему оснований, добавляя р₄=7, р₅=11. Тогда в выражение (5) добавляется еще один столбец и одна строка, а именно

Пусть задано число А=17=(l,2,2,|A|₇, |А|₁₁), необходимо найти остатки по основаниям р₄=7, р₅=11.

Процесс решения приведен в таблице 2.

Таблица 2Вычеты числа А по модулю р_iМодулиp₁=2p₂=3p₃=5р₄=7p₅=1111123520424143002840004|A|₇-000-7|A|₁₁Коэффициенты ОПСС числа Aα₁=1α₂=2α₃=2α₄=2+4|A|₇α₅=2+7|A|₁₁

После сложения цифр по модулю p_i получим

А=[1,2,2,2+4|А|₇,2+7|А|₁₁],

но так как α₄=2+4|A|₇,а α₅=2+7|A|₁₁, и по условию α₄=0 и α₅=0, тогда

Мультипликативные величины

Так как |А|₇=-4, а |А|₁₁=-5 возьмем их дополнения, т.е. |A|₇=7-4=3, а |A|₁₁=11-5=6.

Тогда расширенное представление числа будет равно информационному числу, т.е. А=(1,2,2,3,6)₁₁, и это говорит о том, что число А безошибочное.

Преимущества предложенного метода расширения системы вычетов состоит в том, что:

- все вычисления выполняются в параллельных каналах по отдельным модулям, причем каждый модуль отождествляется с отдельным каналом;

- не требуется вычисления большого количества дополнительных величин, необходимо только наличие констант и мультипликативных величин по расширенным основаниям;

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

Применим этот метод для обнаружения, локализации и исправления ошибки.

Коррекция ошибок в СОК основана на представлении числа в расширенной системе. В качестве расширенных оснований возьмем избыточные (контрольные) основания. Допустим, в процессе обработки и хранения данных в вычислительной системе остатки чисел по избыточным основаниям, с одной стороны, абсолютно верны, а с другой стороны, они вычисляются на основе остатков по неизбыточным (информационным) основаниям, непосредственно перед контролем данных. Если вычисленные избыточные остатки равны исходным, то ошибки в информационных основаниях не произошло, в противном случае - произошла ошибка по информационным основаниям. На основании этой информации устраняется ошибка и определяется неисправный модуль.

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

Пример 4. Исходные данные такие же, как и в примере 3.

Допустим, произошла ошибка по третьему информационному основанию, тогда ошибочное число будет иметь вид =(1,2,3,3,6).

Избыточные разряды по четвертому и пятому основаниям равны соответственно 3 и 6, и они абсолютно верны.

На основании информационных остатков определим синдром ошибки δ.

Метод обнаружения, исправления и локализации ошибок в СОК представляется следующим образом.

Контролируемое число α₁, α₂,...,α_n, α_n+1, α_n+2 делится на две части: информационную, в которую входят остатки по информационным основаниям α₁, α₂,..., α_n, и контрольную часть, в которую входят остатки по избыточным (контрольным) основаниям α_n+1, α_n+2.

Далее по остаткам информационных каналов определяем остатки по избыточным основаниям. Воспользуемся таблицей 2, тогда третья строка будет иметь вид не [0, 0, 2, 8, 4], а [0, 0, 3, 12, 6].

При выполнении операции согласно таблице 2 получим

Отсюда

Используя найденные остатки, определяем синдром ошибки:

По величинам δ₁, δ₂ формируются константы ошибок таким образом, что при их сложении с информационными разрядами контролируемого числа А имевшая место ошибка в числе устраняется. Заметим, что если контролируемое число не будет содержать ошибки, то величины δ₁ и δ₂ равны нулю.

Для локализации ошибки необходимо провести сравнение разрядов исходного числа с исправленным числом и по тому разряду, где сравнение не выполняется, определяется ошибочный разряд.

Определим константы ошибок для данного примера и сведем их в таблицу 3.

Таблица 3
Константы ошибок для СОК с основаниями р₁=2, р₂=3, р₃=5, p₄=7, p₅=11Ошибка по основанию р₁δ₁, δ₂Ошибка по основанию р₂δ₁, δ₂Ошибка по основанию p₃δ₁, δ₂0,0,00,00,0,00,00,0,00,01,0,06,7
1,40,1,01,2
3,100,0,14,9
6,60,0,23,4
5,1  0,2,04,1
6,90,0,34,7
2,100,0,41,5
3,2

В соответствии с δ₁=1, δ₂=5 таблицы 2 определяется величина ошибки (0,0,4), которая складывается с контролируемым числом

По величине ошибки (0,0,4) локализуется ошибочный разряд, им будет разряд по modp₃. Использование синдрома ошибки позволяет все процедуры по обнаружению, локализации и исправлению ошибок объединить в одну процедуру, что позволяет уменьшить время коррекции ошибок и повысить эффективность.

На чертеже приведена нейронная сеть для обнаружения, локализации и исправления ошибок в системе остаточных классов. Нейронная сеть состоит из входного слоя нейронов 2, 23, входного слоя 24, предназначенного для хранения остатков числа по рабочим и контрольным основаниям в течение времени обнаружения ошибки, вход которой соединен со входами 1(α₁, α₂,..., α_n) и входами 25(α_n+1, α_n+2) нейронной сети; нейронной сети 8, предназначенной для вычисления остатков чисел по контрольным основаниям, входы которой соединены с выходами нейронов 2, хранящими остатки по рабочим основаниям; нейронных сетей конечного кольца 10, 11, предназначенных для вычисления синдромов ошибки по контрольным основаниям, первые входы которых соединены соответственно с выходами нейронной сети вычисления остатков по контрольным основаниям, а вторые - соответственно с выходами нейронов 23, хранящие остатки по контрольным основаниям, входы которых подключены к шине 25; блок памяти 14, предназначенный для хранения констант, вход которого соединен с выходами нейронных сетей конечного кольца 10, 11; нейронных сетей конечного кольца 21, предназначенных для получения исправленного числа путем суммирования неправильного числа с константой ошибки, первые входы которых соединены соответственно с выходами блока памяти, шины 15, которые являются выходными шинами 16, 17 и 18, формирующие номера неисправных модулей и входом элемента ИЛИ 19, выход 20 которого формирует сигнал "есть ошибка", а вторые - с выходами нейронов 2, а выходные сигналы 22 нейронных сетей конечного кольца 21 являются выходами нейронной сети исправления ошибок.

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

На входы 1, 25 нейронов 2 и 23 нейронной сети для обнаружения, локализации и исправления ошибки в системе остаточных классов подается контролируемое число А=(α₁, α₂,...,α_n, α_n+1, α_n+2). С выходов нейронов 2 остатки по рабочим основаниям с весовыми коэффициентами w_ij 3 поступают на вход нейронной сети 8 вычисления остатков по контрольным модулям. Нейронная сеть 8 состоит из совокупности нейронных сетей конечного кольца 4, 5, 6. Весовые коэффициенты w_ij 3 и w_jk 7 нейронов нейронных сетей конечного кольца, выполняющие роль распределенной памяти, определяются соответственно и w_jk=1. Нейронные сети конечного кольца 4, 5 и 6 реализуют вычислительную модель, представленную в таблице 2.

Выходные сигналы НСКК 5 и 6 последней строки поступают на вход НСКК 27 и 26, с весовыми коэффициентами w_kl 29, равные где l - количество расширяемых модулей и принимает значение 1,2,....

Выходные сигналы 9 НСКК 27 и 28 будут отрицательными значениями: -α'_n+1 и -α'_n+2, которые поступают соответственно на входы 9 НСКК 10 и 11, а на вторые входы поступают значения α_n+1 и α_n+2 по шинам соответственно 30 и 31. НСКК 10 и 11 реализуют вычислительную модель:

δ₁=α_n+1-(-α'_n+1);

δ₂=α_n+2-(-α'_n+2).

Выходные значения НСКК 10 и 11 по шинам 12 и 13, соответствующим синдромам ошибки, поступают на входы блока памяти 14 и выбирают оттуда соответствующую константу согласно таблице 3. Эти константы с выхода блока памяти 14 по шинам 15 поступают на соответствующую шину 16, 17 и 18, которые показывают номер неисправного модуля, а также на вход элемента ИЛИ 19, выход 20 которого показывает наличие ошибки. На входы НСКК 21 поступает сигнал с выхода блока памяти, а на вторые входы поступают соответственно выходные сигналы рабочих каналов, нейроны 3, выходная шина 26, где суммируются с константами ошибок, подобранными таким образом, что при ее сложении с контролируемым числом А имевшая место ошибка в числе устраняется. На выходе НСКК 21 выходная шина 22 формирует исправленное число.

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

Нейронная сеть для обнаружения, локализации и исправления ошибок в системе остаточных классов (СОК), содержащая входной слой нейронов, на входы которых подается контролируемое число А=(α₁, α₂, ..., α_n, α_n+1, α_n+2), где α_i=Amod p_ii=1, 2, ..., n+2, р₁, ... р_n - рабочие основания СОК, р_n+1, р_n+2 - контрольные основания СОК, блок памяти, элемент ИЛИ, n выходных нейронных сетей конечного кольца, отличающаяся тем, что, ней выходы нейронов входного слоя по рабочим основаниям разветвлены соответственно на первые входы выходных нейронных сетей конечного кольца, предназначенных для получения исправленного числа путем суммирования неправильного числа с константой ошибки, и на входы нейронной сети, предназначенной для вычисления остатков α'_n+1 и α'_n+2 по контрольным основаниям, выходы которой соединены с входами нейронной сети формирования отрицательных значений остатков по контрольным основаниям, выходы которой подключены соответственно к первым входам нейронных сетей конечного кольца определения синдрома ошибки δ₁=|α_n+1-(-α'_n+1)|_p+1 и δ₂=|α_n+2-(-α'_n+2)|_p+2, выходы нейронов входного слоя по контрольным основаниям подключены соответственно на вторые входы нейронных сетей конечного кольца определения синдрома ошибки, выходы которых соединены с адресными входами блока памяти, в котором хранятся константы, определяемые синдромами ошибок δ₁ и δ₂, выходы блока памяти подключены к шинам определения основания по которому произошла ошибка и к элементу ИЛИ, формирующему сигнал «есть ошибка», а также соответственно к вторым входам n выходных нейронных сетей конечного кольца, выходы которых являются выходами нейронной сети обнаружения, локализации и исправления ошибок в СОК.