10. Необычное обычное расстояние

Известно, что расстояние между точками в пространстве определяется как длина отрезка прямой, соединяющей эти точки. Оно служит мерой близости точек - чем меньше расстояние, тем ближе друг к другу расположены точки. Если обозначать расстояние между точками а и b через ρ(а, b), то для любых точек а, b и с имеем:

1) ρ(а, b) ≥ 0;

2) ρ(а, b) = 0 означает, что а = b;

3) ρ(а, b) = ρ(b, а)

4) ρ(а, b) + ρ(b, с) ≥ ρ(а, с).

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

Иногда удобно бывает определить меру близости или расстояние для элементов того или иного множества, даже если эти элементы и не являются точками в обычном смысле. При этом считается, что расстояние между элементами множества определено, если любым двум элементам а и b сопоставлено действительное число ρ(а, b) и для любых элементов a, b и с данного множества выполняются условия 1) - 4).

Вернемся теперь к нашей основной теме. Мы уже знаем, что код тем лучше приспособлен к исправлению ошибок, чем больше отличаются друг от друга кодовые слова. Эту мысль можно будет выразить точно, если ввести расстояние на множестве n-буквенных слов.

Расстоянием ρ(х, у) между двумя словами х и у назовем число несовпадающих позиций этих слов. Например, расстояние между словами x = 01101 и y = 00111 равно 2.

Определенное так расстояние называют расстоянием Хемминга. Не составляет большого труда проверить, что все свойства 1) - 4) расстояния в данном случае выполнены. Вопрос лишь в том, в какой мере это понятие поможет оценить способности кода исправлять и обнаруживать ошибки. Чтобы ответить на этот вопрос, введем для произвольного кода понятие кодового расстояния.

Кодовое расстояние d(V) определим как минимальное расстояние между различными кодовыми словами из V:

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

Код способен исправлять любые комбинации из t (и меньшего числа) ошибок тогда и только тогда, когда его кодовое расстояние больше 2t.

В самом деле, если d(V) > 2t, то для любых кодовых слов х, у имеем ρ(х, y) ≥ 2t + 1. Пусть при передаче некоторого слова х произошло r ≤ t ошибок, и в результате было принято слово z. Тогда ρ(x, z) = r ≤ t, и в то же время расстояние ρ(z, у) до любого другого кодового слова у больше t. Последнее вытекает из неравенства треугольника:

Значит, для восстановления посланного слова (декодирования) необходимо найти кодовое слово х, "ближайшее" к принятому слову z в смысле расстояния Хемминга. Подчеркнем, что это правило декодирования приводит к правильному результату, если число ошибок в передаваемом слове действительно не превосходило t.

Если же условие d(V) > 2t нарушается, то найдутся такие кодовые слова х и у, расстояние между которыми ρ(x, y) ≤ 2t. Тогда может найтись такая комбинация из t ошибок в одном из слов х, что принятое слово z будет находиться от другого слова у не дальше, чем от х. Поэтому нельзя будет определить, какое из слов - х или у - было на самом деле передано