1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность

Рассмотрим двоичный код С, исправляющий ошибки. Если не все из 2^п возможных двоичных векторов длины п будут передаваться по каналу связи, то этот код может обладать свойством помехоустойчивости. В действительности, код С является подмножеством w-мерного двоичного векторного пространства V₂ = {0, 1}ⁿ таким, что элементы этого подмножества максимально удалены друг от друга.

В двоичном пространстве V₂ расстояние определяется как число позиций, на которых два вектора не совпадают. Пусть x₁=(x_1,0, x_1,1, …,x_1,n-1) и х₂=(х_2,0 , х_2,1,..., x_2,n-1) два вектора в V₂. Тогда Хеммингово расстояние между векторами х₁ и х₂, обозначаемое как d_H(x₁, x₂), равно

(1.3)

где через |А| обозначено число элементов в множестве А.

Для заданного кода С минимальное Хеммингово расстояние, d_min, определяется как минимум Хеммингова расстояния по всем возможным парам различных кодовых слов,

(1.4)

Повсюду в пособии обозначение (n, k, d_min) используется для параметров блокового кода длины n, который используется для кодирования сообщений длины k, и имеет минимальное Хеммингово расстояние d_min. Предполагается, что число кодовых слов этого кода равно |С|=2^k.

Пример 1. Простейшим примером является код-повторение длины 3. Каждый информационный бит повторяется три раза. Таким образом, сообщение «0» кодируется вектором (000), а сообщение «1», вектором (111). Так как два вектора различаются в трех позициях, Хеммингово расстояние между ними равно 3. На Рисунке 3 показано графическое представление этого кода. Трехмерное двоичное векторное пространство соответствует 2³=8 вершинам трехмерного единичного куба. Хеммингово расстояние между кодовыми словами (000) и (111) равно числу вершин, через которые проходит соединяющий их путь. Это эквивалентно числу координат, которые необходимо изменить, чтобы преобразовать (000) в (111) и наоборот. Таким образом, d_H= ((000),(111)) = 3. Так как в этом коде только два кодовых слова, то d_min = 3.

Двоичное векторное пространство V₂ обычно называют Хемминговым пространством. Пусть v кодовое слово кода С. Хемминговой сферой S_t(v) радиуса t с центром в точке v является

Рис. 3. (3,1,3) код-повторение в трехмерном векторном пространстве.

Рис. 4. Хемминговы сферы радиуса t=1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.

множество векторов (точек) в V₂ на расстоянии меньше или равном t от центра v,

(1.5)

Заметим, что число слов (число векторов) в S_t(v) равно

(1.6)

Пример 2. На Рисунке 4 показаны Хемминговы сферы радиуса t = 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.

Заметим, что Хемминговы сферы для этого кода не пересекаются, т.е. в пространстве V₂ нет векторов (или вершин в единичном трехмерном кубе), принадлежащих одновременно и S₁(000), и S₁(111). В результате, если изменить любую одну позицию кодового слова v, то получится вектор, который, тем не менее, останется внутри Хемминговой сферы с центром в v. Эта идея является принципиальной для понимания и определения корректирующей способности кода С.

Корректирующей способностью (error correcting capability) t кода С называют наибольший радиус Хемминговой сферы S_t(v) для всех кодовых слов v C такой, что для любых различных пар v_i, v_j С соответствующие им Хемминговы сферы не пересекаются, т.е.

(1.7)

Это соответствует более распространенному определению

(1.8)

где [x] обозначена целая часть x, т.е. целое число меньше или равное x.

Заметим, что для определения минимального кодового расстояния произвольного блокового кода С в соответствии с (1.4), необходимо вычислить все 2^k(2^k — 1) расстояний между различными парами кодовых слов. Это практически невозможно даже для сравнительно коротких кодов, например, с к = 50. Одним из важных преимуществ линейных блоковых кодов является то, что для вычисления d_min достаточно знать только Хемминговы веса 2^к — 1 ненулевых кодовых слов.