Коды, исправляющие одиночную ошибку. Код Хэмминга
В 1948 г. Р.Хеммингом был предложен принцип кодирования информации, который позволяет не только обнаружить существование ошибки, но и локализовать (определить в каком бите она находится) и устранить ее. Подобные коды стали называться кодами Хемминга.
Основная идея состоит в добавлении к информационным битам не одного, а нескольких битов четности, каждый из которых контролирует определенные информационные биты.
Если пронумеровать все биты передаваемые биты, начиная с 1 слева направо (информационные биты нумеруются с 0 и справа налево), то контрольными (проверочными) оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8-битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8:
Если составить таблицу, в которой указать номера проверочных битов, а также номера контрольных битов (строка, соответствующая проверочному биту, - это все числа в двоичной системе счисления, для записи которых используется значение этого бита), получим:
| Проверочные биты | Контролируемые биты | |||||||||||
| 20=1 | … | |||||||||||
| 21=2 | … | |||||||||||
| 22=4 | … | |||||||||||
| 23=8 | … | |||||||||||
| 24=16 | … | |||||||||||
| 25=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 компакт-дисков.