Доказательство. Перепишем условия (9) следующим образом

Перепишем условия (9) следующим образом:

(10)

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

(11)

Разряды – степени числа 2 называются контрольными, их , остальные разряды называются информационными. Информационные разряды заполняются произвольным образом, формируя множество кодовых слов, их будет , контрольные разряды вычисляются по информационным в соответствии с уравнениями (11).

Найдем число контрольных разрядов, если длина кодового слова равна .

или , где минимальное натуральное число, удовлетворяющее этому неравенству. Это условие можно записать следующим образом:

что, по определению, означает

Докажем, что код Хэмминга исправляет одну ошибку типа замещения.

Пусть посланное кодовое слово, принадлежащее коду Хэмминга, это же слово, полученное при передаче, и пусть ошибка произошла в -том разряде:

Исправить ошибку означает установить номер разряда с ошибкой, то есть найти, чему равно .

По полученному слову найдем числа :

где – сумма по модулю .

Утверждается, что число – двоичный код числа .

Действительно, пусть , покажем, что .

Пусть , тогда число , то есть номер разряда с ошибкой, не входит в множество и

Пусть , тогда число (номер разряда с ошибкой) входит в множество и .

Таким образом, и номер разряда с ошибкой .

Пример 9. Построить код Хэмминга для кодирования 10 букв .

Решение. Найдем число информационных разрядов для кодирования 10 букв. Их, очевидно, должно быть 4: , но трех информационных разрядов недостаточно, так как . Информационными разрядами будут , контрольными разрядами будут , что согласовывается с формулой . Длина кодового слова равна 7, все числа от 1 до 7 кодируются трехразрядными двоичными кодами . Дальше осталось произвольным образом заполнить информационные разряды и найти по формулам (11) контрольные (табл. 27).

Таблица 27

Буква закодировалась словом 0010110, пусть при передаче произошла ошибка в пятом разряде, то есть . Найдем номер разряда с ошибкой по полученному слову.

Номер разряда с ошибкой равняется .

Часто даются кодовые слова некоторого равномерного кода, состоящие только из информационных разрядов, которые надо закодировать кодом Хэмминга.

Пример 10. Пусть – кодовое слово, состоящее из информационных разрядов. Заполним все разряды, не являющиеся степенями числа 2, для контрольных разрядов оставим свободные места; число их, а также длина слова найдутся автоматически:

Контрольными разрядами оказались . Числа от 1 до 12 кодируются четырехзначными двоичными кодами и образуют 4 подмножества: .

Заполнив контрольные разряды, получим кодовое слово в коде Хэмминга:

Пример 11. Пусть – кодовое слово, закодированное кодом Хэмминга, полученное в процессе передачи. Найдем номер разряда с ошибкой, если ошибки нет, то метод Хэмминга даст в качестве такого номера 0.