Десятичные коды с автоматическим исправлением однократных ошибок

В качестве примера возьмем двоичный код Хэмминга, модифицированный одним из авторов книги на позиционную систему счисления с произвольным основанием [4, 6].

В исходное m-разрядное кодовое слово вводится дополнительно k контрольных разрядов так, что их номера j равны целой степени числа 2: j = 1, 2, 4, 8, 16, …2k – 1.

Обозначим через i номера разрядов в образованном кодовом слове, тогда номера контрольных разрядов будут i = j. Значение символа А_j в j-м контрольном разряде выбирается из условия кратности q = 10 контрольной суммы E_j, соответствующей этому разряду:

где n = m + k,

(μ_i = 0 при четном значении ближайшего большего целого частного i/j, и μ_i = 1 при нечетном значении ближайшего большего целого частного i/j).

примечаНИЕ

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

Рассмотрим пример помехозащищенного кодирования. Запишем разрядную сетку (курсив) избыточного слова:

Подчеркнутые разряды считаем проверочными, а в остальные разряды записывается исходное слово — 90 723 092 001 для кодирования. Контрольная цифра в j-м контрольном разряде (А₁, А₂, А₄, А₈) рассчитывается так:

E₁ = A₁ + A₃ + A₅ + А₇ + А₉ + А₁₁ +А₁₃ + А₁₅ = 0 mod 10.

Для нашего числа:

1 + 9 + 0 + 2 + 3 + 9 + 0 + 1 = 0 mod 10, А₁ = 6;

Е₂ = A₂ + A₃ + A₆ + А₇ + А₁₀ + А₁₁ + А₁₄ + А₁₅ = 0 mod 10, А₂ = 2;

Е₄ = A₄ + A₅ + A₆ + А₇ + А₁₂ + А₁₃ + А₁₄ + А₁₅ = 0 mod 10, А₄ = 8;

Е₈ = A₈ + A₉ + A₁₀ + А₁₁ + А₁₂ + А₁₃ + А₁₄ + А₁₅ = 0 mod 10, А₈ = 5.

Сформированное таким образом разрешенное избыточное кодовое слово позволяет не только обнаружить, но и автоматически исправить любую однократную ошибку. Такая ошибка переведет кодовое слово в категорию запрещенных потому, что хотя бы одна частная контрольная сумма E_i по модулю 10 будет отлична от 0. Это определяет правило обнаружения ошибки: если проверка кодового слова после его информационного преобразования, производимая путем подсчета частных сумм Е₁, Е₂, Е₄, Е₈, ... , E_s даст хотя бы одну Е_i, не равную нулю по модулю 10, значит, при преобразовании была допущена ошибка.

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

1. Все частные суммы Е_i=0. Это означает отсутствие однократных ошибок при выполнении преобразования (и с большой вероятностью — отсутствие ошибок вообще).

2. Хотя бы одна из сумм Е_i не равна нулю, но все не равные нулю частные суммы Е_i равны между собой (по модулю 10). Можем считать с большой вероятностью, что произошла однократная ошибка при преобразовании; ее адрес — номер искаженного разряда в виде двоичного кода можем определить из выражения:

i_ош = E_s E_s/2…E₄ E₂ E₁,

где E_i = 0, если E_i = 0, и E = 1 — в противном случае (мнемоническое правило: адрес ошибки равен сумме индексов частных контрольных сумм, не равных нулю).

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

Допустим, мы имеем E_i = E_r ≠ 0. Следовательно, при преобразовании произошло либо увеличение цифры по найденному адресу i_ош, на E_r единиц, либо ее уменьшение на 10 – E_r единиц. В любом случае, чтобы исправить эту ошибку, можно вычислить правильное значение цифры по формуле

A_{iош прав} = (А_iош – Е_r) mod 10.

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

Теперь рассмотрим пример декодирования. Допустим, в разрешенном кодовом слове

допущена ошибка в 12-м разряде: вместо 2 появилась ошибочная цифра 0, то есть получили кодовое слово:

Это слово относится к категории запрещенных, поскольку по модулю 10 (учитывается только разряд единиц, а десятки, сотни и т. д. отбрасываются) Е₁ = 0, Е₂ = 0, Е₄ = 8, Е₈ = 8. Все не равные нулю частные контрольные суммы равны между собой и равны E_r = 8, следовательно, произошла однократная ошибка, и ее можно исправить. Адрес ошибки — двоичный код номера искаженного разряда: i_ош = 1100, то есть ошибка имела место в 12 разряде (сумма индексов частных ненулевых контрольных сумм равна: 8 + 4 = 12).

Исправляем ее:

i_{12 прав} = i_{12 ош} – E_r = (0 – 8) mod 10 = 2

ПРИМЕЧАНИЕ

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

Действительно, верное значение цифры в 12-м разряде — 2. Ошибка исправлена.

Данный код позволяет обнаружить подавляющее число ошибок кратности 2 и выше (без их исправления). Для более высокой эффективности обнаружения ошибок к рассматриваемому кодовому слову можно добавить еще один проверочный разряд (нулевой), которым контролировать по модулю 10 сумму всех цифр избыточного кодового слова (включая контрольные разряды). Более полное исследование эффективности рассматриваемых кодов приведено в работах [6, 8]. Широко известные двоичные коды Хэмминга с автоматическим исправлением ошибок являются частным случаем рассмотренных кодов при модуле q = 2.