Канонический код Хемминга

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:35, 11 мая 2016.

Определение

TemplateDifinitionIcon.svg Определение «Определение - Канонический код Хемминга»
Канонический код Хемминга - это код над полем , проверочная матрица которого имеет канонический вид: каждый столбец является двоичной записью своего номера, т.е. столбцы расположены в лексикографическом порядке: , где
TemplateExampleIcon.svg Пример Пример - Проверочная матрица


Кодирование

TemplateExampleIcon.svg Пример Пример кодирование

Кодирование проще осуществлять по проверочной матрице. Если подписать кодовый вектор под проверочной матрицей, то проверочные разряды окажутся прямо под столбцами с одной единицей - . Остальные будут информационными, на их место уже можно смело записать разряды информационного вектора. Проверочные разряды зададим нулями:

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

Выбираем проверочные символы и каждый проверочный символ представляем как сумму информационных разрядов, у которого в разряде стоят единицы.


Декодирование

TemplateExampleIcon.svg Пример Пример - Декодирование

Этапы декодирования:

  1. ;
  2. ;
  3. .

Рассмотрим подробнее. Пусть был принят вектор , синдром которого:

Так как следовательно, произошла ошибка.

При использовании кода Хемминга синдром вектора соответствует номеру разряда в котором произошла ошибка.

Информационный вектор получим, выписав из кодового вектора все информационные разряды:


Ускорение декодирования

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

Вся схема имеет общую сложность :

Литература

Hamming, Richard W. (1950). "Error detecting and error correcting codes" (PDF). Bell System Technical Journal 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. MR 0035935.

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.