10. НЕОБЫЧНОЕ ОБЫЧНОЕ РАССТОЯНИЕ

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

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

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

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

 

 

 

 

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

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

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

 

 

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

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

В самом деле, если й(У)>21, то для любых кодовых слов х, у имеем р(х, у)^21-\-\. Пусть при передаче некоторого слова х произошло г^/ ошибок, и в результате было приня­то слово г. Тогда р (х, г)-=г^1, и в то же время расстояние р (г, у) до любого другого кодового слова у больше I. Послед­нее вытекает из неравенства треугольника:

 

 

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

Если же условие й(У)>21 нарушается, то найдутся та­кие кодовые слова х и у, расстояние между которыми р (х, у)^21. Тогда может найтись такая комбинация из I ошибок в одном из слов х, что принятое слово г будет на­ходиться от другого слова у не дальше, чем от х. Поэтому нельзя будет определить, какое из слов — х или у — было на самом деле передано

Задачи и дополнении

1. Имеется 8 двоичных слов длины 3. Их можно изоб­разить в пространственной системе координат как вершины куба со стороной 1. Каков в этом случае «геометрический смысл» расстояния Хемминга между словами?

2. Доказать, что для обнаружения 5 (или меньшего числа) ошибок необходимо и достаточно, чтобы кодовое расстояние удовлетворяло неравенству

 

3. Доказать, что для исправления I (н меньшего числа) ошибок и вместе с этим обнаружения 5 (и меньшего числа) ошибок (&>/) необ­ходимо и достаточно, чтобы кодовое расстояние удовлетворяло неравенству

 

4. Показать, что кодовое расстояние для кода с общей проверкой на четность равно двум, а для кода Хемминга — трем. Чему оно равно для кода с повторением, чему — для расширенного кода Хемминга?