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

Коды, предложенные Р. Хэммингом, обладают способностью обнаружить и исправить одиночные ошибки.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяеется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибок, запишем 0, если есть ошибка - 1. Запись полученной последовательности символов образует двоичное число.

Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибки в коде данная последовательность будет содержать только нули. Полученное число описывает таким образом n=(m+k+1) событий. Следовательно, справедливо неравенство

2^k>=(m+k+1)

(1)

Определить максимальное значение m для заданого n можно из следующего:

n	4...	8...15	16...31	32...63
m	1...	4...11	11...26	26...57
k

Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, это означает, что в результате первой проверки обнаружена ошибка. Первая проверка охватывает позиции 1, 3, 5, 7, 9, ... (в двоичной записи этих чисел младший разряд равен 1). Вторая проверка - 2, 3, 6, 7, 10...

Проверка N	Проверяемые разряды
	1, 3, 5,7, 9, 11, 13, 15, ...
	2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, ...
	4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23
	8, 9, 10, 11, 12, 13, 14, 15, 24, ...
...	...

Для контроля будем использовать позиции 1,2,4,8,..., так как в данные позиции встречаются только в одной проверяемой группе символов.

Примеры кодирования информации по коду Хемминга для семиразрадного кода:

Разряды двоичного числа	Кодируемая десятичная информация
1 k₁	2 k₂	3 m₁	4 k₃	5 m₂	6 m₃	7 m₄

Как видно из таблицы, n=7, m=4, k=3 и контрольнми будут разряды 1, 2, 4.

Введем, например, одиночную ошибку в код числа 5 - 0100101₍₂₎. Пусть после такой ошибки код стал 0110101. Подсчитываем суммы по модулю групп цифр и выписываем справа налево: 0011. Получилось ненулевое число, равное номеру позици, в которой возникла ошибка (3).

По методу Хэмминга могут быть построены коды разной длины. Чем больше длина кода, тем меньше относительная избыточность. Например, для контроля 48-разрядного числа, потребуется только шесть дополнительных (контрольных) разрядов. Коды Хэмминга используют в основном для контроля передачи информации по каналам связи.

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