Кодовое расстояние, избыточность кода

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

,(1.7)

где, - координаты кодовых слов, в -мерном неевклидовом пространстве L_n.

Если код является двоичным, под расстоянием между парой кодовых слов понимается количество символов, в которых они отличаются между собой. Оно определяется сложением двух этих слов по модулю 2 и равно числу единиц в этой сумме. Например:

Знак означает сумму по модулю 2 (сложение по модулю два выполняется по правилу:,,,).

Напомним, что геометрической моделью -значного двоичного кода является -мерный куб с ребром, равным единице, каждая вершина которого представляет одно из возможных кодовых слов. Расстояние между словами d_ij равно числу ребер куба, отделяющих одну вершину от другой. Наименьшее расстояние между любой парой разрешенных слов данного кода называется кодовым расстояниемd = min d_ij. (1.8)

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

. (1.9)

Для исправления ошибок кратности t_ис требуется кодовое расстояние

. (1.10)

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

Для исправления стираний кратности t_ст требуется кодовое расстояние

, (1.11)

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

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

(1.12)

где - число избыточных кодовых символов в слове (+ =).

Для каналов с независимыми ошибками вероятность приёма кодового слова с ошибками определяется очевидным выражением вида

, (1.13)

а вероятность обнаружения ошибки в принятом кодовом слове при декодировании равна

=. (1.14)

Тогда вероятность необнаружения ошибки при декодировании соответственно равна = -, то есть

=. (1.15)

Тогда коэффициент обнаружения можно определить следующим образом

. (1.16)

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

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

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