Кодирование с целью повышения верности передачи

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

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

Пусть для передачи сообщений используется равномерный двоичный код с длиной кодового слова (кодовых комбинаций) k бит. Тогда общее число кодовых слов равно N₀=2 ^k.

Предположим, что для передачи сообщений используются все возможные кодовые слова N = N ₀. Здесь N – число кодовых слов, используемых для передачи сообщений. Такой код называется простым или примитивным.

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

Увеличим длину кодовых слов до значения n. Тогда общее число кодовых слов N₀=2 ⁿ будет больше числа слов, используемых для передачи сообщений N =2 ^k.

N ₀ > N

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

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

Рассмотрим несколько примеров.

1. Для передачи сообщений используется простой код.

Кодовые слова отличаются друг от друга в одном либо двух символах. Число символов, в которых одно слово отличается от другого, называется расстоянием Хэмминга (d). А	00
В	01
C	10
D	11

Наименьшее расстояние Хэмминга для данного кода называется кодовым расстоянием d_min.

Для данного кода расстояние Хэмминга d=1 или 2, а d_min=1.

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

2. Для передачи того же набора сообщений используется код с длиной кодового слова n=3:

В данном случае N0=8, N=4. Для данного кода кодовое расстояние d=dmin=2. Любая одиночная ошибка переводит разрешенное кодовое слово в запрещенное, что позволяет обнаружить наличие ошибок. A	000
B	011
C	101
D	110

Действие ошибок большего веса (большей кратности) на данный код выражается в следующем:

· Код не обнаруживает двойные ошибки, любая двойная ошибка переводит одно разрешенное кодовое слово в другое разрешенное слово.

· Код обнаруживает тройную ошибку e=(111), так как она всегда приводит к появлению запрещенного слова.

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

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

· Если кодовые слова отличаются друг от друга не менее чем на  символов, то все ошибки веса  будут обнаружены.

· Ошибки веса равного или больше d_min обнаруживаются частично, то есть одни ошибки обнаруживаются, а другие – нет.

 

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

3. Построим код, который может исправить одиночную ошибку t =1. Чтобы код мог исправлять одиночные ошибки, то есть определять, какое кодовое слово было передано в действительности, разрешенные слова должны различаться, по крайней мере, в трех символах .

A	00000
B	01101
C	10110
D	11011

 

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

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

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

· Если код имеет кодовое расстояние , и используется декодирование с исправлением ошибок по ближайшему разрешенному слову, то все ошибки веса t < d_min /2 исправляются.

· Ошибки большего веса могут исправляться частично.

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