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

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

, где m=1,2,… – некоторое положительное число.

Пример:

Если m=3, то имеем код (7,4).

Особой разновидностью кодов Хэмминга являются коды d_min=3, т.е. коды, позволяющие исправлять все одиночные ошибки. Длина кода Хэмминга в этом случае равна:

(1) n ≤ 2^r – 1.

Подставляя в (1) r=n-k, где r - число проверочных разрядов, а k - число информационных разрядов, получим . Данное неравенство является исходным в определении длины КК по заданному числу k информационных символов. Так, при k=4 n=7, а при k=5 n=9.

Проверочная матрица кода Хэмминга H имеет особое совйство, которое позволяет существенно облегчить описание кода. Проверочная матрица (n,k)-кода имеет (n-k) строк и n столбцов. Для двоичного (n,k)-кода Хэмминга столбцов состоят из всех возможных двоичных векторов с n-k= r элементами, исключая вектор со всеми нулевыми элементами. Для кода Хэмминга (7,4) проверочная матрица имеет вид:

От проверочной матрицы можно перейти к системе проверочных уравнений:

, где а₁, а₂, а₄ – проверочные элементы, а₃, а₅, а_6, а₇ – информационные элементы.

Такое расположение столбцов в проверочной матрце удобно тем, что в результате решения системы проверочных уравнений получается синдром, обладающий ососбенным свойством: он представляет собой двочную запись номера разряда, в котором произошла ошибка.

Например, при декодировании решается система проверочных уравнений вида:

=> если не нули, то есть ошибка. Для того, чтобы определить, где она находится, достаточно лишь прочитать совокупность решений системы уравнений снизу вверх как двоичное число. Пример: