Код Хэмминга    

Код Хэмминга, являющийся групповым (n,k) кодом, с минимальным расстоянием d=3  позволяет обнаруживать и исправлять однократные ошибки. Для построения кода Хэмминга используется матрица H.    ,   где A_k- транспонированная подматрица, E_n-k - единичная подматрица порядка n-k.

Если Х - исходная последовательность, то произведение Х·Н=0. Пусть E- вектор ошибок. Тогда  (Х+Е)·Н = Х·Н+Е·Н = 0+Е·Н=E·H - синдром или корректор, который позволяет обнаружить и исправить ошибки. Контрольные символы    e₁ ,e₂ ,...,e_r  образуются из информационных символов, путем линейной комбинации    ,  где  а_j={0,1} - коэффициенты, взятые из подматрицы A матрицы H.     

Рассмотрим Построение кода Хэмминга для k=4 символам. Число контрольных символов r=n-k можно определить по неравенству Хэмминга  для однократной ошибки. Но так, как нам известно, только исходное число символов k, то проще вычислить по эмпирической формуле  

                                     ,                                 (5.2)

где [.] - означает округление до большего ближайшего целого значения. Вычислим для k=4   . Получим код (n,k)=(7,4);      n=7; k=4; r=n-k=3; d=3.  Построим матрицу H.

Контрольные символы e_j  определим по формуле . Например, .  Для простоты оставляем только слагаемые с единичными коэффициентами. В результате получим систему линейных уравнений, с помощью которых вычисляются контрольные разряды. Каждый контрольный разряд является как бы дополнением для определенных информационных разрядов для проверки на четность.

При декодировании вычисляем корректор K=k₄k₂k₁

Если корректор равен нулю, следовательно, ошибок нет. Если корректор не равен нулю, то местоположение вектор-столбца матрицы H, совпадающего с вычисленным корректором, указывает место ошибки. При передаче может возникнуть  двойная и более ошибка. Корректор также не будет равен нулю. В этом случае произойдет исправление  случайного символа и нами будет принят неверный код. Для исключения такого автоматического исправления вводится еще один символ   для проверки всей комбинации на четность. Кодовое расстояние d=4. Тогда матрица H будет иметь вид

Пример 5.4. Дана 1101 - исходная комбинация (k=4). Закодировать ее в коде Хэмминга.

По формуле (5.2) находим число контрольных символов r=3. Берем регистр из 7 ячеек памяти. Размещаем исходную комбинацию в ячейках 3,5,6,7.

1 2 3 4 5 6 7           

* * 1 * 1 0 1           

Находим контрольные символы

 е₄ = 5 + 6 + 7 = 1 + 0 + 1 = 0                   

 е₂ = 3 + 6 + 7 = 1 + 0 + 1 = 0                   

 е₁ = 3 + 5 + 7 = 1 + 1 + 1 = 1                   

Закодированная комбинация будет иметь вид

1 2 3 4 5 6 7           

1 0 1 0 1 0 1           

Допустим, что при передаче возникла ошибка, и мы приняли неверную комбинацию

1 2 3 4 5 6 7

1 0 1 0 1 1 1

Проверяем ее

к ₄ = 4 + 5 + 6 + 7 = 0 + 1 + 1 + 1 = 1

к₂ = 2 + 3 + 6 + 7 = 0 + 1 + 1 + 1 = 1

к₁ = 1 + 3 + 5 + 7 = 1 + 1 + 1 + 1 + 0

K= - в шестом разряде ошибка.

Если бы нам понадобилось построить код и для проверки двойных ошибок, необходимо было бы ввести еще один дополнительный нулевой разряд.

Получим следующий код

0 1 2 3 4 5 6 7        

0 1 0 1 0 1 0 1

При передаче и возникновении ошибки код будет иметь вид

0 1 2 3 4 5 6 7        

0 1 0 1 0 1 1 1

Проверка в этом случае показала бы, что корректор K=110, а проверка всей комбинации на четность E₀ = 0+1+0+1+0+1+1+1=1. Это указывает на одиночную ошибку. Допускается автоматическое исправление  ошибки. 

Существует следующий алгоритм декодирования кода Хэмминга с d=4

Код (7,4) является минимально возможным кодом с достаточно большой избыточностью. Эффективность кода (k/n) растет с увеличением длины кода