Код Хэмминга

Код Хэмминга исправляет одну ошибку, т.е. относится к классу самокорректирующихся кодов. В алфавите записываются все сообщения в виде слов длины m. Эти сообщения кодируются двоичными наборами где длина кода, > m. Пусть Предположим, что при прохождении кодового слова через канал связи произошла одна ошибка, в таком случае код сообщения на выходе может иметь вид:

вариант.

Для того, чтобы дополнительных разрядов в коде хватало для кодировки варианта, необходимо, т.е. Выберём как наименьшее целое число, удовлетворяющее неравенству

Алгоритм кодирования. Пусть натуральное число , его двоичная запись. Построим последовательности:

П₀ = все числа с

П₁ = все числа с

П₂ = все числа с

П₃ = все числа с

… … … … … … … … … …

П_к-1 = все числа с

Члены набора у которых i Î{1, 2, 4, …, }, называют контрольными, а остальные – информационными. Слово кодируется словом так:

Затем определяются контрольные члены:

Обнаружение ошибки в кодах Хэмминга. Пусть при передаче кода произошла ошибка в S- м члене, т.е. на выходе принято слово и пусть запись S в двоичном исчислении. Рассмотрим число , где

Тогда В самом деле, если , то S не принадлежит первой последовательности и для имеем Если то S принадлежит последовательности П₀

Следовательно, для обнаружения и исправления ошибки достаточно построить

Декодирование. Требуется по коду построить слово Для этого достаточно взять информационные члены в .

Пример 1. Закодировать по Хэммингу слово (111011100).

Решение. Заполнив информационные ячейки, получим??1?110?11100. Ответ: (0010110111100).

Пример 2. В коде была допущена одна ошибка: 0010100111100. Найти её.

Решение.