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

 

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

Кодовым расстоянием кода называется минимальное расстояние Хэмминга между любой парой несовпадающих векторов кода

.

Теорема 5.5.1. Код исправляет любые ошибки кратности и менее в том и только в том случае, если кодовое расстояние удовлетворяет неравенству

. (5.5)

Доказательство:

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

,

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

,

что противоречит условию теоремы. Следовательно, неравенство (5.5) определяет достаточное условие исправление ошибок кратности и менее.

С другой стороны, если , то обязательно возникнет ситуация, при которой произойдет неверное декодирование. Например, если , то существует такой вектор наблюдения , для которого , и, следовательно, наблюдается неопределенность в принятии решения. Таким образом, условие (5.5) является необходимым.

Полезной иллюстрацией приведенного доказательства может служить диаграмма, представленная на рис. 5.3. На ней изображены сферы Хэмминга радиуса c центром , представляющие собой множество точек (векторов), расположенных от на расстоянии Хэмминга или ближе. Если все сферы Хэмминга радиуса , окружающие кодовые вектора , не перекрываются, декодер воспримет любой вектор внутри i –ой сферы, как i –ый кодовый вектор . Это означает, что любая ошибка кратности и менее в кодовом слове будет исправлена. Вместе с тем, при условии исправления любых ошибок кратности избежать перекрытия сфер можно только в том случае, если минимальное расстояние Хэмминга между кодовыми векторами не меньше, чем .

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

.

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