авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 |

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Левченко, Александр Юрьевич Разработка нейронных моделей для коррекции ...»

-- [ Страница 3 ] --

N/^ показывает на какое ко личество кодовых (правильных) верщин необходимо переместиться (т.е. ка кое количество дуг необходимо пройти) в направлении от AN^^ к ANQ, чтобы по весу полученной вершины заключить о расстоянии между числами AN^^ и ANi^. К примеру, определяя арифметическое расстояние между N^ и Ni^, с учетом того, что N^ = 3N2 и вершина N2 расположена ближе к NQ, чем вер шина Nf, (ЛГ,8 =3//б), имеем: перемещаемся, пройдя две дуги, из /^jg в Л 1 и, ^ ' поскольку w(iV,2) = 2, заключаем, что расстояние между Nf^ и N^^ равно В силу вышесказанного, взяв за основу, например, вторую модель кода СОК, для кода 37^-СОК, где код СОК задан основаниями р, =2, Рг =3 (при чем р^ - избыточный модуль), можно предложить модель, изображенную на рисунке 2.3.8. Несмотря на то, что расстояние между кодовыми словами З ^ Л^ и 2Nj будет равно сумме арифметических расстояний между равноостаточ ными вершинами по каждому основанию (в каждой окружности, опреде ляющей соответствующий модуль), которые были учтены при перемещении из точки ЪЫ^ к точке ЗЛ/^^, с учетом используемых алгоритмов коррекции ошибок приходим к следующему. Между двумя кодовыми словами кода AN Рис. 2.3.8. Геометрическая модель кода AN-СОК с двумя основаниями СОК целесообразно ввести два расстояния: одно, d^, обусловлено конструк цией кода СОК, (при этом, di[ANi,ANj)=d[Ni,Nj)), другое же, d2, определен но наличием ЛЛ'^-кода. Расстояние ^2 разумно определять (так это было ука зано для кода AN -СОК, построенного на базе безызбыточного кода СОК) как арифметическое расстояние между ЛЛ/^-остатками по определенному моду лю, причем для каждого основания в отдельности.

Найдем расстояние между числами ЗЛ^з и 3N4, являющимися кодовыми словами кода 3N -СОК, геометрическая модель которого представлена на ри сунке 2.3.8. Отметим, что в исходном коде СОК, заданным модулями pj = 2 и Р2 = 3, соответствующие числа имели вид Л^з = (l,o), Л 4 = (ОД)» т.е. расстояние ^ ' между ними в коде СОК было равно 2, что совпадает с числом дуг, которые следует пройти при движении из точки ЗЫ^ к точке 3N^ (З//3 -^37/о -3N^ или 3iV3 -^3Ni -ЗЛ^4) и, следовательно, ^,(3//з'ЗЛ^4) = 2. В коде 3//-С0К чис ла примут вид 37/з=(|3-3|б,|3-3|^)=(3,0)=(11,000), = (0,1) = (00,011). А поскольку j(ll,OO) = 4lOl,OOo)=2 и = c/(0000,010l)=2, то /(ЗЛ^з.ЗА^4) = 2 + 2 = 4. Однако в силу вышеска занного целесообразнее говорить о арифметических расстояниях по каждому основанию в отдельности: с/^^^(злГз,ЗЛ^4) = 2, «/^^^^(ЗЛ^з'ЗЛ^4) = 2.

Таким образом, в параграфе 2.3 рассмотрена существующая и предложены две новые геометрические модели кода СОК. Кроме этого, в параграфе пред ложены геометрическая интерпретация перевода чисел из кода СОК в гиб ридный код AN-СОК (и обратно), а также геометрические модели кода AN СОК.

ПО 2.4. Оценка увеличения длины двоичного кода, обусловленного нере ходом от кода СОК к гибридному коду.

Переход от двоичного кода СОК (безызбыточного или корректирующего) к гибридному коду ^iV-COK, при условии, что последний использует все ос нования исходного кода СОК, связан с некоторым увеличением длины кода (количества двоичных символов, необходимых для изображения числа N ).

Оценим величину этого увеличения.

Длина кода СОК, представленного основаниями р,, Р2,..., /?*, равна сум ме откуда с учетом определения целой части числа получим т.е.

Длина гибридного кода, представленного основаниями р,, p j,..., /7^ с со ответствзжэщимигенераторами ^iV-кодов /1,, /ij» •• Л, равна • k ^Гибрид = Z[l0g2 ^iiPi - 1 ) + I j ' откуда имеем к т.е.

Ь (2.4.2) Из неравенств (2.4.1), (2.4.2) следует, что Z Iog2 4- (P/ -1) - Z l0g2 {pi-l) + k\ L Гибрид - LcOK Z l0g2 4 (P/ " 0 + ^ " Z Iog2 (/?/ " 0 •,=1 V«=l /=I J i=\ Используя свойства логарифмов, после несложных преобразований послед няя формула примет вид к к SIog2 Ai-k Ьгибрид -LcoK S 1о§2 Ai+k. (2.4.3) Таким образом, полученная формула (2.4.3) является оценкой увеличения количества двоичных символов, необходимых для изображения числа Л^, где 7/е p,ji[/,-1, обусловленного переходом от двоичного кода СОК к гиб ридномукоду Пример. Пусть гибридный код и код СОК, представлены двумя информа ционными основаниями р, = 5 и р^=1.Ъ гибридном коде в качестве генера торов ЛА/^-кода возьмем числа Л, =13 и ^2=19, что обеспечит обнаружение двух и исправление одного ошибочного двоичного символа в каждом из мо дулей. Поскольку Iog2l3«3,70, а Iog2l9«4,25, то, воспользовавшись форму лой (2.4.3), имеем 5,95 ^гибрид - ^сок 9'95. Па самом же деле, так как LГибрид - LcoK = (6 + 7) - (3 + 3) = 7. Действительно, 5,95 7 9,95.

Пример. Взяв в качестве информационных оснований кода AN-СОК и ко да СОК числа р, =4 и р^=\25^ в качестве генераторов ЛЛ'^-кода - числа Л, =13 и ^2=29, что обеспечит обнаружение двзос и исправление одного ошибочного двоичного символа в каждом из модулей, получим следующее.

Поскольку Iog2l3«3,70, а Iog2 29«4,86, то, воспользовавшись формулой (2.4.3), имеем 6,561^„5/7ид~^сол: 10'5б- На самом же деле, так как [log2(4-l)+l] = 2, [Iog2(l25-l)+l]=7, [Iog2l3.(4-l)+l] = 6, [log2 29.(l25-l)+l] = 12, ^Гибрид - LcoK = (б +12)- (2 + 7) = 9. Действительно, 6,56 9 10,56.

Пример. Пусть гибридный код и код СОК, представлены информацион ными основаниями р, =29, Р2 =74 и р^=\9\. Для обнаружения двух и ис правление одного ошибочного двоичного символа в каждом из модулей в ка честве генераторов Л/^-кода возьмем числа Л, =23, Л2 =23 и Лз =29. Так как 23«4,52, a Iog2 29«4,86, то, воспользовавшись формулой (2.4.3), имеем 10,9 Lp^Qp,^^ - LQOK 16,9. На самом же деле, поскольку [log ^ (29 -1)+1] = 5, TO = (lO +11 +13)- (5 + 7 + 8) = 14. Действительно, 10,9 14 16,9.

Гибрид Ha рисунке 2.4.1 изображено увеличение длины двоичного кода при пере 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 р Рис. 2.4.1. Оценка увеличения длины двоичного кода при переходе от кода СОК к гибридному коду ходе от кода СОК к гибридному коду. Ломанные соединяют точки {х,у), где д:

- диапазон чисел, представляемых в данных кодах, у - увеличение длины двоичного кода при указанном переходе. Верхняя ломаная изображает уве личение с избытком (правая часть неравенства (2.4.3)), нижняя — с недостат ком (левая часть неравенства (2.4.3)), средняя - истинную величину указан ного увеличения. Результаты моделирования позволяют утверждать, что в качестве точечной оценки упомянутого увеличения можно принять середину 1* интервальной оценки (2.4.3.), т.е. L L Итак, в этом параграфе нами получена оценка увеличения количества дво ичных символов, необходимых для изображения числа N, обусловленного переходом от двоичного кода СОК к коду AN-СОК.

2.5. Решение проблемы внутренней нзбыточностн двоичного кода СОК.

Переводя каждый из разрядов представления исходного числа Л в системе ^ ' остаточных классов в двоичную систему счисления, легко заметить, что на ряду с избыточностью кода, обусловленной наличием проверочных основа ний, код СОК также будет иметь и внутреннюю избыточность (для изобра жения каждого из разрядов представления числа количество двоичных сим волов выбирается с запасом;

например, для представления чисел, соответст вующих модулю р = 17, т.е. чисел из диапазона от О до 16, в двоичной систе ме счисления необходимо 5 символов, но с помощью того же количества символов можно изобразить числа из диапазона от О до 31). Ясно, что внут ренняя избыточность будет отсутствовать по основаниям (модулям) кода СОК, представляющим собой степень двойки, но код СОК не может иметь более одного такого модуля, поскольку ни один из модулей не является де лителем другого основания и модули обязаны отличаться друг от друга как минимум одним простым делителем, а в оптимальном случае основания кода вообще являются взаимно простыми числами. Избыточность окажется мак симальной в случае, когда модулем будет число вида 2^ +1, где ^ е Л'^. Ярки ми представителями таких чисел являются так называемые числа Ферма, т.е.

простые числа вида 2^' +1. Минимальной же избыточность будет в случае, когда основанием окажется число вида 2'^ - 1, где q = 2,3,....

Очевидно, что внутренняя избыточность кода СОК является негативной, понапрасну пожирающей аппаратные ресурсы. Для избежания указанного недостатка кода СОК можно предложить использование его модификации гибридного кода AN-СОК.

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

Пусть AN-код в гибридном коде будет лишь в качестве подспорья коду СОК. Воспользуемся ЛЛ'^-кодом как индикатором наличия одиночных оши бок в двоичном представлении остатков по выбранным модулям кода СОК, а для этого достаточно, чтобы генератором AN -кода являлось любое нечетное число. В силу изложенного приходим к тому, что для решения поставленной задачи необходимо и достаточно найти составные числа 2^ - 1. Из нечетности последних следует нечетность их делителей. Пусть 2'^-l = ai*ia2*^ •••••«и*'"-Взяв в качестве генератора AN-кода нечетное число А = а'\ a'f -...-а'', где 1 ^У, Уг...jt т, 1 /^ А,, 5 = l,f, ;

- Л 2 ^ - 1, а ЧИСЛО в качестве основания кода СОК, можно добиться, во-первых, взаимной А простоты модулей исходного кода СОК, во-вторых, мощность множества из быточных чисел будет равна сумме Ai + A2+... + An, где п— количество осно ваний кода. Если же в качестве модуля кода СОК выбрать число +1, то А внутренняя избыточность вообще будет отсутствовать, но, при этом, сохра нить взаимную простоту оснований не удастся: очевидно, что + 1 - чет А ное число.

Перейдем к обоснованию существования достаточного количества состав ных чисел 2^ - 1. В качестве небольшой справки: числами Мерсенна называ ются простые числа вида 2^-1, где q - простое число. К числам Мерсенна относятся самые большие из известных в настоящее время простых чисел, но для дальнейших рассуждений более существенным является тот факт, что ряд чисел Мерсенна довольно разрежен. Из того, что немногие из чисел 2^ - являются простыми, естественным образом следует, что составных чисел та кого вида немало.

Прежде, чем продолжить докажем следующее утверждение.

Теорема. Каждое второе число вида 2'^ -1 (где ^ = 2,3,...) кратно 3.

Доказательство. Доказательство разобьем на две части.

Вначале покажем, что при любом четном q [2'^-lJ:3. Это означает, что требуется доказать справедливость следующего:

(22^-1)3, где k&N, т.е.

(4^-1)3, где k^N, или 4* =1(тос13),где А:еЛ^, откуда I*=l(mod3), где keN, Верность последнего очевидна.

Далее покажем, что при любом нечетном q [2^ -1)^3. Допустим противное:

пусть для некоторого ke^N верно но тогда =l(mod3), 2 = l(mod3).

Последнее неверно, следовательно, допущение ощибочно и теорема доказа на.

Доказанная теорема позволяет с уверенностью утверждать, что, по мень шей мере, осуществимо построение гибридного кода, где в качестве AN кодов задействованы ЗЛ^-коды, для которых разработаны эффективные алго ритмы кодирования и декодирования [28]. Так кодирование для 3//-кода мо жет быть выполнено в виде суммирования кодируемой величины N с ее сдвинутым на разряд влево значением А декодирование заключается в преобразовании пар закодированной величи ны в соответствующие пары искомой величины Л^. К тому же при такой реа лизации гибридного кода внутренняя избыточность, если и не будет отсутст вовать вовсе, будет минимальной, а число необходимых дополнительных разрядов, обусловленных переходом от кода СОК к гибридному коду, равно п, где п- число модулей кода, т.е. по одному разряду на каждый модуль.

Пример. Пусть задан код СОК с основаниями /?i =2, Р2=5, рз =21. Диа пазон чисел однозначно представимых в данном коде есть интервал [0,210).

Для двоичного представления остатков правильного числа требуются 1, 3 и 5 разрядов соответственно для модулей pi, Р2 и рз. Мощность множества избыточных чисел, т.е. множества чисел, не участвующих в двоичном пред ставлении остатков числа из диапазона [0,210), равна 0+3+11=14. Построим гибридный код 3iV-COK, соответствующий заданному коду СОК. Добавив по одному разряду для каждого модуля, получим, что для модуля pi задейство ваны два разряда, с помощью которых изображаются правильные остатки О и 3, аналогично, для Рг - 4 разряда, изображающие правильные остатки О, 3, 6, 9 и 12, для Р2 — 6 разрядов, представляющие правильные остатки О, 3, 6,..., 60. При этом внутренняя избыточность построенного кода имеет мощность равную 0+3+3=6.

Пельзя не отметить, что в отличие от кода СОК, в котором для обнаруже ния ощибки по некоторому модулю необходимо знание всего исходного чис ла А (всех его остатков по модулям данной СОК), при использовании гиб ридного кода обеспечивается параллельность операции обнаружения ощиб ки: по каждому модулю обнаружение ощибки происходит независимо.

В следующей таблице приведен сравнительный анализ кодов СОК и. AN СОК, способных обнаруживать одиночные ощибки по одному модулю.

Таблица 2.5.1. Сравнительный анализ кодов СОК и AN-СОК, обнаружи вающих одиночные ошибки по одному модулю.

СОК AN-COK Достаточное число избыточных 1 оснований Достаточное число избыточных больше разрядов в двоичном представле- п log 2 max {рЛ нии метод нулевизации:

нахождение Число тактов необходимых для п+ остатка по мо ранг числа:

осуществления алгоритма обнару дулю А:

жения ощибки [l0g2« + l] перевод в ОПС: ранг числа:

п умножений, (w-l) сложений, одно нахождение Число операций необходимых для сравнение остатка по мо осуществления алгоритма обнару дулю А:

перевод в ОПС:

жения ошибки п сравнений п умножений, (n-i) сложений, одно сравнение п - число основании кода.

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

Если для получения гибридного кода AN-СОК при кодировании нримене ны у^Л^-коды, обнаруживающие двойные и исправляющие одиночные ошиб ки (с кодовым расстоянием равным 3). Выбор числа А, генератора AN-кот, определяет максимальную величину р основания кода;

в зависимости от то го, 2 или -2 (но не 2) является примитивным элементом простого поля Галуа будет иметь вид ЧИСЛО Р GF{A) где к — неотрицательное целое число такое, что р2.

Итак, если —2 (но не 2) является примитивным элементом простого поля Галуа GF{AI), качестве соответствующего основания число ТО, ВЗЯВ В 2i, в силу осуществляемых построений можно утверждать, что р= мощность множества избыточных чисел по данному модулю в коде AN-СОК будет равна Aj. Если же в качестве соответствующего модуля взять число 2(4-0/2 _j +1, то внутренняя избыточность вовсе будет отсутствовать.

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

2.6. Обнаружение, локализация и исправление ошибок в коде AN-COK.

Пусть каждое из оснований безызбыточного или корректирующего кода системы остаточных классов (кода СОК) представлено в виде двоичного AN кода, т.е. задан код AN-СОК.

Пусть pi, р2,..., Рп — основания кода СОК, Ai, А2,..., А„ — генераторы ЛЛ'^-кодов для модулей pi, р2,..., Рп соответственно. Если числа р,- взаимно нростые, то набор остатков (наименьших неотрицательных вычетов) {а1,а2,...,а„) числа N но выбранным основаниям однозначно задает число N из диапазона [О, D), где D~p^p2-...-Pn, т.е.

N_ или О/ = iV(mod р,), / = 1,«.

Т (2.6.1) LA-J В силу конструкции кода AN-СОК. число Л'^, удовлетворяющее условиям (2.6.1), в коде AN-СОК имеет вид N= Для обнаружения ошибки по /-ому основанию кода AN-СОК может ока заться достаточным нахождение наименьшего неотрицательного вычета дан ного ^iV-остатка но модулю А: если справедливо модульное равенство (2.6.2) (А) = 0, а то логично полагать, что в /-ом ЛЛ'^-остатке ошибки не содержится, а в слу чае не вынолнения равенства (2.6.2) - считать /-ый AN-остаток ошибочным.

Каждый из Л//-остатков кода представлен в двоичной системе счисления, в силу чего полный диапазон чисел, отображаемый данным ^iV-остатком, есть интервал [0,2"')» где w- - количество двоичных разрядов, выделенных, нод /-ое основание. Количество чисел из полного диапазона, для которых справедливо равенство (2.6.2), определяется формулой 2 и, т, = Под процентом обнаруженных ошибок 7/ по /-ому основанию будем по нимать отношение количества чисел, которые могут быть обнаружены при вычислении (2.6.2), к полному объему чисел данного диапазона, т.е.

7]: = 1 -.

2"' Так как по каждому модулю обнаружение ошибок происходит независимо, то общий процент обнаруженных ошибок для кода AN-СОК, построенного на базе кода СОК с п взаимно простыми модулями, равен (2.6.3) П = пт---Пп' Ошибочные ЛЛ'^-остатки можно отбросить, если оставшиеся остатки одно значно определяют исходное число N.

Таким образом, процесс обнаружения, локализации и исправления ошибок в коде AN-СОК может состоять лишь в нахождении остатка от деления / ого ЛЛ'^-остатка на соответствующий ему генератор А;

AN-код,а..

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

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

Пусть задан безызбыточный код СОК с модулями Pi = 2, Р2=З.В качестве генераторов ЛЛ^-кода для каждого основания возьмем Л = 3, что обеспечит возможность обнаружения одиночной ошибки по любому из данных основа ний. Аппаратные затраты будем измерять в числе S разрядов, зарезервиро ванных под каждый из модулей, необходимых для изображения соответст вующего остатка. А под сложностью алгоритма коррекции ошибок будем понимать число различных операций, используемых алгоритмом. Считая, что коды СОК и AN-СОК являются двоичными, получим ^''^'^=1 + 2 = 3, =2 + 3 = 5, откуда относительное увеличение аппаратных затрат при gAN-сок использовании кода AN-СОК равно А = — - ^ ^ — = - = 1,(б). Итак, имеем код AN-СОК, построенный на базе безызбыточного кода СОК (неспособного к коррекции ошибок), обнаруживает одиночные ошибки по каждому из осно ваний, при этом увеличение аппаратных затрат равно 1,(б), а сложность алго ритма коррекции ошибок для кода AN-СОК равна: две операции определе ния остатка от деления (свертки) по модулю А и два сравнения найденных остатков с нулем.

Пусть код СОК задан модулями р\=2, Рг = 3, Рз = 5? где /i и Р2 ~ инфор мационные, а рз ~ проверочное основание. Как и ранее Ai=3,, / = 1,3.

=1 + 2 + 3 = 6, j-^^-co^ =2 + 3 + 4 = 9, откуда А = - = 1,5. Код СОК гаранти ровано обнаруживает одиночные ошибки, при этом, для полной уверенности, необходимо найти 2 проекции (нахождение же п проекций, где п — обшее число оснований, позволит исправить часть чисел, содержащих одиночные ошибки). При нахождении каждой из проекций //,• необходимо выполнить /7-1 умножений, п-2 сложений, одно сравнение, а поскольку операции сло жения и умножения осуш;

ествляются по модулям Р^^ = РхРг --'Pni •-•PI-XPM то и, как минимум, одну свертку [5]. Сложность процедуры вычисления про екций можно значительно уменьшить, используя алгоритм быстрого перево да числа из СОК в ОПС [94], суть которого будет изложена позже в парагра фе 3.1. При этом число операций сложения и умножения, хотя и останется прежним, но осуш;

ествляться операции будут по модулям Pi. Заметим, что при подсчете операций мы считали ортогональные базисы By сокращенной системы оснований (и их представления в ОПС) известными. Итак, слож ность алгоритма равна: 4 умножения, 2 сложения, 2 свертки и 2 сравнения (в "худшем случае": 6 умножений, 3 сложения, 3 свертки и 3 сравнения). Слож ность алгоритма коррекции ошибок для кода AN-СОК равна: 3 свертки и сравнения. (Отметим, что заданный код СОК позволяет исправить 8 чисел.

содержащих одиночную ошибку, таковыми являются 6 = (0,0,l), 7 = (1,1,2), 8 = (0,2,3), 9 = (1,0,4), 26 = (0,2,1), 27 = (l,0,2), 28 = (0,1,3) И 29 = (1,2,4).) Пусть задан код СОК модулями Pi = 2, /?2 = 3, яз = 5, р^=1, где /?,, pj информационные, 2i р^, Р4 ~ проверочные основания. Как и прежде Л, = 3, / = U4. 5*^^^=1 + 2 + 3 + 3 = 9, J'^^"^^'^ =2 + 3 + 4 + 5 = 14, откуда А = — = 1,(5).

метим, что заданный код СОК безусловно способен обнаруживать любые двойные ошибки и исправлять всякие одиночные ошибки. Для обнаружения двойных и исправления одиночных ошибок необходимо вычислить 4 проек ции Л'^,, исключая из заданной системы оснований поочередно по одному мо дулю. Для исправления грунпы чисел, имеюш;

их двойные ошибки, следует вычислить С^ = ~—- проекций Л^,у, исключая из заданной системы основа ний по очереди по два модуля;

при этом вычисление каждой проекции Л,, ^- ' предполагает выполнение п-2 умножений, п-3 сложений. Сложность мето да проекций равна: 12 умножений, 8 сложений, 4 свертки и 4 сравнения (с учетом вычисления проекций Л^,^: 24 умножения, 14 сложений, 10 сверток и 10 сравнений). Сложность алгоритма коррекции ошибок для кода ЛЛ^-СОК равна: 4 свертки и 4 сравнения. (Заметим, что данный код СОК исправляет чисел, содержащих двойную ошибку, таковыми являются, например, 9 = (1,0,4,2) и 188 = (0,2,3,6).) Как было отмечено, можно считать, что операции, выполняемые для лока лизации ошибки в коде СОК, осуществляются в параллельных каналах по модулям р( (/ = 1,п). Окончательный вывод о наличии ошибки и ее местопо ложении делается лишь при знании всех разрядов по избыточным модулям представления проекций в ОПС. Поэтому, переводя рассуждения о сложно сти алгоритма в плоскость элементарных операций, сложность процесса ло кализации ошибки с помощью метода проекций следует определять числом элементарных операций по наибольшему модулю (в нашем случае по моду лю Р4 = " )• Считая, что умножение реализовано с помощью индексов (дискретных ло гарифмов), получим: сложность одного умножения чисел по модулю /?;

сравнима с трудоемкостью сложения чисел по модулю (/?,- -1). Учитывая, что вычислительная модель подразумевает, что операции выполняются в двоич ном коде, заключаем, что сложность одного умножения есть O(log2(p/-l)).

Полагая сложность операции сравнения равной сложности операции сложе ния, т.е. O(log2 Pi), в силу вышеизложенного получим, что сложность процес са локализации ошибки для данного кода СОК равна O(l21og2(6)+81og2(7)+41og2(7)) или O(log2(30129469486639681536)), т.е. порядка 65 элементарных операций.

Рассмотрим при этом в качестве альтернативного корректирующего кода код AN -СОК, использующего лишь информационные основания Pi=2, Р2=3 с генераторами ЛЛ'^-кодов ^j =11 и ^2 =13 соответственно. Используя алгоритм, изложенный в пункте 3.2.3, для локализации ошибок необходимо осуществить 2 свертки и 2 сравнения, т.е. сравнить с нулем 2 вычета по мо дулям Aj AN -остатков представления числа, полученного в результате неко торого преобразования в гибридном коде, а затем, при необходимости, ис править один из разрядов двоичного представления ЛЛ'^-остатка. Учитывая, что вычисления ведз^гся по параллельным каналам в двоичных кодах, проде лывая рассуждения аналогичные ранее изложенным, заключаем: сложность локализации ошибок с помощью гибридного кода составляет O(log2(l3)+l) или O(log2(26)), т.е. порядка 5 элементарных операций.

Для полной картины осуществляемого сравнения конкретного кода СОК с соответствующим кодом AN-СОК, следует отметить, что первый код спосо бен по максимуму правдоподобия произвести локализацию ошибок у 40% чисел полного диапазона, второй же корректно исправляет ошибки у 35% чи сел, однозначно представимых в данном двоичном гибридном коде, длина обоих двоичных кодов равна 9.

Таким образом, по соотношению цена/качество, где под качеством пони маем процент чисел, подлежаших исправлению, а под ценой - ту цену (в ви де числа элементарных операций), которую нам приходиться платить за осу ществление этой коррекции, код AN-СОК безоговорочно (с явным преиму ществом) выигрывает у кода СОК: — = 162,5, «14,29, т.е. рассмотренный код ^iV-COK приблизительно в 11,4 раза эффективнее кода СОК.

Любопытно отметить, что при попытке осуществления локализации двой ных ошибок для выбранного нами кода СОК процент чисел, подлежащих ис правлению, возрастает почти до 48%, однако сложность алгоритма увеличи вается до O(log2(l96319612718888031297)), т.е. составляет порядка 130 элемен тарных операций, откуда получаем «270,83. Тогда соответствующий гибридный код со своим показателем цены/качества 22,86 будет результатив нее кода СОК почти в 19 раз.

Пусть код СОК задан модулями ^i = 2, Р2 = 3, Р2=5, Р4 = 7, Ps = 11 где проверочными основаниями являются Р2, р^, РА И р^. При Л,=3, / = 1,5, 5^^^=1 + 2 + 3 + 3 + 4 = 13, «5'^^-^^^ =2+3 + 4 + 5 + 6 = 20 и А = — « 1,54. Заданный код бесспорно обнаруживает всякие ошибки четвертого порядка и исправля ет любые двойные ошибки, но для этого нужно вычислить с\ проекций //,• и с1 проекций Ny, т.е. осуществить 50 умножений, 35 сложений, 15 сверток и 15 сравнений. Попытка исправить ошибки большего порядка приведет к не обходимости выполнить 75 умножений, 45 сложений, 25 сверток и 25 срав нений. Для кода ЛЛ'^-СОК сложность алгоритма коррекции равна 5 сверток и 5 сравнений. (Обратим внимание, что заданный код СОК позволяет испра вить 1068 чисел, содержаших тройную ошибку, таковыми являются, напри мер, числа 431 = (1,2,1,4,2) и 1070 = (0,2,0,6,3), а также 270 чисел, имеющих че тыре ошибочных остатка, к примеру, это 398 = (0,2,3,6,2) и 1073 = (1,2,3,2,6).) Полученные результаты по числу модульных операций, необходимых для локализации ошибок методом проекций в коде СОК с одним, двумя и че тырьмя избыточными основаниями можно представить в таблицах 2.6.1 2.6.3.

* + Количество оснований кода — 2 4 6 ••• Ф•Ф • ФФ («-1Х«-2) п {n-Xf Таблица 2.6.1. Число модульных операций сложения (+) и умножения (*), необходимых для обнаружения одиночных ошибок методом проекций в коде СОК с одним избыточным основанием * + Количество оснований кода 3 4 5 • ФФ ф ф ф • ф Ф п{п-2) п{п-\) п Таблица 2.6.2. Число модульных операций сложения (+) и умножения (*), необходимых для обнаружения двойных и исправления одиночных оши бок методом проекций в коде СОК с двумя избыточными основаниями Обобщим изложенное. Пусть код СОК задан взаимно простыми основа ниями /?!, /72,..., Pki Pk+i •• Рт ГД^ Pi» P2J •• Рк — информационные, а • •»

Pjt+i •• Рп ~ избыточные (проверочные) модули;

[0,Р) - рабочий диапазон •»

кода, где Р = PiP2-----Pk [0»^) - полный диапазон кода, где D = piP2-...-Pn.B силу того, что выбранные основания кода являются взаимно простыми чис лами заданный код СОК можно называть R -кодом и справедливо следующее утверждение (теорема 1.2.2.4) [77].

* + Количество оснований кода 5 35 6 69 7 119... ••• • •• / ^ч «(«-1)/ -ч / ч и(«-1)/ ^Ч п \ / 2^ ^'' Таблица 2.6.3. Число модульных операций сложения (+) и умножения (*), необходимых для обнаружения четырех и исправления двух ошибок ме тодом проекций в коде СОК с четырьмя избыточными основаниями Теорема. Корректирующий iг-кoд имеет минимальное расстояние ^^ш ^ том и только в том случае, если степень избыточности R = — не меньше про изведения любых d-l оснований заданной системы остаточных классов:

d-\ 7= Полагая, что задана упорядоченная система оснований, т.е.

P\Pl - Рк Рк+1 '" Рп»

теорему 1.2.2А можно изложить и так: корректирующий R-код имеет мини мальное расстояние равное (r + l), с/щь =г + 1, где r = n-k - число избыточ ных оснований кода(/?j(.+i, р^+г • • • Рп) Минимальное расстояние кода является его важнейшей характеристикой, поскольку код, имеющий минимальное расстояние с/^т» способен обнару жить все совокупности из (c/njjn -1) или меньшего числа ошибок и может ис или меньшего числа ошибок.

правлять все совокупности из Схожие закономерности нрослеживаются в коде AN-СОК, который полу чен из /г-кода СОК с основаниями pi, /?2 •• РА» Pk+i^ •• Рп считая, что • •»

коррекция ошибки в коде AN-СОК происходит лишь за счет нахождения вы четов ЛЛ'^-остатков по соответствующим генераторам Л,-;

при этом соответ ствующая величина d^^^ = г +1, где г = п-к — число проверочных модулей.

Отметим, что число d^i^ не является минимальным расстоянием кода AN СОК, но с учетом изложенного алгоритма коррекции ошибок справедливо утверждение: код AN-СОК, имеющий характеристику c/^in, способен обна ружить все совокупности из (а?^;

^ -1) или меньшего числа ошибок (точнее, числа модулей, содержащих г-кратные ошибки, обнаруженные по формуле (2.6.2);

для случая А = 3 речь идет об одиночных ошибках по некоторому ос нованию), и может исправлять все совокупности из \dl^l^ -1) или меньшего числа указанных ошибок.

Относительное увеличение аппаратных затрат с ростом величины инфор мационных и/или проверочных модулей (или с ростом их количества, что подразумевает увеличение значений оснований) зависит от корректирующих способностей, используемых для кодирования остатков, ^iV-кодов и может быть сделано небольшим по величине, а сложность алгоритма коррекции ошибок в коде ЛЛ^-СОК существенно меньше сложности метода проекций: п г/2 г/ свертки И п сравнений против ^С'„{п-1) умножений, Y.Cn{n-i-l) сложений, г/2. г/2.

ХС^ свертки и Х^и сравнений (при желании же исправить ошибки больше /•=1 1= го порядка, нежели порядок гарантируемый значением минимального рас стояния кода, потребуется осуществить SCj!,(«-/) умножений, 1=1 1= сложений, ^С'„ свертки и ^.С„ сравнений).

На рисунке 2.6.1 изображены графики зависимости вероятности обнару жения ошибки от длины кода для кодов СОК и AN-СОК, а на рисунке 2.6.2 — вероятности обнаружения ошибки от сложности алгоритмов коррекции оши бок. При построении графиков полагали следующее: коды СОК и AN-СОК определены одинаковыми информационными модулями (количество кото рых увеличивается);

код СОК обладает двумя избыточными основаниями, такими, что минимальное расстояние кода равно 3, а генераторы ЛЛ'^-кодов.

.

.

.

50 100 150 200 250 300 350 400 Рис. 2.6.1. Графики зависимости вероятности об наружения ошибки от длины кода для СОК AN-COK.

.

.

.

500 1000 1500 2000 2500 3000 3500 4000 4500 5000 с Рис. 2.6.2. Графики зависимости вероятности обнаружения ошибки от сложности алгоритмов коррекции для СОК AN-СОК подбирались так, чтобы вероятность определения ошибки у гибридного кода была не меньше, чем у соответствующего кода СОК. На рисунке 2.6.3 нред ставлены графики зависимости вероятности обнаружения ошибки от длины кода для кодов СОК и AN-СОК, где генераторы Л//-кодов равны 3, 7, И и 17.

0. 450 500 Рис. 2.6.3. Графики зависимости вероятности обнаружения ошибки от длины кода для СОК AN-COK В заключение отметим, что коррекция ошибок в коде AN-СОК, получен ного из избыточного кода СОК, может осуществляться и с учетом структуры соответствующего кода СОК, переход к которому из данного кода AN-СОК реализуется в один такт по несложным алгоритмам (полагая А/ и pi взаимно простыми числами, для получения остатка по i-му основанию pi кода СОК надо найти произведение по модулю /, соответствующего ЛЛ'^-остатка кода ?• ^iV-COK на число, обратное Л,- по модулю pi). Выше установленные форму лы позволяют с уверенностью утверждать, что подобная избыточность для кода СОК является обоснованной, поскольку даже частичная локализация ошибок значительно уменьшит сложность последующей коррекции ощибоч ного вектора.

в этом параграфе проведено сравнение алгоритма коррекции ошибок в ко де AN'СОК и метода проекций, основного метода коррекции ошибок в коде СОК, а также получена формула для определения процента обнаруженных ошибок для кода AN -СОК.

Выводы по главе 2.

1. Предложен гибридный код ^Л'^-СОК, представляющий собой синтез ко дов системы остаточных классов (СОК) и ЛЛ'^-кодов, найдено достаточное условие того, чтобы длина кода AN-СОК была меньше длины кода СОК, считая, что оба кода представлены одними и теми же информационными ос нованиями, а избыточность в гибридном коде достигнута лишь кодировани ем остатков Л//-кодом.

2. Обоснована осуществимость модульных и немодульных операций над числами гибридного кода ^Л'^-СОК, получены формулы для представления числа N, заданного в десятичной системе счисления или в виде систематиче ской записи, в коде AN-СОК, перевода чисел кода AN-СОК в код СОК и об ратно, а также формулы, задающие правила выполнения модульных опера ций над числами в коде AN-СОК.

3. Рассмотрена существующая и предложены две новые геометрические модели кода СОК. Кроме этого, в параграфе предложены геометрическая ин терпретация перевода чисел из кода СОК в код AN-СОК (и обратно), а также геометрические модели кода AN-СОК.

4. Получена оценка увеличения количества двоичных символов, необхо димых для изображения числа Л^, обусловленного переходом от двоичного кода СОК к гибридному коду.

5. Установлена возможность решения проблемы негативной внутренней избыточности двоичного кода системы остаточных классов, используя гиб ридный код, в котором AN-код применяется для обнаружения одиночных ошибок, или обнаружения двойных и исправления одиночных ошибок в дво ичном представлении остатков по выбранным модулям кода СОК.

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

7. Таким образом, в главе 2 получена математическая модель гибридного кода AN-СОК, обладающего гибкой структурой и весьма сильными коррек тирующими способностями, в сочетании с достаточно простыми методами коррекции. Вобрав множество полезных свойств своих «прародителей», ко дов СОК и Л//-кодов, и обладая возможностью совместного их использова ния, код AN-СОК является мощным средством борьбы с ошибками, возни кающими при обработке данных.

Глава 3. Нейросетевые модели для обнаружения и исиравления ошибок в комиьютериых модулярных вычислениях.

§ 3.1. Нейронная сеть конечного кольца.

Дальнейшее повышение производительности и надежности компьютеров связывают с искусственными нейронными сетями, являющимися основой нейрокомпьютеров (НК) [94].

Нейронная сеть (НС) представляет собой высокопараллельную дина мическую систему с топологией направленного графа, которая может по лучать выходную информацию посредством реакции ее состояния на вход ные воздействия. Узлами в НС называются процессорные элементы и на правлепные графы [21].

Существует общее мнение, из-за чего возникает интерес к этим сетям, что они могут выполнять некоторые сложные и творческие задачи, такие как распознавание образов, прогнозирование, оптимизация, распознавание речи и др., похожие на те, которые выполняет человеческий мозг [44, 53, 54, 76, 78]. Реализация этих задач традиционными методами выполнения затруднено из-за относительно низких их характеристик. Для улучшения этих характе ристик возникает необходимость использования нейронных сетей, которые имеют свойства, сходные со свойствами человеческого мозга, такими как: ас социативное обобщение, параллельный поиск, адаптация к изменениям сре ды и другие.

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

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

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

Рассмотрим модель и структуру НС при реализации арифметики конечно го кольца, описанные в работе [94]. В СОК мы имеем дело с конечными вы числительными структурами (кольца или поля), которые используются для реализации арифметических кольцевых операций. Основной операцией при этом является операция вычисления остатка целочисленного деления по мо дулю, которая обозначается |»|, где pj^ - модуль операции деления.

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

Основное поле R{pk) или GF{pi^)=^:®p^,®p^\, 5' = {о,1,...,/7^5.-l}, где симво лы @р^, ®р^ соответствуют сложению и умножению по модулю р^, а прямое кольцо: /г(р)=^:Ш,®}, 5 = {0,l,...,P-l}, Р = j=i Общая интерпретация архитектзфы НС - это массово параллельная, взаи мосвязанная сеть простых элементов и ее иерархическая организация. Струк тура НС в некоторой степени моделирует биологическую нервную систему.

Мощностью НС является ее способность использования начальной базы знаний для решения существующей проблемы. Все нейроны работают кон курентно, а на непосредственные вычисления влияют знания, зашифро ванные в связях сети [129].

Взаимодействие нейронов з^итывается в трехуровневой иерархии сети, состоящей из слоев [130]:

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

2. Отображение разрядного вычисления (определяет функцию конечного кольца, применяемз^ю к каждому вычислительному разряду).

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

Эти отображения являются краеугольным камнем реализации HCICK. Они подробно описаны ниже. Рассмотрим вычислительную модель НСКК.

Арифметика постоянных величин. Эта классификация предполагает зна ние заранее всех постоянных арифметической операции. Например, опреде и ление модулей р,- (/ = 1,/?) непосредственно задает P = YlPi' Основные кон станты системы определяются следующим образом. Зададим п чисел в СОК.

По определению ортогональных базисов [5] они могут быть представлены в следующем виде для i = \,2,...,n.

i Pi где w, - целое положительное число, которое называется весом ортогональ ного базиса, — ^ = l(mod р,).

Pi Р Обозначив через Sf остаток от деления натурального числа — на pi, в co Pi ответствии с [5] /я,- определяется как рещение сравнения ntiSj s i (mod pi).

Пример. Пусть дана система оснований /?i = 4, Р2=5, Р4 = 9 т о г д а Рг=1, /' = 1260. Вычислим — = 315, — = 252, — = 180, — = 140. Откуда Р\ Рг Ръ РА 51^ = 3, ^2 = |252|5 = 2, ^3 = |18O|^ = 5, J4 = \Щд = 5 • Паходим w, = 3, /«2=3, /«3=3, /«4=2. Таким образом, 5i =3-315 = 945, 52=3-252 = 756, 5з =3-180 = 540, ^4 =2-140 = 280.

Арифметика переменных. Эта классификация определяется операциями кольца 0, 0 и комбинациями этих операций (кодирование и декодирование), где, по крайней мере, один из входов является переменной величиной.

Вычислительная операция приближается к принципу работы системы с обратной связью, которая выполняет операцию по модулю с представлением результата в двоичном виде. Тогда для него можно записать j= где {zp^ —оператор извлечения /-ого разряда двоичного представления Z.

Теорема 3.1.1. Все операции конечного кольца в арифметике переменных основаны на вычислительной модели n-X.

z= (3.1.1) /o = Повторение (итерация) вычислительной модели определяется как Z (3.1.2) {z{k)fK /= Теорема 3.1.2. Вычислительная модель может быть повторенной, и повто рение сходятся в одной точке.

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

Рассмотрим архитектуру НСКК. На основании вычислительной модели конечного кольца, главным оператором которого является оператор извлече ния отдельных разрядов двоичного представления преобразуемого числа, мо тут быть построены многослойные подсети. Структура подсети показана на рисунке 3.1.1, где синаптические веса для z,- равны w- =2', Организация подсети имеет два слоя:

1. Сборный (используется для сбора входов, принадлежащих одному дво ичному разряду входных источников). Результат операций преобразования двоичного числа к остатку, умножения, сложения, вычисляемы при помощи НСКК, является функцией суммы взвешенных входных разрядов.

2. Вычислительный (реализует вычислительную модель (3.1.1)). Резуль тат вычисления определяется положительной логикой. Как сказано выше, конечный результат НСКК будет иметь устойчивую форму.

Система может стабилизироваться до ошибочного представления (в интер вале [/7,2"]), в случае переполнения диапазона. Ошибка может быть исправ лена, если это конечный результат, или оставлена в этом неверном состоя нии, если это промежуточный результат, который не повлияет на ход даль нейших вычислений, используюших его значение.

Одним из положительных моментов СОК является возможность неза висимой и параллельной обработки каждой цифры в большинстве операций арифметического устройства (АУ). В связи с этим в АУ может быть выделен ряд каналов по числу оснований, работающих в большинстве случае незави симо друг от друга и параллельно во времени [5]. Если каждую подсеть (рис.

3.1.1) отождествлять с отдельным основанием (каналом) СОК, предназна ченным для выполнения операций, реализуемых независимо и конструк тивно оформленных в типовой канал АУ, то образованная совокупность ка налов будет представлять собой АУ, функционирующее в СОК. На рисунке 3.1.2 представлена схема АУ в СОК.

Рассмотрим работу сети при преобразовании двоичного кода в код СОК, 2-й слой А В 1-й слой «О «1 А ««-1 fin-l ^ б) а) Рис. 3.1.1. Структура подсети (а) и ее символическое обозначение (б) при этом в сборном слое 1 входы /7,- для всех / будут равны О, т.к. на вход схемы поступает только один операнд.

Пусть число Z задано в виде выражения (3.1.1), тогда легко представить число в СОК. Обозначив Z, = I 2' ДЛЯ у = 1,2,..., г получим Pij j= Pij Z = (Z,,Z2,...,Z^), т.е. для образования числа Z в СОК требуется определить синаптические веса wy.

fio «о Рис. 3.1.2. Структура сети арифметического устройства в СОК Пример. Пусть на вход сети поступает двоичное число Л = 10111, которое необходимо преобразовать по модулям Pi = 4, Р2=5, Р2 =У, Р4 = 9. В данном случае г = 4. Тогда синаптические веса w» = 2' (/ = 0,4, у = 1,4 ) будут равны H'oi=Ol = 00 ^31 = 0 = 001 = 010 W22 = 100 ^32 = o i l W42 = = 001 = 010 W23 = 100 W33 = 001 W43 = = 0001 Wi4=0010 W24=0100 W34=1000 ^44= Ha выходе сети сигнал Zj определяется выражением Zj = (= У = 1,4. Тогда Z, = l l, Z2=011, Z3=010, Z4 =0101, a Z = (l 1,011,010,0101).

При выполнении операций сложения, вычитания и умножения преобразо вания в сети будут выполняться согласно выражению /1-1 /J- E 2' 2' {2} {AQBY^ = /=0 /= p p j= p p где 0 е {+,-,х}. Все действия в каналах независимы и проходят параллельно.

Для иллюстрации работы НСКК рассмотрим преобразование чисел, пред ставленных в СОК, в двоичный код. Для выбранной ранее системы основа ний СОК величины Р = 1260, а В^ =945, ^2 =756, В^ =540, В4 =280. При этом Китайская теорема об остатках может быть записана как Это равенство может быть реализовано с помощью иерархической сети (рис. 3.1.3), основанной на подсети оператора (рис. 3.1.1). При этом синапти ческие веса для Z, равны Wg = Bi, i = 1,2,...,л. Время преобразования чисел оп ределяется как О{п -1). Во всех слоях кроме первого слоя синаптические веса равны Wi=l. Если для суммирования величин Z,- применить принцип рекур сивного сдваивания, тогда число слоев определяется логарифмическим сум А А Рис. 3.1.3. Архитектура преобразователя СОК в двоичный код на основе НСКК мированием как [log2 «], а время преобразования будет равно O(log2 «), На рисунке 3.1.4 приведена архитектура преобразователя СОК в дво ичный код на основе принципа рекурсивного сдваивания.

«л- Рис. 3.1.4. Архитектура НСКК преобразования принципа рекурсивного СОК в двоичный код на основе рекурсивного сдваивания Пример. Как и ранее, будем считать, что основаниями СОК являются Р\=^ Р2 = 5, /'3=7, Р4=9. С целью краткости выкладок числа будем запи сывать в десятичном коде, хотя в НСЮС они представлены в двоичном коде.

Допустим «1=3, « 2 = 3, « 3 = 2, « 4 = 5, а веса Wi=Bi, W2 = B2, W^^B^, ^^4=^4, тогда ^ = «1^1 + «2^2 + «3^3 + «41^4 (mod Р), т.е.

Процесс преобразования числа А из СОК в двоичный код с помощью НСКК (рис. 3.1.3) может быть представлен следующим образом:

2.

3.

4.

Для преобразования числа потребовалось 4 шага. Преобразованное число А в двоичном коде будет равно 10111. Процесс преобразования числа А в двоичный код с использованием схемы, изображенной на рисунке 3.1.4, при водит к росту аппаратурных затрат и уменьшению времени преобразования и может быть записан в два шага:

6 3 ;

|lO8O + 14OO|j26o =1220;

2. |63 + 1220L. = 2 3.

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

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

Рассмотрим теперь структуру преобразователя СОК в ОПС [94]. Исходя из теоремы 1.2.3.2, данное преобразование позволит нам обнаружить ошибки в исходном представлении числа в СОК.

Пусть в выбранной упорядоченной СОК число имеет вид X X = {х1,х2,'.',х„), и требуется найти представление числа X в соответствую щей ОПС.

Известно, что (3.1.3) X = (xiBi+X2B2+... + XnBn)modP, где Bi, Bj,..., В„ - ортогональные базисы, которые являются константами для выбранной СОК и имеют вид:

52=(0Д,0,...,0), ••• 5„ =(0,0,0,...,!).

Пусть для упорядоченной СОК известны представления в ОПС ортого нальных базисов:

Рассмотрим ортогональные числа выражения (3.1.3) о).

XiBi={0,0,:.,0,Xi, Здесь поставлен знак сравнения, так как произведение х,В/ может оказать ся больше Р. Обозначим т.е. XiBi = Bi^. (mod Р), где О Б^. Р.

Пайдем представления в ОПС для чисел Bi^... В виду того, что СОК упоря доченная, то число Х( Pi может служить цифрой в каждом из разрядов с ос нованиями pi, /?,+,,..., р„. Поэтому нахождение произведения л:,-5,- сводится к умножению на одноразрядное число, т.е. равносильно х,- последовательным сложениям. Если при этом не учитывать переполнения в W-M разряде, то в результате вычислений получится вместо л:,-5,- представление в ОПС для чи сел Bi^,. Пусть полученные представления будут Xi =1,2,...,р,-1 для / = 1,2,...,л.

Таким образом, X = xiB^ +Х2В2 +...+х„В„ = 5 ц + В2Х2 +•••+^/и„ Структура описанного преобразователя СОК в ОПС изображена на рисун ке 3.1.5, где w/ = В^^ для / = 1,2,...,п;

j - номер модуля. Для иллюстрации рас Рис. 3.1.5. Архитектура преобразователя СОК в ОПС на основе НСЮС смотренного метода приведем пример.

Пример. Пусть основаниями СОК служат числа Pi = 4, Р2=5, Рз= Р4=9, тогда ^ = 1260. Дано число в СОК Л!" = (3,2,5,4). Найдем представление этого числа в соответствующей ОПС.

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

Bi =945 = 0,1,5,6), ^2 =756 = (0,4,2,5), 5з =540 = (0,0,6,3), ^4 =280 = (0,0,0,2).

Тогда X = (3,2,5,4) = 3Bi + 2^2 + 55з + 4^4 = 5,з + ^22 + ^35 + 5i3 =(3,3,1,2), 522 =(0,3,5,1), Лз5=(00.2,1), ^44 =(0,0,0,8).

Откуда e(3.3,l,2) e(0,3,5,l) e(0,0,2,l) (0,0,0,8) (3,1,2,4) Таким образом, число X, представленное в данной СОК в виде (3,2,5,4), в o n e есть (3,1,2,4). Проверку проведем переходом к десятичной ПСС:

и Вычисления в конечных кольцах являются важным разделом специальных задач кодировании и декодировании информации, цифровой обработки сиг налов, криптографических преобразований. Отображение модулярной ариф метики на нейронную сеть позволяет использовать нейрокомпьютер при ре шении задач, в которых применение модулярной арифметики наиболее эф фективно, что говорит о потенциальной возможности увеличения быстродей ствия решения этих задач [19].


Основной операцией вычислений в конечных кольцах является нахожде ние остатка от деления числа X на. р Недостатки НС алгоритмов (НСА) преобразования чисел по модулю, по строенных по принципу рекуррентной редукции, значительно сужают об ласть применения НС модулярной арифметики и определяются наличием об ратных связей. Основными недостатками НСА являются:

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

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

3. В системе с обратными связями необходимо обеспечить условия устой чивости. Так, если в описанной сети один из весовых коэффициентов, каким то образом, изменится и станет равным w, 2', то вместо редукции и умень шения разрядности преобразуемых данных может возникнуть обратный эф фект;

4. При достаточно большой размерности входных данных число итераций может быть достаточно большим, что снижает быстродействие системы в це лом;

5. В процессе преобразования данных система может просто пропустить правильное решение и стабилизироваться в неверном представлении.

Устранить указанные недостатки можно отказавшись от обратных связей в НСКК, реализовав обработку данных на сети прямого распространения [96].

На рисунке 3.1.6 представлен общий вид многослойной НС прямого распро странения с последовательными связями [21]. Нейроны входного слоя такой сети не выполняют вычислительных функций, а служат лишь для разветвле Рис. 3.1.6. Граф многослойной НС прямого распространения с последовательными связями ния входов, число слоев определяется числом итераций, необходимых для преобразования входных данных, а число нейронов в каждом слое - разряд ностью обрабатываемых данных на каждой из итераций, так как нейрон в та ких сетях упрощен до однобитного процессорного элемента.

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

Замена обратных связей в НСЮС на прямые позволяет повысить скорость обработки данных, так как в такой сети одновременно обрабатывается не сколько отсчетов и в каждом такте работы сети на входе формируется преоб разованные данные. В то время как, в НСКК с обратными связями для преоб разования данных необходимо несколько тактов работы сети [94].

3.2. Нейросетевая реализация гибридного кода ЛЛ'^-СОК.

3.2.1. Модифицироваиная нейронная сеть конечного кольца.

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

Анализ модульных операций над числами гибридного кода показал сле дующее. Основной операцией при модулярной обработке данных в коде AN СОК, как и в арифметике конечного кольца, является вычислительная мо дель, основанная на итеративном механизме сокращения по модулю. Поэто му, проделывая рассуждения аналогичные тем, что были изложены в преды дущем параграфе, можем заключить, что все модульные операции в арифме тике переменных гибридного код основаны на вычислительной модели /г- (3.2.1) 2' I Ар где {zY'^ — оператор извлечения /-ого разряда двоичного представления Z.

По той же причине, что и модель 3.1.1, вычислительная модель 3.2.1 может быть повторенной, и повторение сходятся в одной точке.

На основании вычислительной модели 3.2.1 могут быть построены много слойные подсети. Структура подсети подобна той, что показана на рисунке 3.1.1, но при этом синаптические веса для г,- равны w- = 2',, / = O,l,...,«-l, и Ар результат формируется по модулю Ар.

Если каждую подсеть отождествлять с отдельным основанием (каналом) AN-СОК, предназначенным для выполнения операций, реализуемых незави симо и конструктивно оформленных в типовой канал АУ, то образованная совокупность каналов будет представлять собой АУ, функционирующее в коде AN-СОК, - получим НС, аналогичную сети, представленной на рисунке 3.1.2.

Рассмотрим работу сети при преобразовании двоичного кода в код AN СОК, при этом в сборном слое 1 входы Д- для всех / будут равны О, т.к. на вход схемы поступает только один операнд.

Пусть число Z задано в виде выражения (3.2.1), тогда легко представить п-\ число в AN-СОК. Обозначив Zj = для J = l,2,...,r полу А..-2'\ \AJPJ ;

=о чим Z = (Zi,Z2,...,Z^), т.е. для образования числа Z в AN-СОК требуется оп ределить синаптические веса Wy =А..2'\\AjPj Пример. Пусть на вход сети поступает двоичное число Л'^ = 23 = 10111, ко торое необходимо преобразовать по модулям З/?! =3-4 = 12, 3^2=3-5 = 15, =3-7 = 21, 3^4=3-9 = 27;

Лу=3, у =1,4. В данном случае г = 4. Тогда си = U, - 2' (i = 0,4, У = 1,4 ) будут равны наптические веса nj AjPj ^01=0011 w,i=0110 W2i=0000 W3i=0000 ^41= = 0011 Wi2=0110 W22=1100 W32=1001 W42= = 00011 Wj3 = 00110 W23 = 01100 1V33 = 00011 W43 = = 00011 w,4 =00110 ^24 =01100 W34 =11000 W44 = Па выходе сети сигнал Zj определяется выражением Zj = ;

=о У = 1,4. Тогда Zi=1001, Z2=1001, Z3 =00110, Z4 =01111, а Z = (1001,1001,00110,01 111).

При выполнении операций сложения, вычитания и умножения преобразо вания в сети будут выполняться согласно выражениям п- /1- 2' \Ap \Ap Ар Ар /= /=о j= Ар Ар Ар s л- п-\ \M'\-N Z2' Л/ — N м \Ар \Ap /= ;

=0 /=0 Ар Ар Ар Ар Все действия в каналах независимы и проходят параллельно.

Как и в случае сети конечного кольца, недостатки наличия обратной связи в конструируемой сети можно устранить, реализовав обработку данных на сети прямого распространения [21, 94, 96].

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

3.2.2. Нейронные сети коррекцнн ошибок в коде AN-СОК для исирав леиия искаженных остаток.

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

P «2 •(^г) Н Р2 I • « ап а Рис. Ъ.1.1.\. Архитектура НС коррекции ошибки в коде ^iV-COK для исправления искаженного остатка НС, изображенная на рисунке 3.2.2.1, работает следующим образом. На вход НС подаются разряды а,- (/ = 1,л) данного слова кода AN-QOY. и нахо дятся остатки от деления их на соответствующие генераторы Ai AN-кодов. В очередном блоке процесс решения задачи продолжает выполняться в зависи мости от выходного сигнала первой фазы. Если выходной сигнал после пер вого этапа равен нулю, то исходный сигнал а,- считается правильным и при нимается a'i =ai. В противном случае, делаем вывод о том, что /-ый разряд исходного слова содержит ошибку, и, полагая, что этот разряд является единственным ошибочным разрядом представления данного слова, с помо щью НС, подобной НС расширения системы оснований кода СОК [94], ис правляем искаженный разряд (рисунок 3.2.2.2). В НС расширения системы оснований кода ЛЛ'^-СОК веса изначально определены, при этом ^1 ^ 2 ' •••• ^/-1» ^i+\- • • ^п - о р т о г о н а л ь н ы е б а з и с ы с и с •»

P = P\P2-Pi-\Pi+\Pn^ 1 mj., р„;

gj = темы оснований, где вес Pi-\., Pi-\, соответствуюш,его ортогонального базиса, j = 1,2,...,/-!,/ +1,...,и.

V 1 1 "л ~ «1 \рГ)—•«;

«• « Pi - Р\р, HC расширения системы оснований кода ЛЛ'-СОК Рис. 3.2.2.2. Работа блока [РГ Вышеизложенное можно обобщить на случай исправления ошибок в не скольких (двух, трех и так далее) разрядах представления числа в гибридном коде, для этого достаточно обеспечить НС соответствующим числом избы точных каналов-оснований.

3.2.3. Коррекция искаженных разрядов двоичного представления AN остатков.

Рассматривая ситуацию, когда искажению могут быть подвержены не бо лее одного разряда ау (i = \,n, J = 1,Iog2(/i,-(р,- -1))+1) двоичного представле ния каждого из остатков а,- (которые в предыдуш;

ем случае назывались нами разрядами представления данного слова), может быть предложена НС, изо браженная на рисунке 3.2.3.1. Суть ее работы основана на следуюш;

ем факте, связанном с AN -кодами, способными исправлять одиночные ошибки.

Пусть некоторое число Л из диапазона [0,Л^о) представлено в двоичном ^ -коде: N ^^ = AN = щп2...п1^, где w,e{O,l}, i = \,k. Пусть в указанном пред ставлении числа произошла одиночная ошибка, что означает инвертирование одного из значений щ (с нуля на единицу или наоборот), последнее, в свою очередь, можно трактовать как изменение исходной величины AN на ± 2':

где / - номер (позиция) искаженного символа двоичного представления чис ла AN.

ПЗУ \ ПЗУ \ ПЗУ АЛ \ Рис. 3.2.3.1. Архитектура ПС коррекции ошибки в коде AN-СОК. для исправления искаженных разрядов двоичного представления остатков Таким образом, AN-код,, способен исправлять одиночные ошибки, если число А, генератор AN -кода, выбрано так, что остатки AN ± 2' по модулю А (или, что то же самое, остатки ± 2' по модулю А ) различны для всех одиноч ных ошибок, и величины остатков можно использовать в качестве синдрома для определения местоположения ошибки. Поскольку синдромам 2' и соответствует один и тот же вектор ошибки, /-ая компонента которого -2' равна единице, а все остальные равны нулю, то можно сделать следующий вывод. Таблица соответствия синдрома и вектора ошибки (таблица коррек ции ошибки) для Л//-кода, исправляющего одиночные ошибки, содержит два столбца и А + \ строк;


а в силу теоремы 1.3.3.3 последнее означает, что даже при кодировании чисел из большого диапазона (диапазона [о,7/о)» где Л о ве ^ лико) таблица коррекции ошибки имеет небольшие размеры.

Пример. Пусть для кодирования чисел из диапазона [о,5) выбран генера тор Л = 13, тогда Вектор Разрешенное Принятое число Синдром ошибки число 0 0 000000 1 000001 1 000001 2 000010 2 000010 4 4 000100 8 001000 8 001000 010000 16 010000 100000 32 100000 0 001101 13 000000 12 001100 12 000001 2 15 000010 001001 000100 9 000101 001000 5 3 011101 29 010000 6 101101 45 100000 011010 26 000000 1 011011 27 000001 11 011000 24 000010 011110 30 000100 18 001000 5 10 10 100000 111010 000000 0 100111 38 000001 12 И 000010 100101 35 000100 9 ЮПИ 8 47 001000 110111 55 010000 000111 100000 7 0 110100 000000 1 110101 53 000001 2 110110 54 000010 110000 48 9 8 111100 001000 10 100100 36 010000 7 010100 20 100000 и таблица коррекции ошибки для данного AN -кода имеет следующий вид.

Синдром Вектор ошибки 0 1 или 12 2 или 11 3 или 10 4 или 9 5 или 8 6 или 7 Итак, НС, изображенная на рисунке 3.2.3.1, функционирует следующим образом. На вход сети подаются остатки а,- преставления принятого слова.

Затем находится остаток от деления а,- на Ai, или модуль значения наимень шего по абсолютной величине вычета а,- по модулю Л,-. По найденному зна чению устанавливается соответствующий вектор ощибки, который суммиру ется с исходной величиной а,- (поразрядно, по модулю 2). Результат указан ной суммы представляет собой искомое исправленное значение остатка.

Заметим, что в последнем случае исходный код СОК, на базе которого был построен гибридный код, может и не являться избыточным, однако генерато ры Ai AN-кодов должны быть выбраны так, чтобы минимальное кодовое расстояние полученных при этом AN-кодов было бы не меньше, чем Имеет смысл совместная коррекция: исправление двоичных разрядов AN остатков на базе Л//-кода, а затем коррекция искаженных /iiV-остатков с по мощью свойств кода СОК.

Таким образом, видим, что полученные архитектуры НС отражают поло жительные свойства гибридного кода AN-СОК, а именно, независимость и простоту коррекции искаженных остатков данного слова. Следует отметить, что при использовании кода СОК с небольшим числом малых модулей, в ко торых наиболее вероятна одиночная ошибка в их двоичном представлении, целесообразно применить НС, представленную на рисунке 3.2.3,1. В осталь ных случаях следует воспользоваться нейронными сетями, изложенными в пункте 3.2.2, а также совместной коррекцией на основе избыточного кода СОК и ЛЛ^-кода.

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

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

Для решения этой проблемы в [94] предложено воспользоваться свойства ми СОК и нейронных сетей, а именно, обнаружение ошибки провести на базе свойств системы СОК, а локализацию и коррекцию ошибки - на базе свойств НС. При этом роль указанной НС играла рекуррентная сеть Хопфилда.

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

Сеть Хэмминга, предложенная Р. Липпманом в работе [112], - это трех слойная рекуррентная структура, которую можно считать развитием сети Хопфилда. Она позиционируется как специализированное гетероассоциатив ное запоминающее устройство. Основная идея этой сети состоит в миними зации расстояния Хэмминга между тестовым вектором, подаваемым на вход сети, и векторами обз^ающих выборок, закодированными в структуре сети.

На рисунке 3.3.1 представлена обобщенная схема сети Хэмминга. Первый Рис.3.3.1. Структура сети Хэмминга ее слой имеет однонаправленное распространение сигналов от входа к выхо ду и фиксированные значения весов. Второй слой, MAXNET, состоит из ней ронов, связанных обратными связями по принципу "каждый с каждым", при этом в отличие от структуры Хопфилда существует ненулевая связь входа нейрона со своим собственным выходом. Веса нейронов в слое MAXNET также постоянны. Разные нейроны связаны отрицательной (подавляющей) обратной связью с весом - s, при этом обычно величина s обратно пропор циональна количеству образов. С собственным выходом нейрон связан по ложительной (возбуждающей) обратной связью с весом, равным +1. Веса по ляризации нейронов принимают значения, соответствующие нулю. Нейроны этого слоя функционируют в режиме WTA (англ: Winner Takes All - победи тель получает все), при котором в каждой фиксированной ситуации активи зируется только один нейрон, а остальные пребывают в состоянии покоя.

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

В процессе функционирования сети можно выделить три фазы. В первой из них на ее вход подается Л'^-элементный вектор х. После предъявления этого вектора на выходах нейронов первого слоя генерируются сигналы, за дающие начальные состояния нейронов второго слоя, т.е. MAXNET'a.

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

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

Сеть Хэмминга считается гетероассоциативным запоминающим устройст вом с парой связанных между собой векторов {у,х), где х и у - это соответ ственно входной и выходной биполярные векторы сети со значениями эле ментов ±1. Входные узлы сети 1, 2,..., Л'' принимают значения, задаваемые аналогичными компонентами вектора х. Нейроны первого слоя рассчитыва ют расстояние Хэмминга между фактически предъявленным входным векто ром д: и каждым из р закодированных векторов-образцов х^'\ образующих веса нейронов первого слоя. Нейроны в слое MAXNET выбирают вектор с наименьшим расстоянием Хэмминга, определяя таким образом класс, к кото рому принадлежит предъявленный входной вектор х. Веса нейронов выход ного слоя формируют вектор, соответствующий предъявленному входному вектору. Нри р нейронах первого слоя емкость запоминающего устройства Хэмминга также равна р, поскольку каждый нейрон представляет единст венный класс.

Подбор весов сети Хэмминга оказывается чрезвычайно простым. Веса первого слоя соответствуют очередным векторам образов х^'', поэтому для / = 1,2,...,р. Аналогично веса выходного слоя соответствуют очередным векторам образов у^'', связанным с х^'':

.

Wy =yj в случае нейронов слоя MAXNET, функционирующих в режиме WTA, ве са сети должны усиливать собственный сигнал нейрона и ослаблять осталь ные. Для достижения этого эффекта принимается wH = i (3 3 I) а также для i^j. Для обеспечения абсолютной сходимости алгоритма веса w^' должны отличаться друг от друга. Р. Липпманн в своей работе принял р-\ где ^ — случайная величина с достаточно малой амнлитудой.

Нейроны различных слоев сети Хэмминга функционируют по-разному.

Нейроны первого слоя рассчитывают расстояния Хэмминга между поданны ми на вход сети вектором х и векторами весов wy' = х^'' отдельных нейронов этого слоя (/ = 1,2,...,/?). Значения выходных сигналов этих нейронов опреде ляются по формуле [104] (3.3.4) р 1_^лк1^1П где dfj[x^\x) обозначает расстояние Хэмминга между входными векторами х и х^'\ т.е. количество битов, на которое различаются эти два вектора.

(3.3.5) с учетом (3.3.5) формула (3.3.4) может быть записана в виде, 1 1 л;

. 0) Значение Pi =1, если х = х^'' и j),- = О, если д: = -х^''. В остальных случаях зна чения У1 располагаются в интервале [ОД].

Сигналы j), нейронов первого слоя становятся начальными состояниями нейронов слоя MAXNET на второй фазе функционирования сети. Задача нейронов этого слоя состоит в определении победителя, т.е. нейрона, уровень возбуждения которого наиболее близок к 1. Такой нейрон указывает на век тор образа с минимальным расстоянием Хэмминга до входного вектора jc.

Процесс определения победителя - это рекуррентный процесс, выполняемый согласно формуле (3.3.6) yi{k) = fil.w^\(k-\)\, при начальном значении yj{o) = yi' Функция активации /(у) нейронов слоя MAXNET задается выражением (337) l Указанный итерационный процесс завершается в момент, когда состояние нейронов стабилизируется и активность продолжает проявлять только один нейрон, тогда как остальные пребывают в нулевом состоянии. Активный нейрон становится победителем и через веса w}p линейных нейронов выход ного слоя представляет вектор у^'', который соответствует вектору х^'', при знанному слоем MAXNET в качестве ближайшего к входнЬму вектору х.

Важным достоинством сети Хэмминга считается небольшое количество взвешенных связей между нейронами. Например, 100-входовйя сеть Хоп филда, кодирующая 10 различных векторных классов, должна содержать 10000 взвешенных связей с подбираемыми значениями весов. При построе нии аналогичной сети Хэмминга количество взвешенных связей уменьшается до 1100, из которых 1000 весов находятся в первом слое и 100 - в слое MAX NET. Выходной слой в этом случае не учитывается, поскольку сеть Хэммин га, аналогичная сети Хопфилда, является ассоциативной [67].

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

Кроме того, компьютерное моделирование НС Хэмминга позволило обнару жить и другое немаловажное достоинство использования кода AN -СОК. Так, взяв в качестве оснований кода СОК числа р\=Ъ, Рг = 4, Рз = 5 и PJ^=1, причем считая, что р^, р^— проверочные модули, имеем, что разрешенными векторами (обучающими векторами сети) являются 00000000000, 01001001001, 10010010010, 00011011011, 01000100100, 10001000101, 00010001110, 01011010000, 10000011001, 00001100010, 01010000011, 10011001100. При этом ясно, что код СОК должен исправлять всякую оди ночную ошибку (любой ошибочный остаток). Однако, используя в качестве тестового вектора 00000000110, был получен вектор 00010001110, что не яв ляется ошибочной работой сети, но представляет собой ошибочный резуль тат для кода СОК. Ошибку такого рода можно избежать, если определять расстояние Хэмминга между числами по правилам, изложенным в пункте 1.2.2, т.е. как количество различных остатков в представлениях чисел. По добная ошибка также не произойдет в случае использования для частичной локализации ошибки кода AN-СОК (обладающего достаточными корректи рующими способностями).

В процессе моделирования работы сети Хэмминга был установлен сле дующий важный факт. Соблюдение условий (3.3.1), (3.3.2) и того, что веса w,H должны отличаться друг от друга, т.е. требований к формированию ве совой матрицы w^"*' слоя MAXNET, не являются достаточными для правиль ного функционирования сети Хэмминга. Действительно, поскольку матрица w^'"^ является матрицей размеров [ру-р), а условие (3.3.1) однозначно опре деляет ее диагональные элементы (они равны единице), то для выполнения остальных требований нужно выбрать р^ -р различных чисел, принадлежа щих интервалу,0, этим требованиям удовлетворяют следующие чис I Р-1 ) ла а где а = \,2,...А Итак, можно принять (т) ^ p{ij) wl где [(/)Л при ji (3.3.9) (p{i,j)=\{p-ni-\)+j-\, при ji.

[ при j = i На рисунках 3.3.2.а. и 3.3.2.6. показаны примеры работы программы, де монстрирующей функционирование сети Хэмминга, в которой элементы ве совой матрицы w^'"' слоя MAXNET определяются формулами (3.3.8) и (3.3.9).

Как видим из рисунка 3.3.2.6. с помощью НС получен неверный результат.

•I' Сеть Хэмминга [ГТТГТТ Введите основание Вееаиге генератор AN-коаа Введите принятое число Система счисления 1/5 4/5 2/ (?• десятичная (~ двоичная -1-1-1-1- -1 1-11 1-111- Очистить J i Пуск - Рис.3.3.2.а. Окно программы, моделирующей работу сети Хэмминга Таким образом, условие Липпманна о том, что где ^ - случайная величина с достаточно малой амплитудой, является суще ственным, однако значимым при этом является и неизвестная величина ам плитуды случайной величины ^. Дальнейшие рассуждения позволят нам оп ределить величину указанной амплитуды.

Взяв за основу условия (3.3.1) и (3.3.2), а также тот факт, что недиагональ ные элементы весовой матрицы слоя MAXNET должно незначительной от личаться друг от друга (но быть различными), определим допустимую вели чину рассеяния значений «недиагональных» весов.

Рассмотрим элементы матрицы W^"'', матрицы весов слоя MAXNET. Из вестно, что WY' = 1, остальные же элементы можно считать дробями вида где О а,-, 1, i^ j ;

ij = \,р. Компоненты вектора у представляют собой дро би вида -^, где i//- e{Q,\,2,...,N]. Тогда, вычисляя компоненты очередного N •' вектора у{к), находим произведение W^'"'y{k-\), где ;

'(о) = ^. Наблюдая за формированием /-ой компоненты вектора у{к), видим, что знаменатель дро позволяет «распространить» /-ую компоненту вектора y{k-l) на би — остальные {р -1) слагаемых, уменьшенных в ау раз, получая тем самым для «f Сеть Сэмминга Ввеаите основание У*» |а-1-1-1-м Ввепиге генератор AN иода Ввеаите гринятое число | Система счисления Ум |ЗЛ 4/5 0/ (~ десятичная (f двоичная •1-1-1-м 11- 1-11 М Очистить J Пуск Рис.3.3.2.б. Окно программы, моделирующей работу сети Хэмминга /-0Й компоненты вектора j(l) сумму:

(3.3.10) Как уже было указано ранее, компоненты ^'(о) есть дроби —, где N O^t//j N, поэтому при нахождении компонент вектора ^(1) для выражений, стоящих под знаком суммы в формуле (3.3.10) справедливо Обратим внимание на то, что слагаемых в сумме (3.3.10) ровно р-1, тогда с учетом множителя —-. г, в силу последнего неравенства, а также преоб N[p-\) разований (3.3.6) и (3.3.7) можно заключить, что компоненты вектора '(l) также являются дробями вида (3.3.11) ^,где Оv/iN.

Продолжив аналогичные рассуждения, можно сделать вывод, что компо ненты любого вектора у{к), результата функционирования слоя MAXNET после А:-ой итерации, есть дроби вида (3.3.10). Это замечание существенно, и его надо запомнить.

При нахождении компоненты вектора у(\), соответствующей компоненте вектора ;

;

(о) равной -, сумма (3.3.10) без общего множителя N N{jj-l) имеет вид:

где ^,- О, / = 1, р — 1.

Ясно, что при нахождении суммы (3.3.10) для определения компоненты век тора ;

;

(1), соответствующей компоненте вектора ^'(О) равной, анало гичная сумма будет иметь вид:

Полагая пт, и для начала считая, что число компонент у векторов у{к) лищь две, потребуем, чтобы веса подбирались из условия, что больщее зна чение после преобразования (3.3.10) оставалось большим, для этого доста точно, чтобы,3 3 13) l((N-n)-a{N-m))-((N-m)-(a±qN-n))0, [N - m)-a{N - n))-{{N -n)-{a± ^\N - m)) 0, где ^ — величина допустимого рассеяния недиагональных весов матрицы цг\'»), р1з Предыдущей системы получим й:m-riia + \ [п - т\а + \ откуда {т-п1а + N-n N-m Справедливость второго и третьего неравенств последней системы очевидна в силу условия,^ О. Что же касается первого и четвертого неравенств, по скольку пт, то из справедливости первого неравенства следует правиль ность четвертого. Таким образом, получим #^., (3.3.14) -, N-n Т.е. величина допустимого рассеяния недиагональных весов матрицы W^"*' на (k + l) шаге работы слоя MAXNET зависит как от значения числителя наи большей компоненты рассматриваемого вектора y{k), так и от величины наименьшей разности между числителями компонент у{к).

Сняв ограничение на число компонент векторов у{к), и вновь обращая внимание на выражения (3.3.12') и (3.3.12"), заметим, что для того, чтобы большее значение после преобразования (3.3.10) оставалось большим, при чем разность между числителями вычисленными компонентами оставалась не меньше 1 достаточно, чтобы Т.е.

P-4 M ' = j рассматривая в последнем неравенстве критическую ситуацию (когда w- =0,, а ±(^,-^',) = (/ = 1,р-1), т.е.^,=^, ^', = 0), очевидно, что при этом левая ^ часть неравенства будет наименьшей, получим:

р- Полагая, что наименьшая разность между числителями нредыдуших компо нент, исключая случай равенства компонент (смысл подобного исключения будет пояснен ниже), равна 1 ( т - и = 1), а поскольку очевидным является то, что /и 1, для большей надежности, будем считать, что т = 1. Тогда a (3.3.15) ^ N{p-l)-l Итерационный процесс вычисления у{к) гарантирует, что значение числите ля максимальной компоненты данного вектора не может быть больше Л'^, а условие (3.3.15) позволяет утверждать, что компоненты у{к), соответствую щие различным компонент у{к-1)^ также будут разными.

Осталось пояснить отброшенный случай равенства некоторых компонент данного вектора y{k-l). В ситуации, когда равные компоненты не являются наибольшими, благодаря условию (3.3.15) их отличие от наибольшей компо ненты будет сохраняться. Условия (3.3.1), (3.3.2) гарантируют уменьшение значений компонент на каждом шаге итерации и, в конечном счете, благода ря преобразованиям (3.3.6) и (3.3.7), меньшие компоненты будут равны ну лю. В случае же, когда равными являются наибольшие компоненты, условие (3.3.15) позволит обнулить комноненты, которые меньше их, а (3.3.1), (3.3.2) и условие различия недиагональных элементов матрицы Ж^""' дадут возмож ность «победить» лишь одной из них.

Таким образом, условие (3.3.15) определяет допустимую величину рассея ния значений «недиагональных» весов, и в совокупности с (3.3.1), (3.3.2) и условием различия недиагональных элементов матрицы fV^'"' гарантирует применимость весовой матрицы W^'"^ на протяжении всего процесса функ ционирования слоя MAXNET.

Например, можно принять • '^ Р т.е.

где (3.3.17) при j = i Следующие примеры показывают работу программы, моделирующей функционирование сети Хэмминга, исправляющей искаженный остаток по модулю р. Элементы весовой матрицы w^"*^ слоя MAXNET определяются формулами (3.3.16), (3.3.17).

Пример. Для обеспечения исправления одиночных ошибок в качестве ге нератора ЛЛ^-кода для модуля р = 5 было выбрано число 13. Как видим из рисунка 3.3.2.а. потребовалось 5 итерации для исправления третьего оши бочного символа.



Pages:     | 1 | 2 || 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.