Лекция 9. Код Хэмминга

Данный код позволяет исправлять однократную ошибку в передаваемом сообщении. Под однократной понимается ошибка, возникающая только в одном из битов сообщения. Код Хэмминга не способен исправлять ошибки большей кратности — для исправления таких ошибок существуют более сложные способы кодирования (коды БЧХ, коды Рида-Соломона и другие). В то же время код Хэмминга достаточно быстрый, и его целесообразно использовать в тех случаях, когда ошибки при передаче данных возникают, по статистике, не чаще одного раза на передаваемое сообщение.

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

Пусть вся передаваемая информация разбивается на блоки размером N бит. Значение N обычно берется не менее 8, что соответствует одному байту. Если качество канала передачи информации хорошее (в среднем одна ошибка на 100 бит и реже), то N может быть увеличено до 32 и больше, то есть компьютер может пытаться за один раз передать блок в 32 бита и только потом проверить — возникла ошибка или нет. Если качество канала невысокое и ошибки возникают часто, значение N следует уменьшать. Величина N не обязательно должна быть кратна степени двойки.

Рассмотрим пример кодирования сообщения длиной N=10. Пусть задано следующее сообщение:

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

1. На первом шаге алгоритма необходимо «внедрить» в кодируемое сообщение специальные добавочные биты. Такие биты всегда ставятся в разряды, номера которых кратны степени двойки. Такими разрядами являются первый, второй, четвертый, восьмой, шестнадцатый и т. д.

После внедрения добавочных разрядов наше сообщение принимает следующий вид:

Здесь добавочные биты показаны закрашенными клетками. Пока значения добавочных битов не определены. Очевидно, что добавочные биты «разрывают» передаваемое сообщение, причем относительный порядок битов исходного сообщения сохраняется. Также можно заметить, что длина сообщения увеличилась до 14 битов.

2. Теперь сформируем значения добавочных битов. Здесь мы будем использовать не только значения разрядов сообщения, но и номера разрядов (точнее, их двоичное представление). Например, самый старший разряд имеет номер 1410 = 11 102, самый младший разряд — номер 110=12. Если бы у самого старшего разряда был номер 2510=110 012, то номер самого младшего разряда также обозначался бы пятиразрядным двоичным кодом 12. Таким образом, разрядность двоичного представления номеров разрядов одинакова для всех разрядов кодируемого сообщения.

Выполним следующее. Выпишем в столбик двоичные номера всех разрядов, содержащих единичные значения битов. В нашем примере это будут разряды с номерами 14, 13, 12, 10, 9, 6, 3.

Между всеми разрядами каждого столбика выполним операцию сложения по модулю 2. Визуально это можно сделать следующим образом: если число единиц в столбце четное — результат равен нулю, нечетное — единице. В результате для каждого из столбцов мы получим один бит результата:

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

Данное сообщение готово к передаче по каналу связи. Предположим, что в процессе передачи бит № 11 был передан с ошибкой: вместо переданного нуля была принята единица:

Компьютер, принимающий сообщение, ничего не знает о том, была ли ошибка, и если была — то в каком разряде. Тем не менее, он делает те же самые действия, что делались для получения значений добавочных битов. Сделаем эти действия вручную.

В столбик записываем двоичные номера всех разрядов, равных единице (включая и добавочные разряды):

Можно заметить, что в данной таблице появился одиннадцатый «неправильный» разряд (поскольку он в принятом сообщении равен единице), а также равные единицам добавочные разряды 8 и 1.

Выполняя для каждого столбца операцию сложения по модулю 2, получим следующий результат:

Данная комбинация битов представляет собой двоичное значения числа «одиннадцать» и соответствует номеру того разряда, который был передан с ошибкой. Как видим, с помощью кода Хэмминга компьютер, принявший сообщение, смог сам обнаружить ошибку — причем не только факт наличия ошибки, но и точное ее положение в принятом сообщении. Бит — это всегда одно из двух чисел — ноль или единица, поэтому обнаруженная ошибка исправляется элементарно — путем замены значения бита на противоположное. В нашем случае для получения исходного сообщения необходимо сделать два действия:

• 1) инвертировать одиннадцатый бит;
• 2) выбросить из сообщения все добавочные биты.

Студентам предлагается самостоятельно выполнить и проанализировать примеры декодирования для следующих ситуаций:

• — ошибка произошла в разряде, изначально равном единице;
• — ошибка произошла в одном из добавочных разрядов;
• — ошибки произошли одновременно в двух разрядах;
• — ошибки произошли одновременно в трех разрядах;

Заметим, что если при передаче сообщения ошибки не произошло, то результат сложения по модулю 2 номеров единичных разрядов будет равен нулю (0000). Поскольку мы изначально нумеровали разряды с единицы, а не с нуля, то в принятом сообщении нет разряда с номером ноль. Таким образом, получаемый код «0000» не может быть спутан с номером разряда и однозначно свидетельствует об отсутствии ошибки.

Рассмотренный код Хэмминга позволяет исправить лишь однократную ошибку. При возникновении ошибок в нескольких разрядах возможны ситуации, когда в процессе декодирования будет получена комбинация «0000», говорящая якобы об отсутствии ошибки. Сделать здесь ничего нельзя: при частых ошибках код Хэмминга будет работать неправильно, исправляя ошибки не в тех местах и пропуская ошибочные биты. В таком случае следует использовать более «серьезные» помехозащищенные коды.