Коды Хэмминга —наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления. Достоинство кода в том, что реализация алгоритма требует небольших ресурсов и может быть выполнена аппаратно. Это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение.
История
В середине 1940-х годов Ричард Хэмминг работал в знаменитых лабораториях фирмы Белл (Bell Labs) на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки, скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машину с помощью перфокарт, поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и снова запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую. Хэмминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перезагружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который известен как код Хэмминга.
Коды Хемминга — линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку на блок. Код Хэмминга – систематический код, то есть состоящий из информационных и корректирующих символов, расположенных по строго определенной системе, имеющих одинаковую длину и всегда занимающих строго определенные места в кодовых комбинациях.
Коды Хемминга являются самоконтролирующимися кодами, т.е кодами, позволяющими автоматически обнаруживать наиболее вероятные ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок. При этом, мы не получаем никаких указаний о том, в каком именно разряде произошла ошибка, и, следовательно, не имеем возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырёх или вообще в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными. Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно.
Имея n= k + l разрядов, самокорректирующийся код можно построить следующим образом.
Присвоим каждому из разрядов свой номер - от 1 до k+l; запишем эти номера в двоичной системе счисления.
Предположим далее, что все разряды кода разбиты на контрольные группы, которые частично перекрываются, причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определённым контрольным группам. Например: разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера 510 = …0001012 - 1-й и 3-й разряды содержат единицы.
Среди l+k разрядов кода при этом имеется разряды, каждый из которых принадлежит только к одной контрольной группе:
Разряд № 1: 110 = …0000012 принадлежит только к 1-й контрольной группе.
Разряд № 2: 210 = …0000102 принадлежит только к 2-й контрольной группе.
Разряд № 4: 410 = …0001002 принадлежит только к 3-й контрольной группе.
…
Разряд № 2 k − 1 принадлежит только к k -й контрольной группе.
Эти разряды будем считать контрольными. Остальные m разрядов, каждый из которых принадлежит, по меньшей мере, к двум контрольным группам, будут информационными разрядами.
В каждой из k контрольных групп будем иметь по одному контрольному разряду. В каждый из контрольных разрядов поместим такую цифру (0 или 1), чтобы общее количество единиц в его контрольной группе было четным.
Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты, вычисленные по особым правилам. Вторая часть получает входящее сообщение и заново вычисляет контрольные биты по тому же алгоритму, что и первая часть. Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.
Например, довольно распространен код Хеминга с m=7 и k=4.
Пусть исходное слово (кодовое слово без контрольных разрядов) - 01101012.
Обозначим Pi - контрольный разряд №i; а Di - информационный разряд №i, где i = 1,2,3,4…
Можно посмотреть, как перекрываются контрольные группы в данном случае. Первая группа контролирует разряды № 3,5,7,9,11 исходного кода, вторая — 3,6,7,10,11 (№ группы = № контрольного разряда). Очевидно, что они частично перекрываются.
Предположим теперь, для примера, что при передаче данного кодового слова 10001100101 произошла ошибка в 11–м разряде, так, что было принято новое кодовое слово 1000110010 0. Произведя в принятом коде проверку четности внутри контрольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й,2-й и 4-й контрольных группах, и четно в 3-й контрольной группе. Это указывает, во-первых, на наличие ошибки, во-вторых, означает, что номер ошибочно принятого разряда в двоичном представлении содержит единицы на первом, втором и четвёртом местах и нуль - на третьем месте, т.к ошибка только одна, и 3-я контрольная сумма оказалась верной.
Из таблицы следует, что ошибка произошла в 11-м разряде и её можно исправить. Построенный код, разумеется, не рассчитан на возможность одновременной ошибки в двух разрядах.
Например (Рис №2), когда ошибки одновременно прошли в 3-м и 7-м разрядах исходного кода, первый и второй контрольные биты даже не замечают подмены.
Когда в принятом коде производится проверка четности внутри контрольных групп, случай двойной ошибки ничем внешне не отличается от случая одиночной ошибки.
Например, предположим теперь, что при передаче данного кодового слова 10001100101 произошли ошибки в 3-м и 6-м разрядах, так, что принято кодовое слово 10 1 01 0 00101.
Вывод: ошибка произошла в 5-м разряде Истинное кодовое слово: 1 0 0 0 1 1 0 0 1 0 1 Ошибочное кодовое слово: 1 0 1 0 1 0 0 0 1 0 1 Исправленное кодовое слово: 1 0 1 0 0 0 0 0 1 0 1 Результат получается ещё более отдаленным от правильного, чем принятый код. Исправление кода по общему правилу не только не улучшило, но даже ухудшило бы дело.
Рассмотрим самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Полученные n-битные коды образуются так:
- Позиции с номерами 2i (i = 1, 2, …r) резервируются под контрольные биты;
- в остальные биты копируется исходный код в порядке следования его битов.
- вычисляют контрольные разряды
Для того, чтобы понять работу данного алгоритма, рассмотрим пример.
Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.
На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:
и 
После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):
Было:
Стало:
Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».