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

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

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


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

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

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

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

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

вычислениях

Москва

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

diss.rsl.ru

2006

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

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

компьютерных модулярных вычислениях : [Электронный

ресурс] : Дис. ... канд. физ.­мат. наук

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

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

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

Левченко Александр Юрьевич.г РАЗРАБОТКА НЕЙРОННЫХ МОДЕЛЕЙ ДЛЯ КОРРЕКЦИИ ОШИБОК В КОМПЬЮТЕРНЫХ МОДУЛЯРНЫХ ВЫЧИСЛЕНИЯХ 05.13.18 - Математическое моделирование, численные методы и комплексы программ Диссертация на соискание учёной степени кандидата физико-математических наук

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

Ставрополь - Оглавление Введение Глава 1. Современное состояние теории и практики информационных методов контроля работы ЭВМ. 1.1. Анализ и общая классификация информационных методов контроля работы вычислительных средств. У' 1.2. Корректирующий код системы остаточных классов 1.2.1. Система остаточных классов (СОК). Принципы кодирования и обработки данных в СОК.

1.2.2. Корректирующие свойства кода СОК. 1.2.3. Способы обнаружения ошибок. 1.2.4. Методы локализации и исправления (коррекции) ошибок.

1.3. Л//-коды, их корректирующие способности. 1.3.1. Канонические представления целых чисел. д 1.3.2. Арифметический вес и арифметическое расстояние. 1.3.3. AN-KOjibi. ^ * 1.3.4. Циклические/i//-коды. Выводы по главе 1 Глава 2. Математическая модель гибридного корректирующего кода, обнаруживающего и исправляющего ошибки, возникающие при обра ботке данных.

2.1. Гибридный код AN-СОК, его корректирующие способности. 2.2. Действия над числами, представленными в коде AN-СОК. 2.3. Геометрические модели кодов СОК и AN-СОК. 2.4. Оценка увеличения длины двоичного кода, обусловленного перехо S дом от кода СОК к гибридному коду. * 2.5. Рещение проблемы внутренней избыточности двоичного кода СОК. 2.6. Обнаружение, локализация и исправление ошибок в коде AN -СОК..^, Выводы по главе 2 Глава 3. Нейросетевые модели для обнаружения и исправления ошибок в компьютерных модулярных вычислениях. 3.1. Нейронная сеть конечного кольца. 3.2. Нейросетевая реализация гибридного кода AN-СОК. 3.2.1. Модифицированная нейронная сеть конечного кольца. 3.2.2. Нейронные сети коррекции ошибок в коде AN-СОК для f исправления искаженных остатков. 3.2.3. Коррекция искаженных разрядов двоичного представления ^Л'^-остатков. - 3.3. Сеть Хэмминга. Использование нейронной сети Хэмминга для обнаружения и исправления ошибок в нейрокомпьютерах, функциони рующих в СОК и/1Л^-СОК. Выводы по главе 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. Для избыточных кодов й?„|„ 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

J^ Требуемое число контрольных разрядов (разрядность корректируюш;

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

Корректирующее число длиной к разрядов описывает 2*^ состояний, соот ветствующих отсутствию ощибки и появлению ошибки в /-М разряде. Таким образом, должно соблюдаться соотнощение ИЛИ 2''-к-\т.

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

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

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

При числовом методе контроля код заданного числа определяется как наименьший положительный остаток от деления числа на выбранный модуль Р:

где [ ] - целая часть от деления числа.

При этом надо иметь в виду, что величина модуля Р существенно влияет на качество контроля;

если P = q (q - основание системы счисления, в кото рой выражено число) и имеет место числовой контроль, то контролируется только младший разряд числа и контроль как таковой не имеет смысла;

для P = q'" справедливы аналогичные соображения, так как опять не все разряды числа (если тп) участвуют в контроле и ошибки в разрядах старше т во обще не воспринимаются.

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

При цифровом методе контроля контрольный код числа образуется деле нием суммы цифр числа на выбранный модуль при выполнении условий •Р " 7* Р или г^=Х«/(modP).

Возможны два пути получения контрольного кода: 1) непосредственное деление суммы цифр на модуль Р;

2) суммирование цифр по модулю Р.

Второй путь весьма привлекателен, так как если ai Р, то контрольный код получается только операцией суммирования. Это существенное преиму щество цифрового метода контроля.

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

к одному из классов операций, выполняемых ЭВМ, относятся логические, операции;

их контроль для верного функционирования ЭВМ не менее важен, чем контроль при передаче информации.

К логическим операциям относятся операции сдвига, логического сложе ния и умножения. Несмотря на их кажуп1уюся простоту, осуществление опе раций контроля сталкивается с рядом трудностей, объясняемых тем, что ло гические операции являются поразрядными операциями [70].

1' ^ Начнем с контроля операции сдвига. Пусть задано число /l = a^a^_,...aiao, имеющее контрольный код г^ = а^^...а/^^.

Обозначим код числа А, сдвинутый влево А (без циклического переноса) и Л^ (с циклическим переносом) (при сдвиге вправо стрелка в обозначении будет повернута направо). Соответствующим образом обозначим и кон трольный код: А = г^ (mod Р);

А = Г2 (mod Р);

Ац = г^ (mod Р).

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

r^^r^+A(modP), (1.1.1) где г^ = 2г^ — сдвинутый влево контрольный код.

Очевидно, что величина А зависит от значений а„ и а^, которые при сдвиге выходят за пределы разрядной сетки.

Если при сдвиге п -разрядного числа старшая единица выйдет за пределы « • разрядной сетки, то это эквивалентно вычитанию а„сг„+, единиц из контроль ного кода сдвинзп:ого числа (где сг„+, - вес (и + l)-ro разряда).

Если при сдвиге контрольного кода выходит за пределы разрядной сетки,), разряд а^ = 1, то это эквивалентно уменьшению контрольного кода на 2* = 1.

Такую потерю надо восстановить прибавлением к контрольному коду едини цы. В общем случае (1.1.1) принимает вид г А ^ fc - ««^«+1 + «it, )(mod 2^ -1). (1.1.2) Веса разрядов кодовой комбинации, представленной в системе с основани ем 2", назначаются следующим образом:

Га„ а„_1 а„_2 а„_з... а^ «2 « s = 1 2^ 2^ веса ai 2^ 2^... 2^ 2^ 2^ ' В результате значения поправок Д для контроля выполнения левого сдвига по модулю будут:

Значение а„ 0 10 Значение at О О 1 Поправка А 0 - 1 1 Значение поправок А = -1 можно заменить ее дополнением до модуля.

Для выполнения сдвига влево с циклическим переносом из старшего раз ряда в младший разряд необходимо уменьшить контрольный код на величи ну а„(сг„+1 -1);

так как о-„+, =1, то этот член равен 0. Следовательно, формула (1.1.2) изменяется:

(1.1.3) Г2 =^^+«A,(mod2^-l).

Пример. Найти контрольные коды для числа /1 = 1,01101010, сдвигаемого влево, при Р = 7 (^ = 3).

Сначала определяем контрольный код исходного числа путем сложения триад по модулю 7:

r ^ s 101 + 101 + 010 = 10l(mod 7).

. Затем определяем Л = О 1010100 и его контрольный код Я^ = 010. На осно Д вании (1.1.2) при а„=1, а,^^ =1 определяем контрольный код сдвинутого чис ла:

г^ = 010-1-001 + 001 = 010(mod 7).

Производится сдвиг с циклическим переносом:

Л^ =0,11010101, для которого контрольный код гд S о I о + 001 = о 11 (mod 7).

Итак, г^ =010, гд^ =011.

При сдвиге вправо происходит потеря младших разрядов числа и кон трольного кода этого числа. Так как сдвиг вправо эквивалентен делению на 2, то Эти потери надо компенсировать. Это означает, что контрольный код сдвинутого вправо числа можно найти по формуле (1.1.5) В зависимости от модуля поправка к контрольному коду в случае простого сдвига принимает следующее значение:

Значение а^ О О 1 Значение аь 0 10 н Поправка Д для:

00 10 01 Р=Ъ 000 100 011 Р= При модифицированном сдвиге вправо, который выполняется по правилу А = \,а„,1а„_2...а2а1', Лд/=1,1а„_1...аз ^2» нроисходит также потеря младших разрядов кодовой комбинации числа и контрольного кода. Для этого случая формула (1.1.5) сохраняет свой вид, но поправки должны быть следующими:

Значение а^ 0 0 Значение ajt, 0 10 Поправка Д для:

? =3 10 01 00 100 001 000 Р= Пример. Найти контрольные коды для числа Л = 1,01011101111, сдвигаемого вправо, при Р = 7.

Решение. Сначала определяем контрольный код для исходного числа пу тем сложения триад по модулю 7:

Затем сдвигается вправо число Л = 0,10101110111 и его контрольный код На основании (1.1.5) при ai =1, а^^ =0, поправки А = 011 определяем конт рольный код: rj5 = 011 + 011S110(mod 7).

Производится модифицированный сдвиг числа Jij^ =1,10101110111, для ко торого контрольный код находим при А = 000: Г2 sOll + 000^011 (mod 7).

Итак, г;

^ =110, г^ =011.

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

(1.1.6) f®=f^+B+f^^odP), где г^+в — контрольный код суммы двух чисел;

гл — инверсия контрольного кода логического произведения двух чисел со сдвигом влево на один разряд.

Пример. Найти контрольный код логической суммы чисел Л = 010100001 и В = 100110101 по модулю 7.

Прежде всего, по изложенным выше правилам определим контрольные ко ды для исходных чисел:

Затем вычислим следующие величины:

Л л 5 = 000100001, Гд= 101;

/ Лл5^ав =001000010, Гд= 011.

После этого определим инверсное значение гл = По формуле (1.1.6) находим контрольный код:

Гф =001 +100 s 101 (mod 7).

Таким образом, Гф = 101.

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

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

(1.1.7) где г—-^ - контрольный код суммы, сдвинутый вправо на один разряд;

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

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

Л = 0101001001, 5 = 1001100001.

Прежде всего, находим:

г^ =10, гд=ОО;

Л + 5 = 1110101010, г^+в=10.

Затем по (1.1.5) вычисляем Определяем:

^ © 5 = 1100101000, /©=01, « Гф =Гф+А = 10, гф =01.

Следовательно, контрольный код логического произведения Итак, Гд =10.

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

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

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

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

В перспективе многообещающим представляется использование арифмети ческих кодов при объединении отдельных машин в вычислительную сеть [30].

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

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

"* Появление и развитие электронных ПЗУ в интегральном исполнении, об ладающих большим объемом памяти при высокой плотности упаковки:

10^4-10^ бит/см^, определило направление использования в СОК табличных методов обработки цифровой информации [38]. Однако построение цифро вых устройств табличного типа даже для 16-и разрядных операндов в двоич ной позиционной системе счисления является нереальным, поскольку это по требовало бы запоминающих устройств емкостью* iP'^l^ =10^' бит. Исполь Д зование СОК, реализующей данный диапазон, требует емкости примерно 10^ бит со временем выборки порядка единиц наносекунд. Такие СОК позволят создать цифровые устройства с быстродействием порядка сотни миллионов операций в секунду. Существенным преимуществом табличных схем в СОК, кроме быстродействия, является схемотехническая и конструктивная мо дульность и функциональная простота [95].

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

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

1.2. Корректирующий код системы остаточных классов.

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

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

(1.2.1.1) где 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:

(1.2.1.2) \-N\j^=\D-N\^.

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

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

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

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

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

Тогда (1.2.1.3) () (1.2.1.4) где при этом в качестве цифры результата берется соответственно Га,- + Д- „ i, i = l,n [5].

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

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

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

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

О О Однако раз число В делится на /?,, то это число заведомо не может быть меньще, чем Pi, и поэтому {A/B){D/pi), где D = piP2 •...•/?„.

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

Если Pi и Pi имеют наибольщий общий делитель di, то остаток а,- также должен делиться на di. Тогда di + f ^' Pi di Pi Pi di Pi di Pi Величина ^,- =0,1,2,..,,^,--1 однозначно определяется остальными цифрами частного, носкольку {А1В)(А1 di )(Dldi) [77].

Проиллюстрируем выщесказанное примерами. В этих примерах принято:

Пример. Пусть /1 = 10, В = 5. Найдем А + В, А-В, АВ и —. В-А, В В данной системе остаточных классов исходные числа имеют вид Л = (0,4,3), 5 = (0,5,5).


Тогда J = (0,1,2);

В Поскольку = 5, TO Так как {A/B){A/5){D/5) = 42, ТО остатки по основаниям Р2 и р^ однознач но определяют частное и, следовательно, неопределенную цифру по модулю 0| = 2.

Pi О Итак, 4 = (2,2,2).

Пример. Пусть А = \0, В = 2. Найдем —.

В В данной системе остаточных классов исходные числа имеют вид Л = (0,4,3), В = (2,2,2).

Тогда О В Поскольку = 4, = 3, - то =|о.з| =0, Так как (^/fi)(D/6) = 35, то остатки по основаниям pi и рз позволяют одно значно определить величину ^2'- ^2=1 Таким образом, — = (5,5,5).

Кроме рассмотренных операций (сложения, вычитания, умножения и де ления без остатка), существуют другие, для выполнения которых необходимо знание величины всего числа, а не только его остатков по некоторым моду лям. Такие операции называют немодульными. К ним относятся следующие операции: определение знака числа и наличия переполнения разрядной сетки (выхода из рабочего диапазона), вычисление абсолютной величины числа, сравнение двух чисел, деление с остатком и другие. Их можно осуществить с помощью вычисления позиционных характеристик и расширения системы оснований (подробнее в [5], [77], [95]). А можно для этой цели привлечь иную систему счисления, в которой не составляло бы труда реализовать ука занные операции. Таким образом, необходимо иметь подходящую систему счисления, а также простые методы перевода из данной системы остаточных классов в новую систему счисления и обратно. Данная задача довольно про сто решается привлечением системы счисления, называемой обобщенной по зиционной системой (ОПС), полиадической или же системой счисления со смешанными основаниями (ССО) [5, 77, 94, 95].

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

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

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

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

Возможность использования кодов в остатках для контроля над ошибками на различных этапах существования информации показана в [5, 6, 77, 80, 81, 87, 88, 89, 90, 94, 95].

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

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

Пусть задана совокупность из п целых положительных взаимно простых чисел /»1, Р2' •• Рп- Пазовем кодом СОК длины Р совокупность представ • лений целых положительных чисел {)АР„, где Р„ = piP2 ••• /'я а комплек •• сом остатков по заданной системе модулей:

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

Р„ - числовой диапазон пред ставления чисел в СОК.

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

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

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

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

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

В остатках можно построить и линейный корректирующий код;

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

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

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

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

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

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

Глубиной ошибки А- назовем величину а} -ог;

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

^, то соответствующее представление назовем ошибочным.

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

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

Величина W\A\1 ) задается формулой где / \ Го, если а, * 0;

^ ^' [1, если а,- = 0.

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

Понятие веса числа А, представленного остатками, может быть использо вано для определения понятия расстояния между двумя точками пространст ва, каждой из которых соответствует число А\ и Aj соответственно. Расстоя ние d^^^^ между точками пространства А-^ и Aj определим как вес разности dA,A, = НА - А2\\ ]= f p -O-,U - Л2)].

Введенное таким образом расстояние является метрикой пространства ос татков (в [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, «..., а„, в позиционную систему счисления (ПСС). При этом справедливо ут верждение [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 •...-/?„) и м е е т в и д то, воспользовавшись методом ортонормированных векторов вида Pi где 1 /и,- Pi такое, что 5,- = l(mod р,), / = 1,«, число А может быть представлено формулой /= где ЛА Р ) - функция ранга числа А, которая принимает такое значение, что А находится в диапазоне W р.

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

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

(1.2.3.2) п = 7= где, У = 1Д, Pj Pi mjkPn,k \),n, = Pi Pn Pj Pi При этом, полагая, то на избыточные модули наложено ограничение то для всякого правильного числа справедливо Т.е. проверка на правильность числа сводиться либо к проверке на одинако вость остатков гк+1,..., гп, либо к проверке условия rir^. Очевидно, что последнее предпочтительнее.

Еш;

е одной позиционной характеристикой, которая может быть использо вана для обнаружения ошибок в избыточном коде СОК, является характери стика, носящая название «ядро числа» [4]. Будем обозначать ее как Rp Mlp I.

Ядро числа А = (а,,«2»•••««) определяют формулой где г- - целые числа, выбираемые произвольным образом.

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

При этом, если /?p^|^|^ ][Ру^//?„]+1, то можно полагать, что ошибки нет, в противном случае — произошла ошибка.

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

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

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

Основным способом коррекции ошибок является метод проекций. Его суть в следующем. Пусть в коде СОК с основаниями pi^ Р2,..., р„ (причем Pk = PxPi •-•Pk ~ величина рабочего диапазона, a Р„ = /?,/?2 •••••Pn ~ велич полного диапазона) в результате какой-либо операции или при передаче чис ла оказалось, что получено число A = {pi.x,a2,....,a^. Назовем число Л,, полу ченное из А зачеркиванием цифры «,•, проекцией числа А по основанию /?,•;

число Aij, полученное из А зачеркиванием остатков а,- и aj, проекцией А по основаниям р/ и ру;

и так далее.

Как и ранее, число А, где Ае[О,Р^), будем называть правильным;

если же Ае[р^,Р„),то А - неправильное число.

Если окажется, что проекции Л,- числа А по всем основаниям совпадают, то число А правильное. Если же существует такое А^, что А^ — правильное, при условии, что 4- - неправильные числа, где i = l,2,...,s-\,s + \,...,n^ то имен но в остатке по модулю р^. Тем самым ошибка будет локализована.

Предположим теперь, что по проекциям А/ не удалось локализовать ошиб ку. Это означает, что ошибка не является одиночной. Тогда рассматриваются проекции по паре модулей, по тройкам модулей и так далее (при условии, что минимальное расстояние кода достаточно велико). Если ошибки удалось локализовать с помошью проекций числа А по t модулям, причем А^^^^ ^^ правильное число, то именно остатки по модулям р^^, р^^у..., р^^ являются ошибочными [77].

Вычисление истинных значений искаженных остатков осуществляется по проекции, локализующей ошибки. Поскольку факт правильности проекций можно было устанавливать любым известным методом обнаружения ошибок, то в общем случае мы имеем лишь представление проекции ^,J2...J, • Тогда правильные остатки or,- по основаниям р^^, р^^,..., р^^ найдем по фор муле (1.2.4.2) M где Bj — ортонормированные векторы в системе из оснований pi, Р2,..., В работе [93] доказано, что j^B^^ (mod P^^l (1.2.4.3) a (1.2.4.4) диапазон СОК, сокращенной на /-ый разряд, т.е.

— где fij'^ - соответствующие ортогональные базисы (ортонормированные векто ры).

Обобщим результат, полученный в [93], т.е. докажем, что (1.2.4.5) (1.2.4.6) а= J PI где p(V2-*/) ^ p^p^ •-.^•Psi-lPsi+l --'Psi-lPsi+l •-•Ps,-lPs,+l '--Pn BJ - соответствующие ортонормированные векторы.

Действительно, в силу определения ортонормированных векторов исход ной системы оснований верно, что (1.2.4.7) ^ = {(mod pj), j = \,n.

Pj Для сокращенной СОК (1.2.4.8) = l(mod p. ), 7 6 {1,2,...,5, -1,5, +1,...,5, -1,5, +1,...,и}.

-^ Pj С учетом (1.2.4.7), (1.2.4.8) и свойств сравнений получим:

Pj откуда в силу взаимной простоты оснований Умножая обе части и модуль последнего сравнения на, имеем Pj _ mj mod ^(, Pj Pj Т.е.

Bj = Bj (mod p Следовательно, в силу свойств сравнений п п S ajBj п n Z ^/^y ^•^ ее J: 1J J:

/ = y=i j*s, p^s2...s,) p{s,s2....^,) откуда •••"t) что и требовалось доказать.

= \,2,...,{n-k)) он Обратим внимание, что проекции г-го норядка ределяются по формулам (1.2.4.9) Z ajBj A, i если же для установления факта наличия ошибок в данном числе Л = (аг,,а2»•••««) было вычислено представление числа А в десятичной ПСС, то при ручном подсчете удобной будет формула Отметим, что быстродействие рассмотренного метода коррекции ошибок, метода проекций, относительно невелико.

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

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

Неправильное число А называют А:-альтернативно корректируемым (или просто А:-альтернативным) числом, если существуют к таких правильных чисел Ai, А2,..., А,^, каждое из которых отличается от А цифрой по одному какому-либо основанию, причем эти основания различны для различных А^ (г = 1,к). Совокупность оснований (pi^, р,-^,..., Pi^), по которым числа Ai, А2,..., A^ отличаются от А, называют альтернативной совокупностью числа А.

С учетом изложенного метода проекций необходимым и достаточным ус ловием вхождения основания р,- в альтернативную совокупность неправиль ного числа А является то, что проекция числа А по модулю /?,- есть правиль ное число. Таким образом, альтернативную совокупность можно сформиро вать, найдя правильные проекции среди всех проекций по одному основа нию. Другим способом построения альтернативной совокупности является метод нулевизации, позволяющий определить таблицу распределения оши бок [5].

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

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

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

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

В соответствии с изложенным представляется возможным определить не сколько способов организации контроля и коррекции ошибок [5]:

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

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

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

Пример. Пусть основаниями кода СОК являются /?i = 4, Р2=5, Рз = ^, Р4=И и Р5=13, причем Р2, Рз, РА И р^ - проверочные модули;

/*^=4, Р^ = 20020. Ортонормированные базисные векторы заданной СОК есть числа 5, =5005, ^2 =16016, 5з=5720, 54=1^380 и 55=16940. Пусть дано число Л = (3,1,3,3,12).

Поскольку Л = |3-5005 + М6016 + 3-5720 + 3-16380 + 12-16940|20020=3114, дан ное число является неправильным.

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

Вычислим проекции первого порядка:

=3114, А, =Щ^^^^ ^2ПА, ^4 = |31 l|,g2o = 311 4, ^5 = |31 l|j54Q = 311 4. Локализовать ошибку не удалось, следовательно, число ошибочных остатков превышает единицу.

Вычислим проекции второго порядка:

=3114, Ли =|311|455 = 3 1 1 4, 4 = 311 4, ~314. Откуда заключаем, что количество ошибок в исходном числе равно 2, причем ошибочными являются остатки по модулям Таким образом, исправленным является число Л'= 3 = (3,3,3,3,3).

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

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

Pi{P2 -Р\)кръ -Р\)'-'{Рп-Р\) Действительно, в силу упорядоченности системы оснований данного кода СОК Р\ "^ Pi ••• Рп') а, благодаря тому, что лишь р^ является информационным модулем, рабочий диапазон есть Рк= Р\ и правильными являются числа Откуда следует, что ошибки (n-l)-ro порядка будет исправлены по макси муму правдоподобия, если все, кроме одной, проекции (n-l)-ro порядка больше Pjt;

последнее же означает, что лишь один из остатков в представле нии числа в данной СОК меньше р^.

У учетом сказанного получим, что первый остаток указанного числа есть любое натуральное число из интервала [0,/i), а /-й остаток — всякое нату ральное число из интервала [pi,Pi), i = 2,n;

количество чисел такого вида в силу правила умножения равно Piip2-PiXP3-Pi)' — 'iPn-Pi)- Теорема дока зана.

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

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

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

1.3.1. Канонические нредставления целых чисел.

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

Решению этой задачи носвящено содержание данного нункта.

Представление целых чисел X в виде слов X = ±{ где X = ±Y,Xir', 0Xir-l, «о = называется однородной позиционной системой счисления с естественным порядком весов и является наиболее предпочтительным и для человека (и = 10), и для вычислительной машины (почти всегда г = 2). Длина слова п определяется, как правило, разумными ограничениями на точность представления. Однако если человек при необходимости может в широких пределах варьировать величину w, то в машине длина слов в определенной степени фиксируется еще на стадии проектирования и воплощенные «в металл» регистры, сумматоры, множительные устройства рассчитаны на работу со словами именно этой длины, что превращает машинную арифме тику в арифметику по некоторому модулю т.

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

М.А. Карцев [46], Рейтвизнер [126] и ряд других исследователей для сокращения количества сложений и вычитаний при выполнении «длинных»



Pages:   || 2 | 3 | 4 |
 





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

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