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

На правах рукописи

ЛМёикО

г

Левченко Александр Юрьевич

РАЗРАБОТКА НЕЙРОННЫХ МОДЕЛЕЙ

ДЛЯ КОРРЕКЦИИ ОШИБОК В КОМПЬЮТЕРНЫХ МОДУЛЯРНЫХ ВЫЧИСЛЕНИЯХ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Ставрополь - 2005

Работа выполнена в Ставропольском государственном университете

Научный руководитель: заслуженный деятель науки и техники РФ,

доктор технических наук, профессор Червяков Н.И.,

Официальные оппоненты: доктор физико-математических наук,

старший научный сотрудник Каплан Л.Г.,

кандидат физико-математических наук, доцент Мезенцева О.С.

Ведущая организация: Поволжская государственная академия

телекоммуникаций и информатики, г. Самара.

Защита состоится 22 декабря 2005 года в 14 часов 40 минут на заседании диссертационного совета ДМ 212.256.05 при Ставропольском государственном университете по адресу: 355009, г. Ставрополь, ул. Пушкина, 1, ауд. 214.

С диссертацией можно ознакомиться в библиотеке Ставропольского государственного университета по адресу: 355009, г. Ставрополь, ул. Пушкина, 1.

Автореферат разослан « » ноября 2005 года.

Ученый секретарь /

регионального диссертационного совета пЛ/ /

кандидат физико-математических наук, доцент Б. Копыткова

20о6-4 22ЛШ

~~2 79*7^ ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В данной работе изучаются две конструкции арифметических кодов -коды системы остаточных классов (СОК) и Л//-коды. Достоинства корректирующего кода СОК:

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

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

Основной недостаток кода СОК состоит в высокой арифметической сложности процедуры локализации ошибок. Достоинствами ЛИ -кода являются

- простота процедур кодирования и декодирования;

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

- использование остаточных кодов, как представителей АЫ -кодов, обеспечивает параллелизм при выполнении действий над информационными и избыточными символами.

Основным недостаток АЯ-кода является снижение скорости выполнения арифметических операций за счет увеличения разрядности числа.

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

3 i рос. национальная^

i библиотека

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

Объектом диссертационной работы являются информационные методы контроля работы ЭВМ. Предметом исследований являются два представителя арифметических корректирующих кодов (коды СОК и ЛЛГ-коды), а также рекуррентная сеть Хэмминга, обладающая ассоциативным свойством.

Цель исследований данной работы состоит в повышении эффективности коррекции ошибок, возникающих при обработке данных в ЭВМ.

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

- исследование информационных методов обнаружения, локализации и исправления ошибок;

- разработка математической модели гибридного кода, представляющего собой синтез кодов СОК и АИ -кодов;

- обоснование осуществимости модульных и немодульных операций над числами гибридного кода AN-COK■, вывод формул, задающих правила выполнения операций над числами в коде /Ш-СОК;

- разработка геометрической модели полученного гибридного кода;

- сравнительный анализ основных характеристик кодов СОК и А N -СОК;

- разработка структуры отказоустойчивых нейронных сетей, функционирующих в модифицированной системе остаточных классов;

- компьютерное моделирование исследуемых методов коррекции ошибок. Методы исследования. Для решения поставленных в работе научных

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

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

1. Получены формулы для исправления искаженных разрядов представления чисел в коде СОК. Исследованы отдельные факты обнаружения и исправления ошибок, порядок которых превышает число, гарантированное минимальным расстоянием кода.

2. Предложен гибридный код ЛУУ-СОК, представляющий собой синтез кодов системы остаточных классов (СОК) и АЫ -кодов, найдено достаточное условие того, чтобы длина кода ЛЛГ-СОК была меньше длины кода

СОК, считая, что оба кода представлены одними и теми же информационными основаниями.

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

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

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

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

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

8. Получены достаточные условия для допустимой величины рассеяния недиагональных элементов весовой матрицы IV ^ слоя МАХЫЕТ сети Хэмминга, гарантирующие применимость матрицы на протяжении всего процесса функционирования слоя МАХ№Т.

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

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

Автором разработан пакет программ (СОК, СО К (порядок ошибки), Сеть Хэмминга, Сеть Хэмминга {ЛИ-СОК)), предназначенный для исследования процесса обнаружения, локализации и исправления ошибок в кодах СОК и АЫ-СОК.

На защиту выносятся следующие основные положения:

1. Математические модели кодов СОК и АЫ-кодов, их основные достоинства и недостатки.

2. Математическая модель гибридного кода ЛЫ-СОК, представляющего собой синтез кодов СОК и АЫ-кодов. Методы обнаружения, локализации и исправления ошибок в коде ЛЛГ-СОК, существенно упрощающие процедуру коррекции ошибок соответствующего кода СОК.

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

4. Сравнительный анализ алгоритма коррекции ошибок в коде ЛЛГ-СОК и метода проекций, основного метода коррекции ошибок в коде СОК.

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

6. Модель совместного применения модифицированной нейронной сети конечного кольца и нейронной сети Хэмминга, обеспечивающая по максимуму правдоподобия обнаружение и 100%-ую коррекцию ошибки.

Реализация результатов. Основные результаты диссертационной работы реализованы в ООО «Моби» и учебном процессе Ставропольского государственного университета.

Апробация результатов работы. Результаты работы были представлены в журнале «Инфокоммуникационные технологии» (Самара, 2004 г.), в трудах участников Международной школы-семинара по геометрии и анализу, посвященной памяти Н.В. Ефимова (Ростов-на-Дону, 2004 г.), на I международной научно-техническая конференции «Инфотелекоммуника-ционные технологии в науке, производстве и образовании» (Ставрополь,

2004 г.), на 50-й юбилейной научно-методической конференции преподавателей и студентов «Университетская наука-региону» (СГУ, Ставрополь,

2005 г.), на постоянно действующем межвузовском семинаре «Моделирование и нейросетевые технологии» (СГУ, Ставрополь, 2003-2004 гг.).

Публикации. Основные результаты диссертации достаточно полно изложены в 9 научных статьях.

Структура диссертации. Работа состоит из введения, трех глав, заключения и списка литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведена классификация помехоустойчивых кодов, рассмотрены наиболее применимые из них для контроля выполнения различных операций ЭВМ. Основной объем первой главы занимает материал, посвященный двум конструкциям арифметических кодов - кодам системы остаточных классов (СОК) и ЛМ-кодам.

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

модулям pt, » = 1, л), т.е. А = (<*!, а ......а„), гдЪа,=А- — л=|/<| ,/=1,я.

\_Pii "

Если основания СОК - попарно взаимно простые числа, то между целыми числами из диапазона [0,РЯ), где Р„ = рхр2 ••••/>„, и их набором остатков существует взаимно однозначное соответствие.

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

если И = (а,,а2.....ап), В = (/?,,/ï2,...,#,) и Ле[0,£>), Яе[0,Д), (л*ф[0,/>),то

А*В = (/„у2,...,гя), где Г/=|а,*/?/|Л, <=й, ♦е{+,-,х},£)=р1р1-...-рл.

Полагая, что для однозначного представления используемых чисел достаточно к остатков (к < п ), получим избыточный код, называемый кодом СОК, или кодом в остатках. При этом произведение Рк = рхр2 ■ ••■ рц называют рабочим диапазоном, а Р„ = рхр7 •...• р„ - полным диапазоном.

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

При сохранении условия, что основания СОК - попарно взаимно простые числа, код СОК носит название R -кода. Я-код имеет минимальное расстояние rfmin в том и только в том случае, если степень избыточности Р„/Рк не меньше произведения любых rfmiB -1 оснований заданной СОК, т.е.

"к M

Минимальное расстояние кода является важнейшей характеристикой корректирующего кода. Так, избыточный код может обнаружить все совокупности из / или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше Г: d^ > / +1 ; корректирующий код может исправлять все совокупности из m или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше удвоенного числа ошибок: ¿„у,, г 2т +1.

Однако минимальное расстояние кода не в полной мере характеризует корректирующие свойства кода. В диссертационной работе доказана справедливость следующего утверждения.

Теорема. Упорядоченный код СОК с одним информационным и п - i проверочными модулями исправляет ровно р{(рг - pi){p¡ - Р\)- {p„-pi) чисел, содержащих ошибку порядка и -1.

К примеру, код СОК с основаниями р1 =3, р2 =19, где рг - проверочный модуль, исправляет 48 чисел, содержащих одиночную ошибку, что составляет более 84% от количества чисел полного диапазона, или почти 90%, если учесть правильные числа кода.

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

СОК, А,=(а^,а2.....al4,«lt|„ .,а„) - проекция А по модулю р„ тогда при

условии, что А, = Аг =... = А„, следует считать А - правильное; если А,<Рк, a Aj > Рк (у = l,2,...,/-l,j' + l,...,n), то А - ошибочное, причем ошибка произошла в остатке по основанию p¡. Локализованный ошибочный остаток о/ можно исправить, используя формулу

п _

a'¡ = 2>jbj у

м

j*i ¡ао pi

где в', - исправленное значение ап Bj (у = 1,л) - ортогональные базисы сокращенной СОК, Р^ - р,р2 ■...• />Hft+t '•••'Ра ■

Если по проекциям А, не удалось локализовать ошибку, то это означает, что ошибка не является одиночной. Тогда рассматриваются проекции по паре модулей, по тройкам модулей и так далее (при условии, что минимальное расстояние кода достаточно велико). Автором диссертации доказана справедливость формул

Bj а В J (mod л<)),

и

i ajbj

н

1*'i

j**i fапч «l)

(где В] - соответ-

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

Другими хорошо известными арифметическими кодами являются Л//-коды.

ЛИ -код представляет собой отображение N ли, 0<, N < В, где А - положительное целое число, называемое порождающим числом, или генератором кода, а В определяет количество чисел в коде, или мощность кода.

Легко видеть, что АМХ + АИг = А(ых + Ыг), т. е. сумма кодовых слов для и Ы2 является кодовым словом суммы этих чисел (если /V, + Ы2 < в); поэтому иногда /«//-коды называют линейными арифметическими кодами.

Если А - нечетное число, А > 1, то А является генератором кода, обнаруживающего одиночные ошибки ((1тш >1); для обнаружения одиночных ошибок в машинной арифметике достаточно выбрать значение А- 3.

Если А - нечетное простое число, а в удовлетворяет условию

В =

,когда 2-примитивный элемент вР{р), 2 (Р~§г _1

,когда -2{но не 2)-примитивный элемент СР(р),

Р

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

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

г/2

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

г

чением минимального расстояния кода, потребуется определить ]ГС'„ проекций). Под вычислением (определением) проекций следует понимать ряд операций, достаточных для осуществления сравнения величины проекции с рабочим диапазоном. Например, в случае десятичной позиционной системы счисления (ПСС) для указанного процесса потребуется выполнить

г/2 г/2

X С„ (и - г) умножений и £ Сди -»' - 1) сложений по соответствующим мо-1=1

дулям где = рхрг-..г р^р^-..^ Р,2_хР,2+х- р^р,^- ..г Рп,

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

г/2 г!2

избыточных оснований, и составит £С„ •("-') умножений и ЛС„ (п-1~\)

1=1 ы

сложений по модулям р,.

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

Вторая глава посвящена разработке и изучению математической модели гибридного кода ЛЛ^-СОК, представляющего собой синтез кодов СОК и АЫ -кодов.

Пусть каждый из остатков безызбыточного или корректирующего кода СОК представлен в ввде двоичного АЫ-кода. Полученный код назовем гибридным кодом Л/У-СОК [3,9].

Из вышесказанного и соглашения, что числа А, и р, являются взаимно простыми, т.е. (л, ,/>,)= 1, / = 1,«, следует справедливость формул [2]: пусть N -{ах,а2.....ап)сок, где а, =Щр> (; = 17«). тогда

"4 \л\а{4).....4АТ~С0К = или «^М^, 0-и), (2)

УЛ? б [о,£>), N - целое число, В = р,рг ■ ...• р„;

если М = М = {рУ\рг(А\...,р}А)) и Ме[0,£>), Л^б[0,0),

(М±Л')е[0,£)), то

У\гУ\..,гп(А)), (3)

где , /=1,

I I Л,р,

(4)

где у^ =

Переход от двоичного кода СОК (безызбыточного или корректирующего) к соответствующему гибридному коду -4//-СОК связан с некоторым увеличением длины кода.

Неравенство, полученное в работе [6],

* *

5>82 4-к < 1>1Щяк>-1<Ш ^•оег А1 +* м м

задает интервальную оценку указанного увеличения, а приближенное 1 *

равенство ЬГш6рид - Ьс0К *А( - точечную оценку этого увеличения.

Если полагать, что при получении из корректирующего кода СОК, имеющего избыточные основания рк+1, рк+2, .... р„, кода Л//-СОК были задействованы лишь информационные модули, а избыточность достигнута за счет генераторов лIV-кодов {л, - генератор АЫ-кода для модуля рп I = \,к), то установлено достаточное условие, при котором длина построен-

ии

Л1

, / = 1,1 •

ного кода л/У-СОК будет меньше длины двоичного кода СОК, т.е. доказана следующая теорема [9]. Теорема. Длина гибридного кода ЛМ-СОК меньше длины кода СОК, если

Пр,->2*+1/М2--Ч- (5)

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

В работе [8] рассмотрена существующая и предложены две новые геометрические модели кода СОК. Кроме этого, в диссертации получена геометрическая интерпретация перевода чисел из кода СОК в код ЛЛГ-СОК (и обратно), а также геометрические модели кода ЛМ-СОК.

Переводя каждый из разрядов представления исходного числа N в системе остаточных классов в двоичную систему счисления, легко заметить, что наряду с избыточностью кода, обусловленной наличием проверочных оснований, код СОК также будет иметь и внутреннюю избыточность (для изображения каждого из разрядов представления числа количество двоичных символов выбирается с запасом; например, для представления чисел, соответствующих модулю р-17, т.е. чисел из диапазона от 0 до 16, в двоичной системе счисления необходимо 5 символов, но с помощью того же количества символов можно изобразить числа из диапазона от 0 до 31). Очевидно, что внутренняя избыточность кода СОК является негативной, напрасно затрачивающей аппаратные ресурсы. В работе [6] установлены следующие важные факты.

Одним из решением указанной проблемы может служить использование кода ЛИ-СОК, остатки которого удовлетворяют условиям

где <у2 <•■■</( ^т, 1 » = 1,г, А - генератор л^-кода,

Л < 2' -1, полагая р = {^д ~\)/А - основание кода СОК, тогда можно добиться

1) взаимной простоты модулей исходного кода СОК,

2) мощность множества избыточных чисел будет равна сумме А,+А2+...+ А„, где я - количество оснований кода,

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

ни-.

В частности, обоснована осуществимость построения кодов ЗЛ/ -СОК (^тт = 2) с минимальной негативной избыточностью, а также кодов ЛИСОК с основанием

г(А,-\)И_Х

где А, такое, что -2 (но не 2) - примитивный элемент простого поля Галуа ОР(А,), при этом

Перейдем к описанию методов обнаружения и исправления ошибок в Гибридном коде ли-СОК.

Для обнаружения ошибки по 1-ому основанию кода ЛЛГ-СОК может оказаться достаточным нахождение наименьшего неотрицательного вычета данного АЫ -остатка по модулю А: если справедливо модульное равенство

<6)

то логично полагать, что в /-ом Л Л'-остатке ошибки не содержится, а в случае не выполнения равенства (6) - считать / -ый АЫ -остаток ошибочным.

Каждый из АЫ -остатков кода представлен в двоичной системе счисления, в силу чего полный диапазон чисел, отображаемый данным АЫ -остатком, есть интервал [0,2"'), где и, - количество двоичных разрядов, выделенных под /-ое основание. Количество чисел из полного диапазона,

2"I

для которых справедливо равенство (6), определяется формулой т, = —

14.

Под процентом обнаруженных ошибок 7, по /-ому основанию будем понимать отношение количества чисел, которые могут быть обнаружены при вычислении (6), к полному объему чисел данного диапазона, т.е.

■ т1

п. =1— 2 щ

Так как по каждому модулю обнаружение ошибок происходит независимо, то общий процент обнаруженных ошибок для кода АЫ-СОК, построенного на базе кода СОК с и взаимно простыми модулями, равен П = Щг\г-"Пп-

Ошибочные АЫ -остатки можно отбросить, если оставшиеся остатки однозначно определяют исходное число Ы.

Исправить ошибочные основания можно, воспользовавшись формулой (1), для чего перевести безошибочные АЫ -остатки а/^ в остатки а, соответствующего кода СОК:

ч

V

(7)

я

последнее возможно, когда А, и р, - взаимно простые числа. Затем вернуться к АЫ -остатку: а= Л,а,.

Таким образом, сложность алгоритма локализации ошибок в коде ЛАОСОК существенно меньше сложности метода проекций: л сверток (операций определения остатка от деления) по модулям Л, и л сравнений против г/2 г/2 т

1с;-(я-0 умножений, (и-1-1) сложений, £С„ свертки по модулям /=1 1=! /=1 г/2

у Р/ и сравнений, где л - общее число оснований кода, к - число ин-

/=1

формационных модулей, г = п-к.

4 Локализация ошибок в коде АЫ-СОК, полученного из избыточного кода

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

В диссертационной работе был предложен и иной способ локализации и исправления ошибок. Пусть генераторы АИ -кодов Л, , соответствующие основаниям р1 (/= 1,и), выбраны так, что минимальное кодовое расстояние полученных при этом АЫ-кодов не меньше, чем 3 (</^п г 3). Предположим, что в некотором У-ом АЫ -остатке произошла одиночная ошибка, что можно трактовать как изменение исходной величины А1Ы на ± 2;:

где j - номер (позиция) искаженного символа двоичного представления числа А,И. Используя величины остатков в качестве синдрома для определения местоположения ошибки, в силу того, что синдромам и |- соответствует один и тот же вектор ошибки, } -ая компонента которого равна единице, а все остальные равны нулю, можно сделать следующий вывод. Таблица соответствия синдрома и вектора ошибки (таблица коррекции ошибки) для

А +1

АЫ -кода, исправляющего одиночные ошибки, содержит два столбца и

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

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

1 кодов СОК (ИЛ'-СОК) и рекуррентной нейронной сети Хэмминга, и полу-

чены достаточные условия допустимой величины рассеяния недиагональных элементов весовой матрицы слоя МАХНЕТ сети Хэмминга.

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

11

Л |

* PJ

где Ш] - вес соответствующего

pi

ортогонального базиса, j = 1,2.....»- и+1.....п.

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

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

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

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

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

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

аг--»ЦП-► аг

—-И Рп [-*■ а'„

Рисунок 1. Архитектура НС коррекции ошибки в коде ЛЛГ-СОК для исправления искаженного остатка а) общая, модель б) схема работы блока I р< I < = 1,я

а\-

V

ПЗУ

аг-ПЗУ

N_Ьи=

V

ПЗУ

Рисунок 2. Архитектура НС коррекции ошибки в коде ЛЛГ-СОК для исправления искаженного разряда двоичного представления остатка

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

Веса слоя МА?СЧЕТ должны усиливать собственный сигнал нейрона и ослаблять остальные. Для достижения этого эффекта принимается

И*"> = 1, (8)

---^<^<0 (9)

для у. Для обеспечения абсолютной сходимости алгоритма веса

должны отличаться друг от друга.

В результате проведенных исследований автором диссертации был установлен следующий важный факт. Соблюдение условий (8), (9) и того, что веса -л^ должны отличаться друг от друга, т.е. требований к формированию весовой матрицы слоя МАХЫЕТ, не являются достаточными для правильного функционирования сети Хэмминга. Удалось доказать, что допустимая величина рассеяния недиагональных

элементов ^М _ _ ; удовлетворяющих неравенству (9), матрицы р-1

Ж(т) равна:

Условия (8)-(10) совместно с условием различия недиагональных элементов матрицы РУ^ гарантируют абсолютную сходимость алгоритма функционирования слоя МАХЫЕТ к правильному значению. Например, весовая матрица И'М может бьггь задана формулой

1 /. л ■ Г(р-1Х«-1)+у-1, при у'</

= ~ +_2Т—V/—%—\> где 0+7-2, при }>1

р рг(р-\1ы{р-х)-\) ЫСр- 1X^0-0-1)0+при 1 = 1

' = 1 >Р, 7 = 1 ,Р-

Сочетание СОК {АЫ-СОК) и НС по максимуму правдоподобия обеспечивает обнаружение и 100%-ую коррекцию ошибки. Изложенный подход позволяет создавать высокопроизводительные и надежные вычислительные структуры.

ЗАКЛЮЧЕНИЕ

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

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

2. Предложен гибридный код ЛЛГ-СОК, найдено достаточное условие того, чтобы длина кода /(А/-СОК была меньше длины кода СОК, считая, что оба кода представлены одними и теми же информационными основаниями.

3. Обоснована осуществимость модульных и немодульных операций над числами гибридного кода АЫ-СОК, получены формулы для представления числа И, заданного в десятичной системе счисления или в виде систематической записи, в коде ЛЛГ-СОК, перевода чисел кода АЯ-СОК в код СОК и обратно, а также формулы, задающие правила выполнения модульных операций над числами в коде ААГ-СОК.

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

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

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

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

8. Получены алгоритмы вычисления элементов весовой матрицы н^М слоя МАХЫЕТ сети Хэмминга, гарантирующие абсолютную сходимость процесса функционирования слоя МАХЫЕТ к правильному значению.

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

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

Список публикаций по теме диссертационной работы

1. Левченко А.Ю. Анализ эффективности алгоритмов кодирования и декодирования некоторых помехоустойчивых кодов // Ученые записки физи-

ко-математического факультета Ставропольского государственного университета. - Ставрополь: Изд-во СГУ, 2002. - С. 112-117.

2. Левченко А.Ю. Действия над числами, представленными в коде АЫ-СОК. // Физико-математические науки в Ставропольском государственном университете: Материалы 50-й юбилейной научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону», посвященной 60-летию Победы в Великой Отечественной войне. - Ставрополь: Изд-во СГУ, 2005.-С. 122-126.

3. Левченко А.Ю. Комбинированный код, построенный на базе кода системы остаточных классов. // Труды участников Международной школы-семинара по геометрии и анализу, посвященной памяти Н.В. Ефимова, Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 5-11 сентября 2004 г. - Ростов-на-Дону: Изд-во ООО «ЦВВР», 2004. - С. 200-201.

4. Левченко А.Ю. О некоторых возможностях помехоустойчивых (корректирующих) кодов. // Современные проблемы математики и информатики: Сборник научных трудов. Вып. 1 / Сост Н.Г. Дендеберя, С.Г. Манве-лов. - Армавир: Редакционно-издательский центр АГПУ, 2004. - С. 61-62.

5. Левченко А.Ю. Одно из решений проблемы негативной внутренней избыточности двоичного кода системы остаточных классов. // Материалы международной научно-технической конференции «Перспективные технологии в средствах передачи информации», г. Владимир, 20-22 апреля 2005. - Владимир, 2005. - С. 78-81.

6. Левченко А.Ю. Определение оптимальных оснований комбинированного кода. // Инфотелекоммуникационные технологии в науке, производстве и образовании: Первая международная научно-техническая конференция, г. Ставрополь, 19 декабря 2004 г., Северо-Кавказский государственный технический университет. - С. 457-465.

7. Левченко А.Ю. Помехоустойчивые коды в системе остаточных классов. // Современные проблемы математики и информатики: Сборник научных трудов. Вып. 1 / Сост Н.Г. Дендеберя, С.Г. Манвелов. - Армавир: Редакционно-издательский центр АГПУ, 2004. - С. 62-64.

8. Червяков Н.И., Левченко А.Ю. Геометрические модели корректирующего кода в системе остаточных классов. // Инфокоммуникационные технологии. - Самара, 2004. - №3. - С. 10-13.

9. Червяков Н.И., Левченко А.Ю. Использование АЫ-кодов для исправления ошибок в кодах системы остаточных классов. И Инфотелекоммуникационные технологии в науке, производстве и образовании: Первая международная научно-техническая конференция, г. Ставрополь, 19 декабря 2004 г., Северо-Кавказский государственный технический университет. - С. 584-594.

Изд. лиц.серия ИД № 05975 от 03.10.2001 Подписано в печать 09.11.2005 Формат 60x84 1/16 Усл.печ.л. 1,05 Уч.-изд.л. 0,94

Бумага офсетная Тираж 100 экз. Заказ 473

Отпечатано в Издательско-полиграфическом комплексе Ставропольского государственного университета. 355009, Ставрополь, ул.Пушкина, 1.

»23866

РЫБ Русский фонд

2006-4 27979

Введение

Глава 1. Современное состояние теории и практики информационных методов контроля работы ЭВМ. 10 1.1. Анализ и общая классификация информационных методов контроля работы вычислительных средств. 1.2. Корректирующий код системы остаточных классов

1.2.1. Система остаточных классов (СОК). Принципы 28 кодирования и обработки данных в СОК.

1.2.2. Корректирующие свойства кода СОК.

1.2.3. Способы обнаружения ошибок.

1.2.4. Методы локализации и исправления (коррекции) 44 ошибок.

1.3. АЫ -коды, их корректирующие способности.

1.3.1. Канонические представления целых чисел. 1.3.2. Арифметический вес и арифметическое расстояние.

1.3.3. ЛЛГ-коды. 1.3.4. Циклические АЫ -коды.

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

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

2.1. Гибридный код АЫ -СОК, его корректирующие способности.

2.2. Действия над числами, представленными в коде ЛЛ^-СОК.

2.3. Геометрические модели кодов СОК и Л//-СОК. 100 ( 2.4. Оценка увеличения длины двоичного кода, обусловленного переходом от кода СОК к гибридному коду. 2.5. Решение проблемы внутренней избыточности двоичного кода СОК.

2.6. Обнаружение, локализация и исправление ошибок в коде АИ -СОК. ч, Выводы по главе

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

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

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

3.2.1. Модифицированная нейронная сеть конечного кольца. 148 / 3.2.2. Нейронные сети коррекции ошибок в коде АИ-СОК для исправления искаженных остатков. 150 3.2.3. Коррекция искаженных разрядов двоичного представления

АИ -остатков.

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

Актуальность темы. Развитие средств вычислительной техники сопровождается ростом производительности машин, усложнением их конструкций и расширением областей применения. Это обусловливает постоянный интерес к проблеме повышения надежности работы машин [30]. Проблема помехоустойчивости относится к числу тех проблем, значение и актуальность которых с течением времени не только не уменьшаются, а даже увеличиваются [36]. Решение этой проблемы техническими средствами требует больших финансовых затрат; повышение надежности информации при этом ограничено уровнем развития техники и сколь-нибудь значительные достижения в этой области требуют новых технических решений. Другим путем решения задачи повышения достоверности является использование специальных процедур, основанных на применении помехоустойчивых (корректирующих) кодов. Этот путь не содержит никаких принципиальных ограничений. Более того, при выборе подходящего кода, обладающего необходимой корректирующей способностью, можно заметно снизить требования к надежности самого технического оборудования, сделать его более простым и дешевым [5].

В данной работе изучаются две конструкции арифметических кодов - коды системы остаточных классов (СОК) и АЫ -коды.

Достоинства корректирующего кода СОК:

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

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

К основному недостатку кода СОК отнесем высокую арифметическую сложность процедуры локализации ошибочных остатков. Достоинствами АЫ -кода являются

- простота процедур кодирования и декодирования;

- возможность обнаружения одиночных ошибок при малом увеличении двоичного представления исходного числа (например, при А = 3 не более чем на два разряда);

- использование остаточных кодов, как представителей АИ -кодов, обеспечивает параллелизм при выполнении действий над информационными и избыточными символами.

К основному недостатку АИ -кода отнесем снижение скорости выполнения арифметических операций за счет увеличения разрядности числа.

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

Объектом диссертационной работы являются информационные методы контроля работы ЭВМ. Предметом исследований являются два представителя арифметических корректирующих кодов (коды СОК и АЫ -коды), а также рекуррентная сеть Хэмминга, обладающая ассоциативным свойством.

Цель исследований данной работы состоит в повышении эффективности коррекции ошибок, возникающих при обработке данных в ЭВМ.

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

При этом решались следующие частные задачи:

- исследование информационных методов обнаружения, локализации и исправления ошибок;

- разработка математической модели гибридного кода, представляющего собой синтез кодов СОК и АЛ -кодов;

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

- разработка геометрической модели полученного гибридного кода;

- сравнительный анализ основных характеристик кодов СОК и АЫ -СОК;

- разработка структуры отказоустойчивых нейронных сетей, функционирующих в модифицированной системе остаточных классов;

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

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

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

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

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

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

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

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

7. Проведено сравнение алгоритма коррекции ошибок в коде ЛАГ-СОК и метода проекций, основного метода коррекции ошибок в коде СОК, а также получена формула для определения процента обнаруженных ошибок для кода АИ- СОК.

8. Получены достаточные условия для допустимой величины рассеяния недиагональных элементов весовой матрицы Ш ^ слоя МАХИЕТ сети Хэм-минга, гарантирующие применимость матрицы IV М на протяжении всего процесса функционирования слоя МАХЫЕТ.

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

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

Автором разработан пакет программ (СОК, СОК (порядок ошибки), Сеть Хэмминга, Сеть Хэмминга (/1/У-СОК)), предназначенный для исследования процесса обнаружения, локализации и исправления ошибок в кодах СОК и ЛЛГ-СОК.

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

В первой главе приведена классификация помехоустойчивых кодов, рассмотрены наиболее применимые из них для контроля выполнения различных операций ЭВМ. Основной объем первой главы занимает материал, посвященный двум конструкциям арифметических кодов - кодам системы остаточных классов (СОК) и АИ -кодам.

Вторая глава посвящена разработке и изучению математической модели гибридного кода ЛЛ^-СОК, представляющего собой синтез кодов СОК и АЫ-кодов.

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

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

На защиту выносятся следующие основные положения:

1. Математические модели кодов СОК и АЫ -кодов, их основные достоинства и недостатки.

2. Математическая модель гибридного кода Л7У-СОК, представляющего собой синтез кодов СОК и АЫ -кодов. Методы обнаружения, локализации и исправления ошибок в коде А/У-СОК, существенно упрощающие процедуру коррекции ошибок соответствующего кода СОК.

3. Геометрическая интерпретация кодов СОК и А/У-СОК, отражающая свойство цикличности указанных кодов и позволяющая изображать коды с количеством оснований большим 3.

4. Сравнительный анализ алгоритма коррекции ошибок в коде А/У-СОК и метода проекций, основного метода коррекции ошибок в коде СОК.

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

6. Модель совместного применения модифицированной нейронной сети конечного кольца и нейронной сети Хэмминга, обеспечивающая по максимуму правдоподобия обнаружение и 100%-ую коррекцию ошибки.

Апробация результатов работы. Результаты работы были представлены в журнале «Инфокоммуникационные технологии» (Самара, 2004 г.), в трудах участников Международной школы-семинара по геометрии и анализу, посвященной памяти Н.В. Ефимова (Ростов-на-Дону, 2004), на I международной научно-техническая конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004 г.), на 50-й юбилейной научно-методической конференции преподавателей и студентов «Университетская наука-региону» (СГУ, Ставрополь, 2005 г.), на постоянно действующем межвузовском семинаре «Моделирование и нейросетевые технологии» (СГУ, Ставрополь, 2003-2004 гг.). 9

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

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

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

3. Предпосылкой к созданию нейрокомпьютерных вычислительных средств на основе аппарата системы остаточных классов является семантическое сходство математических моделей нейронных сетей и системы остаточных классов.

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

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

6. Получены достаточные условия для допустимой величины рассеяния недиагональных элементов весовой матрицы W^ слоя MAXNET сети Хэмминга, гарантирующие применимость матрицы W^ на протяжении всего процесса функционирования слоя MAXNET.

7. Сочетание СОК (АИ -СОК) и ИНС по максимуму правдоподобия обеспечивает обнаружение и 100%-ую коррекцию ошибки. Изложенный подход позволяет создавать высокопроизводительные и надежные вычислительные структуры.

Заключение

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

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

2. Предложен гибридный код АЫ -СОК, найдено достаточное условие того, чтобы длина кода А/У-СОК была меньше длины кода СОК, считая, что оба кода представлены одними и теми же информационными основаниями.

3. Обоснована осуществимость модульных и немодульных операций над числами гибридного кода АЫ -СОК, получены формулы для представления числа Ы, заданного в десятичной системе счисления или в виде систематической записи, в коде Л//-СОК, перевода чисел кода ЛЛГ-СОК в код СОК и обратно, а также формулы, задающие правила выполнения модульных операций над числами в коде АЫ -СОК.

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

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

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

7. Сравнительный анализ основных характеристик кодов СОК и ЛЛ/-СОК показал, что относительное увеличение аппаратных затрат зависит от корректирующих способностей АЫ -кодов, используемых для кодирования остатков, и может быть сделано небольшим по величине, а сложность алгоритма коррекции ошибок в коде АЫ -СОК существенно меньше сложности метода проекций. Так, по соотношению цена/качество, где под качеством понимаем процент чисел, подлежащих исправлению, а под ценой — ту цену (в виде числа элементарных операций), которую нам приходиться платить за осуществление этой коррекции, отдельные гибридные коды в 8-20 раз эффективнее соответствующих кодов СОК.

8. Получены алгоритмы вычисления элементов весовой матрицы IV^ слоя МАХЫЕТ сети Хэмминга, гарантирующие абсолютную сходимость процесса функционирования слоя МАХЫЕТ к правильному значению.

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

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

1. Акритас А. Основы компьютерной алгебры с приложениями. - М.: Мир, 1994.-544 с.

2. Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. — Алма-Ата: Наука, 1970. 248 с.

3. Акушский И. Я., Бурцев В.Н. Принципы построения высокопроизводительных и надежных процессоров в непозиционных системах счисления. // В сборнике "Теория кодирования и сложность вычислений". Алма-Ата: Наука, 1980.

4. Акушский И. Я., Пак И. Т. Вопросы помехоустойчивого кодирования в непозиционном коде. // Вопросы кибернетики, 1977. Т. 28. С. 36-56.

5. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Советское радио, 1968. - 440 с.

6. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. - 324 с.

7. Берлекэмп Э. Алгебраическая теория кодирования: Пер. с англ./ Пер. И.И. Грушко. М.: Мир, 1971.-478 с.

8. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. М.: Мир, 1986. -576 с.

9. Бояринов И.М. Недвоичные арифметические коды с большим минимальным расстоянием. // Проблемы передачи информации, 1975, т. 11, вып. 1, с. 57-63.

10. Бояринов И.М., Кабатянский Г.А. Спектр весов арифметических кодов с большим расстоянием. // Доклады VI симпозиума по проблеме избыточности в информационных системах, Ленинград, 1974. Л., 1974, ч. 1, с. 6-12.

11. Бояринов И.М., Кабатянский Г.А. Арифметические (п, А)-коды над произвольным основанием. // ДАН СССР, 1975, т. 221, № 4, с. 794-797.

12. Бояринов И.М., Кабатянский Г.А. Совершенные арифметические AN-коды, исправляющие одиночные ошибки. // Проблемы передачи информации, 1976, т. 12, вып. 1, с. 16-23.

13. Бояринов И.М., Кабатянский Г.А. Арифметические итеративные коды, исправляющие независимые ошибки. // Проблемы передачи информации, 1979, т. 15, вып. 1, с. 38-49.

14. Бухштаб А.А Теория чисел. М.: Просвещение, 1966. - 334 с.

15. Виноградов И.М. Основы теории чисел. М.: Наука, 1981. - 176 с.

16. Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.

17. Галушкин А.И. и др. Некоторые концептуальные вопросы развития нейрокомпьютеров. // Зарубежная радиоэлектроника. Успехи современной радиоэлектроники, №2, 1997. С. 3-10.

18. Галушкин А.И. Нейрокомпьютеры восьмидесятых (начало очередной революции в области нейрокомпьютеров) // Зарубежная радиоэлектроника. Успехи современной радиоэлектроники, 1999, №1. С. 3-16.

19. Галушкин А.И. Нейрокомпьютеры. М.: ИПРЖР, 2000. - 526 с.

20. Галушкин А.И. Некоторые исторические аспекты развития элементной базы вычислительных систем с массовым параллелизмом (80-е и 90-е годы) // Нейрокомпьютеры: разработка, применение, 2000, №1. С. 68-82.

21. Галушкин А.И. Теория нейронных сетей. М.: ИПРЖР, 2000. - 416 с.

22. Глухов М.М., Елизаров В.П., Нечаев A.A. Алгебра: Учебник. В 2-х т. -М.: Гелиос АРВ, 2003.

23. Горбань А.Н. Обучение нейронных сетей. М.: СП ПараГраф, 1991. -116с.

24. Головко В.А. Нейронные сети: обучение, организация и применение. -М.: ИПРЖ, 2001.-201 с.

25. Гриценко В.М. Недвоичные арифметические корректирующие коды. // Проблемы передачи информации, 1969, т. 5, вып. 4, с. 19-27.

26. Дадаев Ю.Г. Арифметические разделимые коды с исправлением независимых ошибок. // Изв. АН ССР. Техн. кибернетика, 1965, № 6, с. 84-93.

27. Дадаев Ю.Г. Арифметические композиционные коды с исправлением ошибок. // Проблемы передачи информации, 1968, т. 4, вып. 2, с. 38-45.

28. Дадаев Ю.Г. Арифметические коды, исправляющие ошибки. — М.: Сов. радио, 1969.-168 с.

29. Дадаев Ю.Г. К теории циклических арифметических кодов. // Проблемы передачи информации, 1970, т. 6, вып. 1, с. 45-51.

30. Дадаев Ю.Г. Теория арифметических кодов. — М.: Радио и связь, 1981. 272 с.

31. Дадаев Ю.Г. Циклическая структура AN -кодов. // Проблемы передачи информации, 1970, т. 6, вып. 4, с. 16-26.

32. Дынькин В.Н., Кимельфельд Б.Н. Построение недвоичных арифметических кодов, исправляющих одиночные ошибки. // Проблемы передачи информации, 1973, т. 9, вып. 1, с. 22-25.

33. Дынькин В.Н., Тененгольц Г.М., Хабелашвили Г.И. Об одном классе циклических арифметических кодов. // Сообщения АН ГССР, 1969, т. 55, № 3, с. 533-536.

34. Ерош И.Л., Ерош СЛ. Арифметические коды с исправлением многократных ошибок. // Проблемы передачи информации, 1967, т. 3, вып. 4, с. 7280.

35. Злотник Б.М. Помехоустойчивые коды в системах связи. М.: Радио и связь, 1989.-232 с.

36. Зюко А.Г. Помехоустойчивость и эффективность систем связи. М.: Связь, 1972.-360 с.

37. Зюко А.Г., Коробов Ю.Ф. Теория передачи сигналов. Учебник для ВУЗОВ. М.: Связь, 1972. - 282 с.

38. Информационные системы. Табличная обработка информации / Под ред. Е. П. Балашова, В. Б. Смочова. — JL: Энергоиздат, JI.O., 1985.

39. Кабатянский Г.А. О границах для числа кодовых слов в двоичных арифметических кодах. // Проблемы передачи информации, 1976, т. 12, вып. 4, с. 46-54.

40. Кабатянский Г.А. Минимальные представления чисел и негацикличе-ские арифметические коды. // Доклады VII симпозиума по проблеме избыточности в информационных системах, Ленинград, 1977. Д., 1977, ч. III, с. 136-140.

41. Кабатянский Г.А. Обобщенные остаточные коды. // Вопросы кибернетики/ АН СССР. Научный совет по комплексной проблеме «Кибернетика». — М., 1977, вып. 28, с. 91-109.

42. Каган Б.М. Электронные вычислительные машины и системы : Учеб. пособие для вузов. М.: Энергоатомиздат, 1991. —592 с.

43. Каган Б.М., Мкртумян И.Б. Основы эксплуатации ЭВМ: Учеб. пособие для вузов / Под ред. Б.М. Кагана. М.: Энергоатомиздат, 1988. - 432 с.

44. Калсон Роберт. Основные концепции нейронных сетей. М.: Вильяме, 2001.-288с.

45. Кармазин М.А. Об одном классе корректирующих кодов. // ДАН СССР, 1964, т. 157, №2, с. 303-306.

46. Карцев М.А. Арифметические устройства электронных цифровых машин. -М.: Наука, 1958.- 156 с.

47. Кладов Г.К., Шпильберг А.Я. Об одном классе избыточных арифметических кодов. // Кибернетика, 1966, № 4, с. 78-80.

48. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. - 392 с.

49. Колесник В.Д., Мирончиков Е.Т. Коды с. исправлением ошибок при арифметических операциях. // Проблемы передачи информации, 1965, т. 1, вып. 3, с. 20-28.

50. Комарцева Л.Г., Максимов A.B. Нейрокомпьютеры. М.: Из-во МГТУ им. Баумена, 2002. - 320 с.

51. Кондратьев В.Н., Трофимов Н.Н. Корректирующие коды с расстоянием, не меньшим пяти по Питерсону. // Изв. АН СССР. Техн. кибернетика, 1969, №3, с. 95-100.

52. Кострикин А.И. Введение в алгебру: Учебник для вузов. В 3-х т. М.: ФИЗМАТЛИТ, 2001.

53. Кохонен Т. Ассоциативная память: Пер. с англ. М.: Мир, 1980. - 204с.

54. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия телеком, 2001. - 381 с.

55. Левченко А.Ю. Анализ эффективности алгоритмов кодирования и декодирования некоторых помехоустойчивых кодов // Ученые записки физико-математического факультета Ставропольского государственного университета. Ставрополь: Изд-во СГУ, 2002. - С. 112-117.

56. Левченко А.Ю. Помехоустойчивые коды в системе остаточных классов. // Современные проблемы математики и информатики: Сборник научных трудов. Вып. 1 / Сост Н.Г. Дендеберя, С.Г. Манвелов. — Армавир: Редак-ционно-издательский центр АГПУ, 2004. С. 62-64.

57. Михеев В.М. О кодах, исправляющих арифметические ошибки. -Журн. вычисл. мат. и мат. физ., 1965, т. 5, № 2, с. 311-316.

58. Михелович Ш.Х. Теория чисел. Учебное пособие для физ.-мат. факультетов пед. ин-тов. — Изд. 2-е, переработ, и доп. М.: Высшая школа, 1967.-336 с.

59. Мкртчян С.О. Нейроны и нейронные сети. (Введение в теорию формальных нейронов) М.: Энергия, 1971. - 232 с.

60. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями): Пер. с франц. М.: Мир, 1999. - 720 с.

61. Огнев И.В., Борисов В.В. Интеллектуальные системы ассоциативной памяти. М.: Радио и связь, 1996. - 176 с.

62. Осовский С. Нейронные сети для обработки информации. / Пер. с польского И. Д. Рудинского. М.: Финансы и статистика, 2002. - 344 с.

63. Питерсон У. Коды, исправляющие ошибки: Пер. с англ./ Пер. Л.Е. Филипповой. М.: Мир, 1964. - 338 с.

64. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ./ Под ред. Р.Л. Добрушина и С.И. Самойленко. М.: Мир, 1976. - 594 с.

65. Савельев А.Я. Арифметические и логические основы цифровых автоматов: Учебник. М.: Высш. школа, 1980. - 255 с.

66. Сасковец В.Н., Андрианов В.И., Ерош И.Л., Беляев O.A. Составные арифметические коды. // Труды IV конф. по теории передачи и кодирования информации, Ташкент, 1969. -М., 1969, ч. V, с. 147-151.

67. Соколов О.Б., Еникеев И.И. Класс арифметических кодов с исправлением нескольких ошибок. // Проблемы передачи информации, 1976, т. 3, вып. 4, с. 73-75.

68. Стемпковский А.Л., Осинов Л.Б., Селезнев С.З. Проблемы реализации отказоустойчивых архитектур нейрочипов по технологии Систем с Интеграцией на Пластине. // Информационные технологии. №5, 1997. С. 15-20.

69. Тененгольц Г.М., Дынькин В.Н. Циклические коды, исправляющие арифметические ошибки. // Проблемы передачи информации, 1970, т. 6, вып. 3, с. 38-42.

70. Терехов В.А., Ефимов Д.В., Тюкин И.Ю., Антонов В.Н. Нейросетевые системы управления. СПб.: Издательств СПб.-Петербургского университета, 1999.-265 с.

71. Торгашев В.А. Система остаточных классов и надежность ЦВМ. М.: Советское радио, 1973. - 120 с.

72. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика. М.: Мир, 1992.-240 с.

73. Хассе Г. Лекции по теории чисел: Пер. с нем./ Пер. В.Б. Демьянова. — М.: ИЛ, 1953.-527 с.

74. Червяков Н.И. Геометрическая модель избыточного кода системы остаточных классов // Управляющие системы и машины, Киев, 1988, №3. С. 3

75. Червяков Н.И. Надежность и живучесть систем управления и связи, функционирующих в СОК. Ставрополь: СВВИУС, 1986.

76. Червяков Н.И. Отказоустойчивые непозиционные процессоры // Управляющие системы и машины. 1988, № 3. — С. 3-7.

77. Червяков Н.И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. — Ставрополь: СВВИУС, 1984. -84 с.

78. Червяков Н.И. Сумматор в системе остаточных классов. A.C. № 377771, БИ№ 18, 1973.

79. Червяков Н.И. Ускоренный алгоритм определения позиционных характеристик и его нейросетевая реализация // Нейрокомпьютеры: разработка, применение, 2001, №10. С. 22-29.

80. Червяков Н.И. Устройство для преобразования чисел из десятичной системы счисления в систему остаточных классов. A.C. 377767, БИ № 18, 1979.

81. Червяков Н.И., Бережной В.В., Оленев A.A. Устройство для контроля и исправления ошибок в избыточном модулярном коде. Патент РФ № 2022472, БИ № 20,1994.

82. Червяков Н.И., Бережной В.В., Оленев A.A. Устройство для преобразования кода системы остаточных классов в позиционный код с исправлением ошибок. Патент РФ № 1797119, БИ № 7, 1993.

83. Червяков Н.И., Бережной В.В., Оленев A.A., Калмыков А. И. Минимизация избыточного кода системы остаточных классов с одним контрольным основанием // Электронное моделирование, Киев, 1994, № 1. С. 56-60.

84. Червяков Н.И., Ирхин В.П. и др. Отказоустойчивость специализированных процессоров автоматизированных систем управления и связи. — Ставрополь: СВВИУС, 1991. 115 с.

85. Червяков Н.И., Левченко А.Ю. Геометрические модели корректирующего кода в системе остаточных классов. // Инфокоммуникационные технологии, Самара, 2004, №3. С. 10-13.

86. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Макоха А.Н. Нейрокомпьютеры в остаточных классах. Кн. 11: Учеб. пособие для вузов. (Научная серия «Нейрокомпьютеры и их применение», редактор А.И. Галушкин) — М.: Радиотехника, 2003. 272 с.

87. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С.А. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Под. ред. Н.И. Червякова. М.: ФИЗМАТЛИТ, 2003. - 288 с.

88. Шапошников А.В., Сахнюк П.А. Оптимизация структуры нейронных сетей конечного кольца. // Нейрокомпьютеры: разработка, применение, 2001, №10.-С. 13-19.

89. Barrows J.T., Jr. A new method for constructing multiple error correcting linear residue codes. Coord. Science Lab./Univ. Illinois, Urbana, 1966, Rep. R-277.

90. Brown D.T. Error detecting and correcting binary codes for arithmetic operations. IRE Trans., 1960, v. EC-9, N 3, p. 333-337.

91. Chang S.-H., Tsao-Wu N.T. Discussion on «Arithmetic codes with large distance». // IEEE Trans., 1968, v. IT-14, N 1, p. 174-176.

92. Chiang A.C.L., Reed I.S. Arithmetic norms and bounds of the arithmetic AN codes. // IEEE Trans., 1970, v. IT-16, p. 470-476.

93. Clark W.E., Liang J.J. On arithmetic weight for a general representation of integers. // IEEE Trans., 1973, v. IT-19, N 6, p. 823-826.

94. Clark W.E., Liang J.J. On modular weight and cyclic nonadjacent forms for arithmetic codes. // IEEE Trans., 1974, v. IT-20, N 6, p. 767-770.

95. Diamond J.M. Checking codes for digital computers. Proc. IRE, 1955, v. 43, p. 487-488.

96. Floreen P. The convergence of Hamming memory networks // IEEE Trans. -Neural Networks, 1991, vol. 2, N 5, p. 449-457.

97. Garner H.L. Error codes for arithmetic operations. // IEEE Trans., 1966, v. EC-15, N 5, p. 763-770.

98. Goto M. A note on perfect decimal AN codes. Information and Control, 1975, v. 29, N4, p. 385-387.

99. Goto M., Fucumura T. The distance of arithmetic codes. Memoirs Faculty Eng./Nagoya Univ., Jap., 1968, v. 20, N 2, p. 474-482.

100. Goto M., Fucumura T. Nonbinary AN codes with distance not less that five. // IEEE Trans., 1973, v. IT-19, N 1, p. 129-134.

101. Goto M., Fucumura T. Perfect nonbinary AN codes with distance three. -Information and Control, 1975, v. 27, N 4, p. 336-348.

102. Hartmann C.R.P., Tzeng K.K. A bound for arithmetic codes of composite length. // IEEE Trans., 1972, v. IT-18, N 2, p. 308.

103. Hwang T.-Y., Hartmann C.R.P. Some results on arithmetic codes of composite length. // IEEE Trans., 1978, v. IT-24, N 1, p. 93-99.

104. Lippmann R. An introduction to computing with neural nets. // IEEE ASSP Magazine, 1987, April. p. 4-22.

105. Liu J. J., Rudolph L.D. A direct method of computing the GNAF of an integer. // IEEE Trans., 1975, v. C-24, N 10, p. 1042-1043.

106. Mandelbaum D. Multivalued arithmetic burst error codes. // IEEE Int. Conv. Rec., 1966, v. 14, pt. 7, p. 54-59.

107. Mandelbaum D. Arithmetic codes with large distance. // IEEE Trans., 1967, v. IT-13, N 2, p. 237-242.

108. Mandelbaum D. A comparison of linear sequential circuits and arithmetic sequences. // IEEE Trans., 1967, v. EC-16, N 2, p. 151-157.

109. Massey J.L. Survey of residue coding for arithmetic errors. Intern. Comp. Center Bull./ UNESCO, Rome, Italy. - 1964, v. 3, N 4, p. 3-17.

110. Massey J.L., Garcia O.N. Error correcting codes in computers arithmetic. -In: Advances in information sciences/ Ed. by J.T. Tou. N.Y.: Plenum Press, 1971, v. 4, p. 273-326.

111. Neumann P.G., Rao T.R.N. Error-correcting codes for byte-organized arithmetic processors. // IEEE Trans., 1975, v. C-24, N 3, p. 226-232.

112. Peterson W.W. On checking an adder. IBM J. Res. Dev., 1958, v. 2, N 2, p. 166-168.

113. Preparata F.P. On the representation of integers in nonadjacent form. -SIAM J. Appl. Math., 1971, v. 21, N. 4, p. 630-635.

114. Rao T.R.N. Biresidue error-correcting codes for computer arithmetic. // IEEE Trans., 1970, v. C-19, N 5, p. 398-402.

115. Rao T.R.N. Error correction in adders using systematic subcodes. // IEEE Trans., 1972, v. C-21, N 3, p. 254-259.

116. Rao T.R.N., Garcia O.N. Cyclic and multiresidue codes for arithmetic operations. // IEEE Trans., 1971, v. IT-17, N 1, p. 85-91.

117. Rao T.R.N., Trehan A. Single-error-correcting nonbinary arithmetic codes. // IEEE Trans., 1970, v. IT-16, N 5, p. 604-608.

118. Reitwiesner G.W. Binary arithmetic. In: Advances in computers/ Ed. by F.L. Alt. -N.Y.: Academic Press, 1960, v. 1, p. 231-308.

119. Seguin G. Bounds for certain cyclic AN codes. Information and Control, 1973, v. 23, N1., p. 41-47.

120. Tsao-Wu N.T., Chang S.-H. On the evaluation of minimum distance of binary arithmetic cyclic codes. // IEEE Trans., 1969, v. IT-15, N 5, p. 628-631.

121. Zhang D. Parallel designs for Chinese remainder conversion // Proc. Int. Conf. Parallel Process (17-21 Aug. 1987). University Park, Pa, 1987. P. 557 559.

122. Zhang D. Parallel VLSI neural sections designs. Springer, 1998. - 257 p.