Корректирующая способность кода

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

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

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

Для расстояния Хэмминга выполняются следующие три аксиомы:

симметрии - ;

неотрицательности - , причем если , то ;

неравенства треугольника - .

Наряду с расстоянием Хэмминга широко используется такая характеристика, как вес Хэмминга. Весом Хэмминга вектора называется число его ненулевых компонент. Очевидно, что и , где под суммированием векторов понимается покомпонентное сложение.

Пример 1.4.1.

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

Теорема 1.4.1.

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

. (*)

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

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

,

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

,

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

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