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

В 1948 г. Р.Хеммингом был предложен принцип кодирования информации, который позволяет не только обнаружить существование ошибки, но и локализовать (определить в каком бите она находится) и устранить ее. Подобные коды стали называться кодами Хемминга.

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

Если пронумеровать все биты передаваемые биты, начиная с 1 слева направо (информационные биты нумеруются с 0 и справа налево), то контрольными (проверочными) оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8-битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8:

Если составить таблицу, в которой указать номера проверочных битов, а также номера контрольных битов (строка, соответствующая проверочному биту, - это все числа в двоичной системе счисления, для записи которых используется значение этого бита), получим:

Проверочные биты

Контролируемые биты

2⁰=1

…

2¹=2

…

2²=4

…

2³=8

…

2⁴=16

…

2⁵=32

…

При этом в перечень контролируемых битов входит и тот, в котором располагается проверочный.

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

Пусть, например, пришло следующее сообщение:

Бит 1 (контролирует 1,3,5,7,9, 11 биты. Сумма единиц в них нечетная) указывает на наличие ошибки в каком-либо бите с нечетным номером.

Бит 2 (контролирует 2,3,6,7,10,11 бит, сумма единиц в них четная) свидетельствует о том, контролируемые биты переданы верно, Что позволяет исключить ошибку в 3, 7 и 11 битах, т.е. ошибка в 5 или 9-м.

Бит 4 (контролируемые 4,5,6,7,12 биты, сумма единиц нечетная) указывает, что ошибка в 5-м бите.

Таким образом, однозначно устанавливается, что ошибочным является 5-й бит – можно исправить его значение на противоположное и, тем самым, восстановить правильную последовательность.

Более детальное рассмотрение кодов Хемминга позволяет сформулировать простой алгоритм проверки и исправления передаваемой последовательности бит:

- произвести проверку всех битов четности;

- если все биты четности верны, то перейти к п.(e);

- вычислить сумму номеров всех неправильных битов четности;

- инвертировать содержимое бита, номер которого равен сумме, найденной в п.(c);

- исключить биты четности, передать правильный информационный код.

Избыточность кодов Хемминга для различных длин передаваемых последовательностей приведена ниже:

Число информационных бит Число контрольных бит Избыточность

1,50

1,31

1,06

Из сопоставления видно, что выгоднее передавать и хранить более длинные последовательности бит.

Безусловно, данный способ кодирования требует увеличения объема памяти компьютера приблизительно на одну треть при 16-битной длине машинного слова, однако, он позволяет автоматически исправлять одиночные ошибки.

Методы коррекции ошибок широко используются в целях повышения надежности ВТ. Например, они используются в драйверах магнитных дисков большой емкости, чтобы снизить вероятность искажения хранимой информации в результате дефектов поверхности диска. Более того, главное отличие между форматом, используемым в звуковых компакт-дисках, и форматом CD-ROM, заключается именно в использовании кодов с исправлением ошибок. Функция исправления ошибок в формате CD-DA позволяет устранить только одну ошибку на два компакт диска. Однако, для компаний, поставляющих ПО, наличие ошибок в 50% поставляемыми ими компакт-дисков является совершенно недопустимым. Поэтому в формат CD-ROM включены дополнительные средства, позволяющие снизить вероятность возникновения ошибки до одной на 20 000 компакт-дисков.

[1] О – одинарный формат; Д –двойной формат