Кодовое расстояние

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

Кодовым расстоянием d называется минимальное количество разрядов в которых одна кодовая комбинация отличается от другой кодовой комбинации.

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

Иногда кодовое расстояние называется хемминговым расстоянием (по имени Ричарда Хемминга, основателя помехоустойчивых кодов).

У простого двоичного кода d =1. Каким должно быть кодовое расстояние у кодов, обнаруживающих ошибки, и у кодов, исправляющих ошибки?

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

Пусть имеется n -разрядный двоичный код. Выберем 2 кодовые комбинации и , которые будем считать разрешенными (рисунок 7.1). Каждой разрешенной кодовой комбинации соответствует свое подмножество запрещенных кодовых комбинаций с одиночными ошибками. Число их равно C _n¹, а кодовое расстояние относительно исходной кодовой комбинации d =1. Графически это представляется окружностью с радиусом d =1.

Рисунок 7.1 – Определение кодового расстояния

Аналогично, подмножество запрещенных кодовых комбинаций с двойной ошибкой имеет кодовое расстояние относительно исходной d =2, а число их равно C _n². И так далее до ошибок кратности t включительно.

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

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

Для исправления ошибки кратности s кодовое расстояние должно быть:

.

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

Помехоустойчивые коды делятся на два больших класса:

1. Блоковые коды;

2. Непрерывные коды.

Для блоковых кодов к каждой исходной комбинации добавляется блок избыточных символов и получается новая комбинация (рисунок 7.2).

Рисунок 7.2 – Построение блокового кода

Различают разделимые и неразделимые блоковые коды. В разделимых блоковых кодах k символов являются информативными, а r - проверочными.

Такие коды обозначают как (n, k) – коды.

Для неразделимых кодов разделить символы на информативные и проверочные невозможно (см. далее корреляционный код).

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