∑ αi + βi, где знак + обозначает сумму по модулю 2, а знак ∑
i=1
обозначает обычное арифметическое суммирование.
Если αi = βi, то αi + βi =0 , а еслиαi ≠ βi, то αi + βi =1.
Поэтому, расстояние между кодовыми словами – это число разрядов в обоих словах, в которых биты не равны, то есть число несовпадающих разрядов. Например, рассмотрим два кодовых слова длины 7: 0110010 и 1110011. В этих словах не совпадают биты в первом и в последнем разрядах, а остальные разряды совпадают. Так как всего два несовпадения в этих словах, значит расстояние между ними равно 2.
Расстояние между двоичными кодовыми словами часто называют расстоянием Хемминга, в честь Ричарда Хемминга, использовавшего это понятие при исследовании кодов с исправлением ошибок.
Обозначим расстояние между кодовыми словами A=α1α2…αn и B=β1β2…βn
через ρ(A, B). Двоичные коды длины nс заданным расстоянием ρявляется метрическим пространством, то есть удовлетворяет трем аксиомам метрики (как и обычное геометрическое пространство):
1) ρ(A, B) =0тогда и только тогда, когда A = B(аксиома тождества);
2) ρ(A, B) + ρ(B, C) ≥ ρ(A, C)(аксиома треугольника);
3) ρ(A, B) = ρ(B, A)(аксиома симметрии).
Метрику на множестве двоичных кодовых слов называют метрикой Хемминга.
Метрику на двоичных кодах длины nможно геометрически интерпретировать на
n-мерном кубе.
Например, в коде порядка 2 кодовые слова: 00, 01, 10, 11, можно представить в виде координат вершин единичного квадрата (2-мерный куб), как показано на следующем рисунке:
Здесь пары кодовых слов, соответствующие вершинам, соединенным ребром квадрата, находятся на расстоянии 1 , а остальные пары - на расстоянии 2. Так между 00 и 11 , а также между 01 и 10 расстояние равно 2 (от одной вершины к другой нужно пройти по двум ребрам).
Аналогично, все кодовые слова длины 3 можно геометрически представить на 3-мерном единичном кубе:
Здесь уже можно увидеть пары кодов, находящихся на расстоянии 3. Например, между кодами 100 и 011 расстояние равно 3. Это следует не только из определения расстояния, но и видно по рисунку (от одной вершины к другой кратчайший путь содержит 3 ребра).
А как быть с кодами большей длины? Например, для кодов длины 4 нужно представить себе 4-мерный куб, то есть рассматривать его в 4-мерном пространстве. Но на предыдущем рисунке мы спроектировали 3-мерный куб на плоскость, то есть в 2-мерное пространство, Почему бы не попробовать спроектировать 4-мерный куб на плоскость? Просто надо поступить по аналогии.
На следующем рисунке представлены кодовые слова длины 4 на вершинах 4-мерного куба:
Вершины 4-мерного куба можно представить более симметрично так, чтобы все ребра имели одинаковую длину:
А на следующем рисунке вершины расположены по ярусам, где на каждом ярусе вершины находятся на одинаковом расстоянии от нулевой вершины (0000):
Вернемся к кодам с обнаружением и исправлением ошибок.
Обратим внимание на следующий факт:
Если при передаче двоичного кодового слова длины n произошла одиночная ошибка, то передаваемое слово перешло в слово на расстоянии 1;на n–мерном кубе это соответствует переходу в соседнюю вершину по одному ребру. Если же в слове произошла двойная ошибка, то измененное слова оказалось на расстоянии 2, что соответствует переходу в кубе в другую вершину по двум ребрам.
Предположим, мы выбрали для передачи сообщение только такие слова, что никакая пара из них не находится на расстоянии 1. Тогда код из таких слов будет кодом с обнаружением одной ошибки. Действительно, если при передаче одного из слов этого кода произошла ошибка в одном разряде, то оно перешло в слово на расстоянии 1, но полученное слово не принадлежит нашему коду, следовательно, оно ошибочно.
Назовем шириной кода минимальное расстояние между его кодовыми словами. Из сказанного выше следует, что если ширина кода равна 2, то он является кодом с обнаружением одной ошибки.
Найдем в 3-мерном кубе вершины, находящиеся друг от друга на расстоянии 2. Такими вершинами будут, например, вершины с координатами: 100, 010, 001, 111. Их координаты образуют код ширины 2. Значит, он является кодом с обнаружением одной ошибки. Действительно, измените любой бит в любом из его кодовых слов и вы получите слово, не принадлежащее коду. Но если произошли две ошибки (изменилось 2 бита), то обнаружить это уже не удается. Более того, единичную ошибку, можно только обнаружить, но не исправить. Например, при передаче появилось слово 101. Мы видим, что это ошибочное слово. Но оно могло произойти при изменении бита у любого из следующих кодовых слов: 100, 001, 111, и мы не можем определить какого. Значит, наш код не является кодом с исправлением ошибки.
Рассмотрим теперь код, состоящий всего из двух кодовых слов: 010 и 101. Эти слова находятся на расстоянии 3 (это следует из определения расстояния и видно по изображению 3-мерного куба). Следовательно, этот код имеет ширину 3. Если мы будем передавать сообщения только этими двумя словами и при передаче в одном из слов произойдет единичная ошибка, то мы сможем не только обнаружить ошибку, но и понять, где изменился бит, и исправить его. Пусть, например, мы получили слово 110. Это слово находится на расстоянии 1 от слова 010 и на расстоянии 2 от слова 101. Значит, при одиночной ошибке полученное слово не может произойти от слова 101, следовательно, было передано слово 010.
Ясно, что и в общем случае, независимо от порядка кода (длины кодовых слов), если код имеет ширину 3, то он является кодом с исправлением одной ошибки. Это утверждение иллюстрируется следующим рисунком:
Если же код имеет ширину 4, то уже можно не только исправлять одиночную ошибку, но и обнаруживать двойную ошибку, что иллюстрируется следующим рисунком:
Следовательно, код ширины 4 является кодом с исправлением одной ошибки и с обнаружением двух ошибок.
Задача 11. Пусть двоичный код имеет ширину K. Сколько можно обнаружить ошибок в таком коде и сколько исправить?
Задача 12. Построить двоичный код порядка 4, ширины 3, с максимальным числом кодовых слов.
