double arrow

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


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

,(1.7)

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

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

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

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

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




. (1.9)

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

. (1.10)

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

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

, (1.11)

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

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

(1.12)

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

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

, (1.13)

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

= . (1.14)

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

= . (1.15)

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

. (1.16)

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

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

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







Сейчас читают про: