8.7. Синдромы и методы декодирования AN-кодов

Предположим, что кодовое число AN в результате арифметической ошибки переходит в число Минимальный вычет по модулю числа I:

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

Таблица 8.10 (см. скан) Примеры -кодов с минимальным расстоянием 5

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

Теорема 8.10. Пусть некоторое множество ошибок. Для того чтобы AN-код исправлял все ошибки из множества необходимо и достаточно, чтобы любые две ошибки такие, что и

имели различные синдромы.

Доказательство. Пусть две различные ошибки. Если допустить, что эти ошибки нельзя исправить, то найдутся такие кодовые числа что

Так как то Однако

Следовательно, код исправляет все ошибки из тогда и только тогда, когда для любых двух различных ошибок удовлетворяющих неравенству (8.83)).

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

теоремы 8.10, это не так; последнее условие является достаточным, но не необходимым.

Рассмотрим -код с из примера 8.7. Пусть множество, состоящее из ошибок веса 1, таких, что и числа 0. Этот AN-код имеет минимальное расстояние 3 и, следовательно, может исправлять все ошибки веса 1. Ошибки из множества удовлетворяют условиям теоремы 8.10, но не обязательно все они имеют различные синдромы. Например, ошибки входят в но Однако поскольку то условия теоремы 8.10 в действительности и не требуют, чтобы ошибки имели различные синдромы. Тем не менее обе эти ошибки рассматриваемым -кодом исправляются. Это происходит потому, что ни для каких двух кодовых чисел и из трех кодовых чисел 0, 11 и 22 не выполняется равенство Рассмотрим, например, уравнение В этом случае следовательно, возникла одна из двух ошибок 25 или —1. Однако число не является кодовым числом рассматриваемого кода, и, значит, ошибка —1 возникнуть не могла. Допустим, что произошла ошибка 25. Тогда В результате приходим к выводу, что ошибка равна 25, а правильное кодовое число равно 11.

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

Утверждение -код исправляет все ошибки из заданного множества тогда и только тогда, когда при любом фиксированном целом все ошибки из удовлетворяющие условию

имеют различные синдромы.

Это утверждение непосредственно следует из теоремы 8.10, если заметить, что когда и удовлетворяют неравенству (8.84) при одном и том же то они удовлетворяют также и (8.83).

Последнее утверждение оказывается полезным, когда величину ошибок устанавливается ограничение. Так как число лежит в области где длина кода, задаваемая равенством (8.32), то

Однако поскольку то это неравенство можно заменить на следующее неравенство, не связанное с

Ошибки удовлетворяющие (8.85), называются реально возможными ошибками. Для рассмотренного выше -кода с реально возможными ошибками являются ошибки, удовлетворяющие неравенству

Как видно из таблицы, приведенной в примере 8.7, целые числа веса 0 и 1, лежащие в этой области (это множество обозначается через имеют различные синдромы. Действительно, для AN-кодов, даваемых теоремой 8.5 из разд. 8.5, реально возможные ошибки веса 0 и 1 имеют различные синдромы, и, более того, эти синдромы «пробегают» все вычеты по модулю

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

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

Как можно видеть из этого краткого пояснения, желательно, чтобы соответствие между реально возможными исправляемыми ошибками и соответствующими им синдромами было взаимно однозначным. Такие коды известны [11], но даже если это условие не выполняется, можно использовать другие описанные ниже методы декодирования. Кроме того, в случае, если длина кода такова, что полезным оказывается алгоритм декодирования, описанный в разд. 9.3.