«.г РАЗРАБОТКА НЕЙРОННЫХ МОДЕЛЕЙ ДЛЯ КОРРЕКЦИИ ОШИБОК В КОМПЬЮТЕРНЫХ МОДУЛЯРНЫХ ВЫЧИСЛЕНИЯХ ...»

ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ

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

Разработка нейронных моделей для коррекции

ошибок в компьютерных модулярных

вычислениях

Москва

Российская государственная библиотека

diss.rsl.ru

2006

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

Разработка нейронных моделей для коррекции ошибок в

компьютерных модулярных вычислениях : [Электронный ресурс] : Дис. ... канд. физ.­мат. наук

 : 05.13.18. ­ Ставрополь: РГБ, 2005 (Из фондов Российской Государственной Библиотеки) Математическое моделирование, численные методы и комплексы программ Текст воспроизводится по экземпляру, находящемуся в фонде РГБ:

Левченко, Александр Юрьевич Разработка нейронных моделей для коррекции ошибок в компьютерных модулярных вычислениях Ставрополь  Российская государственная библиотека, 2006 (электронный текст) Ставропольский государственный университет

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

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

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

ДЛЯ КОРРЕКЦИИ ОШИБОК

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ Диссертация на соискание учёной степени кандидата физико-математических наук

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

Ставрополь - Оглавление Введение Глава 1. Современное состояние теории и практики информационных 1.1. Анализ и общая классификация информационных методов контроля кодирования и обработки данных в СОК.

д 1.3.2. Арифметический вес и арифметическое расстояние. Глава 2. Математическая модель гибридного корректирующего кода, 2.1. Гибридный код AN-СОК, его корректирующие способности. 2.2. Действия над числами, представленными в коде AN-СОК. 2.4. Оценка увеличения длины двоичного кода, обусловленного перехоS * 2.5. Рещение проблемы внутренней избыточности двоичного кода СОК. 2.6. Обнаружение, локализация и исправление ошибок в коде AN -СОК. Глава 3. Нейросетевые модели для обнаружения и исправления ошибок в 3.2.1. Модифицированная нейронная сеть конечного кольца. 3.2.2. Нейронные сети коррекции ошибок в коде AN-СОК для 3.2.3. Коррекция искаженных разрядов двоичного представления 3.3. Сеть Хэмминга. Использование нейронной сети Хэмминга для,^ Актуальность темы. Развитие средств вычислительной техники сонровождается ростом производительности машин, усложнением их конструкций и расширением областей нрименения. Это обусловливает ностоянный интерес к проблеме повышения надежности работы машин [30]. Проблема помехоустойчивости относится к числу тех проблем, значение и актуальность которых с течением времени не только не уменьшаются, а даже увеличиваются Л [36]. Решение этой проблемы техническими средствами требует больших финансовых затрат; повышение надежности информации при этом ограничено уровнем развития техники и сколь-нибудь значительные достижения в этой области требуют новых технических решений. Другим путем решения задачи повышения достоверности является использование специальных процедур, основанных на применении помехоустойчивых (корректируюших) кодов. Этот путь не содержит никаких принципиальных ограничений. Более того, при выборе подходяшего кода, обладаюшего необходимой корректируюшей способностью, можно заметно снизить требования к надежности самого технического оборудования, сделать его более простым и дешевым [5].

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

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

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

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

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

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

Достоинствами AN -кода являются - простота процедур кодирования и декодирования;

- возможность обнаружения одиночных ошибок при малом увеличении двоичного представления исходного числа (например, при А = 3 не более - использование остаточных кодов, как представителей ЛЛ^-кодов, обеспечивает параллелизм при выполнении действий над информационными и I К основному недостатку AN-кола отнесем снижение скорости выполнения арифметических операций за счет увеличения разрядности числа.

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

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

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

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

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

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

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

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

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

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

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

*' - компьютерное моделирование исследуемых методов коррекции ощибок.

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

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

Научная новизна работы заключается в следующем:

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

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

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

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

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

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

7. Проведено сравнение алгоритма коррекции ошибок в коде AN-СОК и метода проекций, основного метода коррекции ощибок в коде СОК, а также получена формула для определения процента обнаруженных ощибок для кода 8. Получены достаточные условия для допустимой величины рассеяния недиагональных элементов весовой матрицы W^'"' слоя MAXNET сети Хэмминга, гарантирующие применимость матрицы W^"*^ на протяжении всего процесса функционирования слоя MAXNET.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Современное состояние теорни н нрактики информанионных методов контроля работы ЭВМ.

1.1. Анализ и общая классификация информационных методов контроля работы вычислительных средств.

В настоящее время невозможно представить себе сколько-нибудь сложную автоматическую систему без того, чтобы ее центральную частью не составляли вычислительные мащины [5]. ЭВМ имеются практически во всех предметах, неотъемлемо связанных, а порою и определяющих жизнь современного человека. ЭВМ можно определить как универсальный преобразователь информации, а реализуемый в ней вычислительный процесс — как процесс преобразования информации. С этой точки зрения любые выполняемые ЭВМ операции могут быть сведены к следующим трем классам: передача информации, арифметические и логические преобразования. При передаче информации кодовое (мащинное) слово передается в пространстве (между отдельными блоками и устройствами мащины) или во времени (хранение информации). Передача информации в пространстве и хранение являются взаимно однозначными преобразованиями, при которых входное слово, поступающее на устройство или схему передачи (хранения) информации, и выходное слово на выходе устройства (схемы) совпадают [42, 43]. При выполнении операции любого из указанных классов основным требованием, предъявляемым к результату функционирования ЭВМ, является достоверность результата операции, подразумевающая правильность работы вычислительной мащины.

Функции по контролю правильности функционирования ЭВМ в целом или ее отдельных устройств возлагаются на систему контроля.

Система контроля должна строиться с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарущения. При этом надо различать следующие виды ощибок результата [70]:

1) возникающие из-за погрещностей в исходных данных;

2) обусловленные методическими погрещностями;

3) появляющиеся из-за возникновения неисправностей в работе мащины.

Первые два вида ошибок не являются объектом для работы системы контроля. Конечно, погрешности перевода или представления: числовой информации в разрядной сетке автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная ее максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно.

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

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

Информационная избыточность проявляется в представлении команд и данных ЭВМ кодами с дополнительными разрядами, используемыми в процедурах контроля и коррекции ошибок.

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

Алгоритмическая избыточность предполагает выполнение решения задачи по разным алгоритмам (программам) с проверкой получаемых результатов на На практике системы автоматического контроля правильности работы ЭВМ строятся в основном на использовании информационной избыточности в сочетании с элементами избыточностей других типов [43].

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

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

Принадлежность слова к разрещенным или запрещенным словам определяется правилами кодирования, и для различных кодов эти правила различны.

Способность кода обнаруживать или исправлять ошибки определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова п, то кодовое расстояние может принимать значения от 1 до «. Минимальным кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде.

* Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1. Простой (неизбыточный) код имеет минимальное расстояние /„,;„ = 1. Для избыточных В общем случае, чтобы корректирующий код обнаружить все совокупности из / или меньшего числа ошибок, должно выполняться условие d^^ > / +1.

Корректирующий код может исправлять все совокупности из к или меньщего числа ощибок лищь в том случае, если d^ > 2Л: +1 [1, 16,42,43,48].

К настоящему времени разработано много различных помехоустойчивых кодов, отличающихся друг от друга основанием, расстоянием, избыточностью, структурой, функциональным назначением, корреляционными свойствами, алгоритмами кодирования и декодирования, физическим свойствам кода как сигнала. В связи с этим можно предложить различные классификации существующих корректирующих кодов, взяв за основу тот или иной критерий классификации. В работах [1, 7, 8, 16, 35, 37, 42, 43, 48] можно найти следз^ощие классификации помехоустойчивых кодов.

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

По структуре и алгоритмам кодирования и декодирования можно выделить следующие коды.

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

При другом нодходе коды можно разделить на линейные и нелинейные.

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

* В циклических кодах каждое слово содержит все свои циклические перестановки. Все п циклических перестановок (слова длины п) образуют цикл. В квазициклических кодах цикл образуется на числе символов п-1 или, реже, пЦиклические коды важны как с точки зрения математического описания, так и для построения и реализации кода.

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

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

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

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

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

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

Под арифметичностью кода следует понимать равносильность информационной и контрольной частей относительно любой арифметической операции.

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

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

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

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

Минимальное расстояние кода d^^m = 2, поэтому код с проверкой четности обнаруживает все одиночные ошибки и, кроме того, все случаи нечетного числа ошибок (3, 5 и т.д.). При одновременном возникновении двух или любого другого четного числа ошибок код с проверкой четности не обнаруживает ошибок.

При контроле по нечетности контролируется полное пропадание информации, поскольку кодовое слово, состоящее из О, относится к запрещенным.

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

Интенсивная реализация методов помехоустойчивого кодирования в ЭВМ началась с памяти. Практически во всех выпускаемых машинах введено исправление одиночных ошибок и обнаружение двойных ошибок в оперативной памяти с помощью кода Хэмминга. В различных устройствах внешней памяти для обнаружения и исправления пакетов ошибок используются циклические коды. Коды Хэмминга применяются и в сверхоперативной памяти [30].

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

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

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

Корректирующее число длиной к разрядов описывает 2*^ состояний, соответствующих отсутствию ощибки и появлению ошибки в /-М разряде. Таким образом, должно соблюдаться соотнощение Из этого неравенства следует, что пять контрольных разрядов позволяют передать в коде Хэмминга от 11 до 26 информационных разрядов и т.д. Таким образом, избыточность кода Хэмминга значительно выще избыточности кода с проверкой на четность [43].

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

При этом различают числовой и цифровой методы контроля.

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

При этом надо иметь в виду, что величина модуля Р существенно влияет на качество контроля; если P = q (q - основание системы счисления, в которой выражено число) и имеет место числовой контроль, то контролируется только младший разряд числа и контроль как таковой не имеет смысла; для P = q'" справедливы аналогичные соображения, так как опять не все разряды числа (если т"-,Pn, которые называют основаниями или модулями системы. Под системой остаточных классов (СОК) понимают такую непозиционную систему счисления, в которой любое целое неотрицательное число Л можно представить в виде набора остатков от деления этого числа на выбранные основания системы (наименьших неотрицательных вычетов по модулям Р(, i = \,n) [2, 5, 77, 83], т.е.

где ai =N-\ — •Pi, i = \,n, или так: а,- s A'^(mod р,), i = l,n.

Здесь и далее формула [х] означает целую часть числа х, т.е. наибольшее целое число, не превосходяш;ее х. В дальнейшем при описании операций, выполняемых по некоторому модулю, например для изображения того факта, что а,- является наименьшим неотрицательным вычетом N по модулю р,, наряду с формулой а,- =N{mod pi) будем использовать записи: а,- =\N\ ИЛИ Для начала будем полагать, что основания СОК pj, Р2,..., р„ являются взаимно простыми числами. В теории чисел доказано, что если pi, Р2» «-ч Рп взаимно простые между собой, то описанное дифрами «j, а2,..., а„ представление числа N является единственным (Китайская теорема об остатках (КТО)) [5, 65, 77, 94]. При этом диапазон однозначно представимых чисел в заданной СОК есть интервал где D = piP2-...-Pn- Число Л'^, удовлетвоO,D), ряюшее условию Л е [О, D), будем называть правильным числом.

В системе остаточных классов нет естественного разделения чисел на положительные и отрицательные. Поэтому существует несколько способов введения отрицательных чисел. По-видимому, удобнее всего представлять отрицательные числа в виде дополнения абсолютной величины числа до веЛИЧИНЫ D:

В этом случае, в качестве нуля выступает число Р (Р = —, если D:2, иначе, где D = piP2'...'Pn)- Положительными числами являются числа, леР= жащие в интервале (о, Р), а отрицательными - числа в интервале {Р, D).

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

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

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

Пусть операнды А и В представлены соответственно остатками «• и /?,• по основаниям р^, / = 1,и,т.е.

Тогда где при этом в качестве цифры результата берется соответственно Интересно, что если отрицательные числа в СОК определяются выражением (1.2.1.2), то формулы (1.2.1.3), (1.2.1.4) оказываются справедливыми для чисел любого знака.

К модульным операция также относят и деление целых чисел без остатка:

пусть в СОК с взаимно простыми основаниями pi, Р2,..., р„ числа А и В имеют вид Таким образом, деление без остатка двух чисел в СОК осуществляется путем модульного умножения делимого на мультипликативную обратную величину делителя. Величина является однозначно определена, если Д- и Pi взаимно простые числа.

Пусть для какого-либо модуля /?,- остаток Д- ранен нулю. Это означает, что Pi является делителем числа В. Но поскольку число А по условию делится на В без остатка, то основание Pi должно быть также делителем А. Следовательно, а, = О и соответствующая цифра частного является неопределенной:

Однако раз число В делится на /?,, то это число заведомо не может быть меньще, чем Pi, и поэтому {A/B) а комплексом остатков по заданной системе модулей:

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

На диапазон возможного изменения наложим ограничение. Для этого будем считать, что для однозначного представления числа А достаточно к остатков, причем к кп.Зарабочие основания примем основания pi, р2,..., р^.

Диапазон однозначного представления по этим основаниям, соответственно, равен Pjt = Р\Р2'-'Рк- Таким образом, при представлении числа Ле|»р остатками а^, aj,..., а„ используется г = п-к дополнительных остатков.

Другими словами, из представления А{а1,а2,...,а„) можно выбросить любые г остатков без ущерба для однозначности представления числа А, вследствие чего остаточный код является несистематическим или неразделимым кодом.

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

Рассмотренный выше остаточный код, который может контролировать ошибки, представляет собой нелинейный код, называемый /?-кодом [77].

В остатках можно построить и линейный корректирующий код; такой код называют L -кодом. Для его построения достаточно снять ограничение на попарную взаимную простоту оснований.

Интересно отметить, что снятие условия попарной взаимной простоты оснований приводит к тому, что избыточность в представлении числа А появляется не только за счет сокращения числа рабочих оснований, но и за счет того, что диапазон представления числа А будет меньше 1*1^.

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

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

Будем в дальнейшем числа, меньшие Р,^, называть правильными, а большие Р^ - неправильными. Любое искажение цифры по одному какому-либо разряду (основанию) превращает число в неправильное и тем самым позволяет обнаружить наличие искажения. Под одиночной ошибкой будем понимать искажение какой-либо одной цифры любого «-разрядного представления, причем это искажение ограничивается лишь величиной основания. Под /и-кратной ошибкой будем понимать искажение т цифр представления.

Множество Р„ комбинаций можно преобразовать в метрическое пространство. Метрику введем так, чтобы она согласовывалась как со свойствами системы остаточных классов, так и с механизмом возникновения ошибок при функциональных преобразованиях кода. Поскольку в кодовых комбинациях отсутствз^ют межразрядные связи, то действие помех при выполнении операций над комбинациями может проявляться лишь в виде независимой трансформации одного или нескольких символов исходного представления. Это позволяет механизм воздействия помех отождествлять с операцией, например, сложения в СОК произвольного числа АеР„ с информационным числом Пусть А{а1,а2,...,а„) — переданное сообщение. Тогда принятое сообщение где ! = («,+Д,,«2+А2,...,«„+Д«).

Глубиной ошибки А- назовем величину а} -ог;, которая изменяет цифру а,в результате возникновения ошибки [77]. Глубина ошибки может иметь значение от А,- = 1 до Д,- = р,- - 1. Будем считать сообщение безошибочным, если Если же Л > Р;^, то соответствующее представление назовем ошибочным.

Очевидно, что если Л > Р^, то Л,- т о. Будем называть {д} комплексом ошибок.

Для того, чтобы оценить свойства и некоторые предельные соотношения способности остаточных кодов контролировать ошибки, введем понятие веса W\A Р ) числа А. Вес числа А будем считать равным числу его ненулевых остатков. Такое определение веса числа соответствует определению веса кода в метрике Хемминга [84].

Величина W\A\1 ) задается формулой где Определенный таким образом вес комплекса интерпретируется как количество ненулевых остатков в представлении числа в СОК.

Понятие веса числа А, представленного остатками, может быть использовано для определения понятия расстояния между двумя точками пространства, каждой из которых соответствует число А\ и Aj соответственно. Расстояние d^^^^ между точками пространства А-^ и Aj определим как вес разности Введенное таким образом расстояние является метрикой пространства остатков (в [95] показано, что оно удовлетворяет свойствам рефлексивности, симметричности и неравенству треугольника), что позволяет сделать вывод о том, что рассматриваемое пространство остатков является метрическим.

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

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

В этой связи уместно привести следующее предложение.

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

Очевидно, что код тем лучше приспособлен к исправлению ошибок, чем больше отличаются друг от друга числа в представлении кода, т. е. чем больше кодовое расстояние. При этом между различными числами кодовое расстояние будет различным.

Теорема 1.2.2.1. В избыточном непозиционном коде минимальное кодовое расстояние ^/^jn равно минимальному весу его ненулевых векторов:

В [95] показано, что верхняя граница минимального расстояния кода с к информационными ^ п-к проверочными основаниями равна причем при заданных параметрах кода пик выбор величины конкретных оснований pi не оказывает влияния на значение верхней границы его минимального расстояния.

Теорема 1.2.2.2. Корректирующий код может обнаружить все совокупности из / или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше /, т.е. d^ > / +1.

Теорема 1.2.2.3. Корректируюший код может исправлять все совокупности из к или меньшего числа ошибок лишь в том случае, если минимальное расстояние кода больше удвоенного числа ошибок, т.е. ^„(„ >2к + \.

Для кода СОК с взаимно простыми основаниями (Л-кода) справедливо следующее утверждение.

Теорема 1.2.2.4. Корректирующий iг-кoд имеет минимальное расстояние d в том и только в том случае, если степень избыточности R не меньще произведения любых d-\ оснований заданной системы остаточных классов:

Таким образом, минимальное расстояние кода является важнейщей характеристикой кода. Тем не менее, следует помнить, что неравенства в теоремах 1.2.2.2, 1.2.2.3 свидетельствуют о том, что минимальное расстояние кода не в полной мере описывает корректирующие свойства кода. Например, код в остатках с одним избыточным основанием, позволяет обнаружить 100% одиночных и почти 90% двойных ощибок [77, 95].

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

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

Методом, которым можно воспользоваться для обнаружения ошибок, является непосредственный перевод числа, представленного остатками «j, «2 >..., а„, в позиционную систему счисления (ПСС). При этом справедливо утверждение [86, 95].

Теорема 1.2.3.1. Пусть Л = (а,,«2,..-,«„), 0 < / i < i \ - точный результат выполнения арифметической операции в СОК, а Л'=(«,',«2',...,«„') - полученный результат вычислений в СОК. Тогда, если ai=ai при i^l и ai^ai' (/ = 1,и), то имеет место неравенство Л'> i\, которое обнаруживает ошибку.

Основой метода обнаружения ошибок с помощью ОПС является следующая теорема [94].

Теорема 1.2.3.2. Пусть Л', полученный результат вычислений в СОК, в соответствующей ОПС имеет вид ^'=(ai',a2'>-»«A+r')' Тогда А' лежит в диапазоне разрешенных значений, когда и только когда избыточные цифры ОПС являются нулевыми, т.е. a^+j'= О для j = 1,2,...,г.

Таким образом, в качестве критерия безошибочного приема числа А используется тот факт, что избыточные цифры ОПС для правильного числа равны нулю. Достоинством данного метода является то, что если стоит задача только установления факта возникновения ошибок, то при неравенстве нулю любой разрядной цифры а^^+Г» •• °^А+Г' процесс перевода прекращается. Это позволяет сокращать в среднем объем вычислений, требуемый для обнаружения ошибок, по сравнению с методом, основанным на использовании ПСС.

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

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

РОССИЙСКАЯ

ГОСУДАРСТВЕННАЯ

БИБЛИОТЕКА

Выше было указано, что процесс обнаружения ошибок в остаточных кодах сводится к сравнению числа А' с величиной диапазона Р^. Следовательно, вычисляемая характеристика должна быть позиционной, так как она должна определять положение числа А' внутри диапазона |*|р. В общем случае мы будем обозначать позиционные характеристики символом ^|^4|^ ).

В конечном итоге процедура обнаружения ошибок в остаточных кодах сводится к вычислению такой позиционной характеристики я-м| р ), что Иначе говоря, если л-|л|р ]= О — ошибки нет, в противном случае произошла ошибка. По характеру изменения позиционные характеристики можно разделить на линейные и нелинейные. Линейные позиционные характеристики монотонно изменяются (возрастают или убывают) при возрастании аргумента, а нелинейные изменяются немонотонно.

Примером нелинейной позиционной характеристики является функция ранга числа ЛА^р ).

Рангом Л^р ) числа А называется целое положительное число, показыч Чу, I вающее, сколько раз диапазон системы Р„ был превзойден при переходе от представления числа в системе остаточных классов к его позиционному представлению через систему ортогональных базисов. Таким образом, если число А в системе остаточных классов с взаимно простыми основаниями рх, /72,..., Рп ( п р и ч е м Рп=Р\Р2 •...-/?„) и м е е т в и д то, воспользовавшись методом ортонормированных векторов вида где 1 < /и,- < Pi такое, что 5,- = l(mod р,), / = 1,«, число А может быть представлено формулой где ЛА Р ) - функция ранга числа А, которая принимает такое значение, что А находится в диапазоне W р.

В работах [94] и [95] предлагается воспользоваться для обнаружения ошибки функцией нормированного ранга ^^Iv^lp]. Для этого было отмечено, что если информационными основаниями являются pi, /?2,..., р^, то ранг числа принимает значения из интервала поэтому, введя избыточные основания p^^+i,..., р„ так, чтобы p^+j '—'Рп >^л> то нормированный ранг числа - позиционную характеристику, позволяюшую обнаружить ошибки, — определили формулой где РпPi Для обнаружения ошибки следует оценить верность неравенства Если неравенство верное, то можно полагать, что ошибки нет, в противном случае - произошла ошибка.

Вычисление r\A\'^pj с помошью (1.2.3.1) при достаточно большом Р^„ становится сложным, так как рост аппаратных затрат в однотактных сумматорах пропорционален Р^^„. В силу этого, в [94] вместо нахождения нормированного ранга гЩ'*^,! предлагается вычислять его остатки по избыточным модулям:

где При этом, полагая, то на избыточные модули наложено ограничение то для всякого правильного числа справедливо Т.е. проверка на правильность числа сводиться либо к проверке на одинаковость остатков гк+1,..., гп, либо к проверке условия ri««) определяют формулой где г- - целые числа, выбираемые произвольным образом.

В [95] доказано, что процедура обнаружения ошибки в избыточном остаточном коде с использованием позиционной характеристики ядра числа сводится к вычислению i?/>^|/i|* j с последующим ее сравнением с [р^/р„]+1.

При этом, если /?p^|^|^ ] 5;

3) длина п кода определяется неравенством где /, U /2 = {1,2,.,,,/} И /, О/2 = 0.

Исследованиями возможности обобщения конструкции таких кодов занимались И.М. Бояринов и Г.А. Кабатянский [13]. По аналогии с кодами для передачи сообщений они ввели конструкцию арифметического ;w-мерного A = HOK^^^ - l ), Ni=n/ni, («,,иу)=1; /,y = l,2,.,,,m.

Другой подход к построению арифметических кодов с dj^^j^ > 3 был основан на модификации AN-кодов; исследования подобного типа рассмотрены в работах [27, 28, 30, 31, 34, 41, 62, 71, 104, 121].

В последнее время заметно усилился интерес к г -ичным арифметическим кодам. Ограничимся результатами для произвольного г, относящимися к «до-циклическому» периоду развития Л7^-кодов. По-прежнему мощность кода В будет определяться как наименьшее положительное целое число, арифметический вес произведения которого на А меньше минимального расстояния кода.

Па простое ограничение для генератора г-ичного ЛЛ^^-кода с с/^ш =3 указали И.М. Бояринов и Г.Л. Кабатянский [12].

Лемма 1.3.3.1. Если А - генератор г-ичного ЛЛГ-кода, исправляющего одиночные ошибки, то А>г^ +г.

Им же принадлежит обобщение теоремы 1.3.3.4 на г-ичный случай.

Теорема 1.3.3.7. г-ичный AN-кол исправляет одиночные ощибки Е = ±аг', 1«p-3>->ai,ao), могут рассматриваться как целые числа Итак, имеется р-1 ненулевых двоичных (p-l)-разрядных чисел, которые делятся на Л и могут быть получены одно из другого циклическим сдвигом.

Если добавить к ним слово, состоящее целиком из нулей, то тем самым будет построен двоичный циклический AN-код с генератором Л = (2^"^ -l)/p и количеством слов В = р, где р — простое число и 2 — первообразный корень по модулю р.

Ни Мандельбауму [115], ни О.Б. Соколову и И.И. Еникееву [73] не удалось точно определить минимальное расстояние предложенного ими кода; это было сделано Бэрроузом [97], Гото н Фукумура [108] и Чжаном и Цзао-У [99].

которых модулярные расстояния между всеми парами разУ1Л'^-КОДЫ, ДЛЯ личных кодовых слов одинаковы, естественно называть эквидистантными.

Так генератор А = (2^"^ -l)/p, где р - простое число и 2 - первообразный корень по модулю р, порождает эквидистантный циклический AN-код длины л = р - 1, содержащий р слов, с dj^m = (р ± l)/3.

Еще один пример циклического AN-кода был рассмотрен ранее. В случае если -2, но не 2 является первообразным корнем по простому модулю р, то, как следует из определения циклического кода, генератор А = р порождает циклический совершенный AN-код длины n = {p-i)/2 с /„,;„ = 3. Если 2 является первообразным корнем по модулю р, то генератор А = р также порождает совершенный ^Л'^-код длины n = {p-l)/2 с c/^jn = 3, однако этот код уже не будет циклическим, и поскольку в этом случае А = [г^'^"^^'^ +^уВ, то, следуя Берлекэмпу [7], будем называть его негациклическим.

Месси и Гарсиа [118] предложили для оценки циклических У4Л^-кодов использовать сходное со скоростью передачи отношение двоичного логарифма числа кодовых слов к двоичному логарифму общего количества целых чисел BZ, Действительно, эта величина, которую по аналогии будем называть скоростью, является естественной и удобной для сравнения различных кодов; при отсутствии кодирования, т. е. когда Л = 1, скорость R = \ если же имеется только одно кодовое слово, т. е. 5 = 1, то скорость /? = О. Величина Iog2 А называется избыточностью. Как видно, эквидистантные AN-коды с В-р я ^min =(;?±l)/3 и совершенные AN-коды с А = р и /„;„ =3 являются в определенном смысле предельными случаями циклических ^iV-кодов: первые имеют большую корректирующую способность, но низкое значение скорости;

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

Пусть числа, меньшие т = 2"-\, могут быть разделены на три класса:

L^=(o,2"/2), множество целых чисел /, а^(00 И о) = w(o 1 Ою) = 2, w(3?/5) = ^(^15) - ^(01111) = vv^lOOOi] = 2 ). По числу AN^ однозначно определяется //;. Пусть число Ni^ - ближайщее из данных к NQ с учетом направления обхода (соответственно ANi^ — ближайщее к ANQ ); 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. Геометрическая модель СОК целесообразно ввести два расстояния: одно, 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), = 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» •• Л, равна откуда имеем т.е.

Из неравенств (2.4.1), (2.4.2) следует, что Z Iog2 4- (P/ -1) - Z l0g2 {pi-l) + k\< L Гибрид - LcOK ~ Вышеизложенное можно обобщить на случай исправления ошибок в нескольких (двух, трех и так далее) разрядах представления числа в гибридном коде, для этого достаточно обеспечить НС соответствующим числом избыточных каналов-оснований.

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, тогда и таблица коррекции ошибки для данного AN -кода имеет следующий вид.

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

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

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

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

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

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

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

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

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

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

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

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

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

Важным достоинством сети Хэмминга считается небольшое количество взвешенных связей между нейронами. Например, 100-входовйя сеть Хопфилда, кодирующая 10 различных векторных классов, должна содержать 10000 взвешенных связей с подбираемыми значениями весов. При построении аналогичной сети Хэмминга количество взвешенных связей уменьшается до 1100, из которых 1000 весов находятся в первом слое и 100 - в слое MAXNET. Выходной слой в этом случае не учитывается, поскольку сеть Хэмминга, аналогичная сети Хопфилда, является ассоциативной [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,...А Итак, можно принять Таким образом, сочетание СОК {AN-СОК) и ИНС по максимуму правдоподобия обеспечивает обнаружение и 100%-ую коррекцию ошибки. Изложенный подход позволяет создавать высокопроизводительные и надежные вычислительные структуры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, ^2 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, Xal. - С. 68-82.

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

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

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

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

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

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

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

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

радио, 1969.-168 с.

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

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

- 272 с.

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

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

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

3, с. 533-536.

34. Ерош И.Л., Ерош С.Л. Арифметические коды с исправлением многократных ошибок. // Проблемы передачи информации, 1967, т. 3, вып. 4, с. 72Злотник Б.М. Помехоустойчивые коды в системах связи. — М.: Радио и связь, 1989.-232 с.

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

Связь, 1972.-360 с.

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

38. Информационные системы. Табличная обработка информации / Под ред. Е. П. Балашова, В. Б. Смочова. — Л.: Энергоиздат, Л.О., 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. Комарцева Л.Г., Максимов А.В. Нейрокомпьютеры. - М.: Из-во МГТУ им. Баумена, 2002. - 320 с.

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

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

ФИЗМАТЛИТ,2001.

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

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

56. Левченко А.Ю. Действия над числами, представленными в коде ANСОК. // Физико-математические науки в Ставропольском государственном университете: Материалы 50-й юбилейной научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука — региону», посвященной 60-летию Победы в Великой Отечественной войне. - Ставрополь: Изд-во СГУ, 2005. — С. 122- 57. Левченко А.Ю. Комбинированный код, построенный на базе кода системы остаточных классов. // Труды участников Международной щколысеминара по геометрии и анализу, посвященной памяти Н.В. Ефимова, Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 5-11 сентября 2004 г. - Ростов-на-Дону: Изд-во 0 0 0 «ЦВВР», 2004. - С. 200-201.

58. Левченко А.Ю. О некоторых возможностях помехоустойчивых (корректирующих) кодов. // Современные проблемы математики и информатики:

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

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

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

Ставрополь, 19 декабря 2004 г., Северо-Кавказский государственный технический университет. — С. 457-465.

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

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

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

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

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

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

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

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

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

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

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

72. Сахнюк П.А. Отказоустойчивый непозициопный процессор на основе нейронных сетей в системах управления // Материалы 2-ой международной науч.-техн. конф. "Новые технологии управления техническими объектами".

- Ю ж. -Рос. гос. техн. ун-т. Новочеркасск: 1999. - С. 163-165.

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

4, с. 73-75.

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

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

3, с. 38-42.

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

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

Советское радио, 1973. - 120 с.

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

Мир, 1992.-240 с.

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

80. Червяков Н.И. Геометрическая модель избыточного кода системы остаточных классов // Управляющие системы и машины, Киев, 1988, ХаЗ. - С. 3Червяков Н.И. Надежность и живучесть систем управления и связи, функционирующих в с о к. - Ставроноль: СВВИУС, 1986.

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

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

- 8 4 с.

84. Червяков Н.И. Сумматор в системе остаточных классов. А.С. N 377771,БИХ2 18, 1973.

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

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

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

88. Червяков Н.И., Бережной В.В., Оленев А.А. Устройство для преобразования кода системы остаточных классов в позиционный код с исправлением ощибок. Патент РФ К2 1797119, БИ Ш 7, 1993.

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

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

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

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

93. Червяков Н.И., Непретимова Е.В. Исправление ошибки в системе остаточных классов как следствие метода проекций. // Ученые записки физикоматематического факультета Ставропольского государственного университета. - Ставрополь: Изд-во СГУ, 2002. - С. 112-117.

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

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

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

97. Barrows J.T., Jr. А new method for constructing multiple error correcting linear residue codes. - Coord. Science Lab.AJniv. Illinois, Urbana, 1966, Rep. RBrown D.T. Error detecting and correcting binary codes for arithmetic operations. - IRE Trans., 1960, v. EC-9, N 3, p. 333-337.

99. 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.

100. 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.

101. 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.

^ 102. 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. 161-110.

103. Diamond J.M. Checking codes for digital computers. — Proc. IRE, 1955, v.

104. Floreen P. The convergence of Hamming memory networks // IEEE Trans.

(j - Neural Networks, 1991, vol. 2, N 5, p. 449-457.

105. Gamer H.L. Error codes for arithmetic operations. // IEEE Trans., 1966, v.

\ EC-15,N5,p. 763-770.

106. Goto M. A note on perfect decimal AN codes. - Information and Control, 107. Goto M., Fucumura T. The distance of arithmetic codes. — Memoirs Faculty Eng./Nagoya Univ., Jap., 1968, v. 20, N 2, p. 474-482.

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

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

, 110. 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.

111. 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.

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

-• 113. 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.

* 114. Mandelbaum D. Multivalued arithmetic burst error codes. // IEEE Int.

i Conv. Rec, 1966, v. 14, pt. 7, p. 54-59.

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

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

'i 117. Massey J.L. Survey of residue coding for arithmetic errors. - Intern. Сотр.

j Center Bull./ UNESCO, Rome, Italy. - 1964, v. 3, N 4, p. 3-17.

118. 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, t 119. 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.