Коды Хемминга

Начнем с нескольких определений и конструкций общего характера.

Если функция кодирования блочного кода E:{0,1}ⁿ→{0,1}^m линейна, то код называется линейным. В дальнейшем мы рассматриваем только линейные коды. Назовем проверочным такое линейное отображение S:{0,1}^m→{0,1}^k, что S(β)=0 тогда и только тогда, когда β является кодовым словом. Для произвольного β∈{0,1}^m вектор S(β) называется синдромом. Нулевой синдром имеют кодовые слова, и только они.

Предположим, что в зашумленном канале передаваемое кодовое слово E(α) исказилось, к нему добавился вектор ошибок δ, так что на выходе принято слово β=δ⊕E(α). Тогда

S(β)=S(δ⊕E(α))=S(δ)⊕S(E(α))=S(δ).

Для того чтобы правильно декодировать передаваемое сообщение, нужно уметь определять вектор ошибок по его синдрому. Если вектор ошибок определен, то исправить их несложно: E(α)=δ⊕β. Ограничившись случаем одиночных ошибок, можно привести сравнительно несложное построение кода, исправляющего ошибки.

Вектор одиночной ошибки имеет всего одну ненулевую координату, то есть является одним из векторов канонического базиса пространства {0,1}^m. Линейный код позволяет исправлять все одиночные ошибки тогда и только тогда, когда синдромы всех векторов из канонического базиса пространства {0,1}^m отличны от нуля и друг от друга. Поскольку пространство {0,1}^k содержит всего 2^k−1 ненулевых векторов, используя проверочное отображение S:{0,1}^m→{0,1}^k, можно исправлять одиночные ошибки лишь в том случае, когда длины кодовых слов ограничены числом 2^k−1, то есть m≤2^k−1. Оказывается, что можно построить коды с исправлением ошибок, в которых m=2^k−1. В таких кодах их «исправляющие» возможности используются с максимальной эффективностью. К их числу относятся рассматриваемые ниже коды Хемминга.

Перейдем к описанию кода Хемминга. Пусть m=2^k−1. Среди m позиций кодового слова k позиций являются контрольными, а n = 2^k−k–1 – информационными. Матрица H (размерности k×(2^k−1)), задающая проверочное отображение, содержит в качестве столбцов все ненулевые векторы пространства {0,1}^k. Порядок столбцов не важен, но технически удобнее считать, что в каждом столбце записан его номер в двоичном формате. Строки матрицы H определяют коэффициенты системы из k однородных линейных уравнений c 2^k−1 неизвестными. Множество кодовых слов совпадает с множеством решений этой системы. Выражая последние k неизвестных через первые 2^k−k–1, мы получаем уравнения для вычисления контрольных битов. Вектор с нулевым синдромом является кодовым и его декодирование сводится просто к отбрасыванию контрольных битов. Если синдром отличен от нуля, он представляет собой двоичную запись номера позиции, в которой произошла ошибка. В этом случае при декодировании ошибка исправляется. Доля информационных позиций в коде Хемминга составляет

1211212−−=−−−kkkkk

и стремится к 1 с ростом k.

Пример.Рассмотрим случай k=3, m=7, n=4. Проверочное отображение S задается следующей матрицей:

=101010111001101111000H.

Столбцы матрицы представляют собой образы векторов канонического базиса пространства {0,1}⁷ относительно S. Для произвольного вектора β=(β₁,β₂,β₃,β₄,β₅,β₆,β₇) синдром S(β)=(σ₁,σ₂,σ₃) определяется уравнениями

σ₁=β₄⊕β₅⊕β₆⊕β₇;

σ₂=β₂⊕β₃⊕β₆⊕β₇;

σ₃=β₁⊕β₃⊕β₅⊕β₇.

Кодовое слово S(α)=(α₁,α₂,α₃,α₄,α₅,α₆,α₇) должно удовлетворять системе уравнений

α₄⊕α₅⊕α₆⊕α₇=0;

α₂⊕α₃⊕α₆⊕α₇=0;

α₁⊕α₃⊕α₅⊕α₇=0.

Решив эту систему относительно α₅, α₆, α₇, можно найти уравнения, задающие контрольные биты. Сложив первые два уравнения, получаем

α₂⊕α₃⊕α₄⊕α₅=0,

откуда

α₅=α₂⊕α₃⊕α₄.

Подставив выражение для α₅ в третье уравнение системы, получаем

α₇=α₁⊕α₂⊕α₄.

Теперь подставляем выражение для α₇ во второе уравнение системы и находим

α₆=α₁⊕α₃⊕α₄.􀀀