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

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

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

Кодовая матрица расстояний выглядит следующим образом.

(см. скан)

Как видно из матрицы расстояний, в качестве разрешенных комбинаций в этом случае выбираем следующие! либо

Для обнаружения двукратных ошибок кодовое

расстояние При этом в качестве разрешенных комбинаций можно выбрать либо либо и либо Очевидна справедливость условия

Поэтому в принципе невозможно обнаружить ошибки кратностью, равной

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

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

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

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

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

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

Для исправления всех ошибок кратности до .и одновременного обнаружения всех ошибок кратности не более кодовое расстояние должно удовлетворять условию [29]

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

Таблица 14 (см. скан)

Идея построения кода с данной корректирующей способностью, следовательно, заключается во внесении в него такой избыточности, которая обеспечила бы расстояние между любыми кодовыми комбинациями данного кода не менее К сожалению, вопрос об определении минимального количества избыточных символов не решен. Существует лишь ряд верхних и нижних оценок (границ) [57, 61, 78, 81, 83, 90, 91, 92, 96, 107]

1) граница Хэмминга

2) граница Плоткина

3) граница Элайеса

где

4) граница Варшамова—Гильберта

Экспериментально установлено, что наиболее близкие значения дает граница Варшамова — Гильберта [90]. Все приведенные границы позволяют сделать вывод, что при выполнении одного из условий (3.7) — (3.10) имеется возможность построить код с данными параметрами.

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

В табл. 15 приведены значения проверочных символов рассчитанные для двоичного алфавита при

(см. скан)

(см. скан)

(см. скан)