9.4. Дополнение

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

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

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

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

-коды, обнаруживающие пачки ошибок и подобные кодам Файра, были предложены Мандельбаумом [6]. Эти коды имеют порождающие числа А вида

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

1) Длины конфигураций пачек ошибок удовлетворяют неравенству

2) Число является простым и

3) Длина кода где

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

Гото и Фукумура [7] установили необходимые и достаточные условия того, что код исправляет пачки ошибок веса 1 или обнаруживает пачки ошибок веса 2. Они показали, что этим условиям удовлетворяют -коды, исправляющие ошибки веса 1 с порождающими числами вида где - простое число.

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

и

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

Между многоостаточными кодами и -кодами существует тесная связь. Многоостаточному коду, порождаемому целыми числами можно поставить в соответствие AN-код, взяв в качестве порождающего числа последнего . Число кодовых слов В этого AN-кода определяется из равенства При этом по вычетам произвольного числа однозначно может быть определен вычет по модулю А и, наоборот, по вычету могут быть определены однозначно вычеты . В силу этого многоостаточные коды и соответствующие им AN-коды имеют одинаковую корректирующую способность.

Опубликовано несколько работ, посвященных многоостаточным кодам [8, 11], в которых затронутые выше вопросы рассмотрены более детально.

На большое сходство -кодов и циклических алгебраических кодов уже указывалось в конце разд. 8.5. Однако если рассматривать циклические AN-коды, то это сходство оказывается еще более глубоким. Этот вопрос подробно рассматривается в работе Месси и Гарсиа [8]. В последние годы было проведено несколько исследований, посвященных поиску циклических AN-кодов, соответствующих некоторым хорошим циклическим алгебраическим кодам и исследованию их свойств.

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

Наиболее глубоким исследованием, посвященным применению -кодов в реальных системах, по-видимому, является исследование, проведенное Авидзинисом и др. [9] в рамках проекта Лаборатории реактивных двигателей, имевшего своей целью создание сверхнадежной вычислительной машины для космических кораблей. Авидзинис и другие исследовали эффективность -кодов не только при исправлении ошибок, возникающих при обычных арифметических операциях, но и при сдвигах чисел, вычислении дополнительных чисел и др. Кроме того, были проведены экспериментальные исследования процессора с длиной слова 4 байта (32 бита), использовавшего AN-код с который может быть реализован с помощью относительно простых и недорогих устройств. Результаты

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

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