Применение кодов Хемминга позволяет исправлять единичные ошибки. Добавление к коду Хемминга контрольного разряда, обеспечивающего четность/нечетность всей кодовой комбинации в целом, приводит к модифицированному коду Хемминга, с помощью которого можно исправлять единичные ошибки и обнаруживать двойные.
Методы контроля с помощью кодов Хемминга основаны на тех же идеях, что и контроль по модулю 2. Отсюда и область эффективного применения кодов Хемминга - устройства, в которых вероятность единичных ошибок много больше, чем вероятность групповых.
Для получения кодовой комбинации кода Хемминга к информационному слову добавляется несколько контрольных разрядов. Для простоты просмотра кодовых комбинаций с целью определения значений контрольных разрядов примем, что контрольные разряды занимают позиции с номерами 2i ( i = О, 1, 2,... ).
Каждый контрольный разряд ассоциируется с некоторой группой разрядов кодовой комбинации и выводит вес группы, в которую он входит, на четность/нечетность.
Первый контрольный разряд входит в группу разрядов с номерами XX...XX1, где Х означает произвольное значение, т.е. 0 либо 1. Иными словами в первую группу входят разряды с нечетными номерами: 1, 3, 5, 7, 9,... .
Второй контрольный разряд входит в группу разрядов с номерами, имеющими единицу во втором справа разряде, т. е. номерами XX...X1X. Это номера 2, 3, 6, 7, 10, 11,... Третий контрольный разряд входит в группу, у которой номера разрядов имеют единицу в третьем справа разряде: ХХ...1ХХ, т. е. с номерами 4, 5, 6, 7, 12, 13, 14, 15,... .
Таблица 2.10
r
а3
а2
а1
r3
а0
r2
r1
а3а2а1а0 = 0110
...
...
...
...
...
...
...
...
Контрольные разряды выводят веса своих групп на четность/нечетность. Далее для определенности примем, что ведется контроль по четности. После выполнения операции (например, считывания кодовой комбинации из памяти) производится столько проверок по модулю 2, сколько контрольных разрядов в кодовой комбинации, т. е. проверяется сохранение четности весов групп. Если в кодовой комбинации произошла ошибка, то в одних проверках она скажется, а в других - нет. Это и позволяет определить разряд, в котором произошла ошибка. Для восстановления правильного значения слова теперь остается только проинвертировать ошибочный разряд. Такова идея построения и использования кода Хемминга.
Пример составления кода Хемминга для четырехразрядного информационного слова А = а3а2а1а0 = 0110 приведен в табл. 2.10.
Через r в таблице обозначен общий контрольный разряд для всей кодовой комбинации, через r1, r2, r3 - первый, второй и третий групповые контрольные разряды.
Для коротких слов избыточность кода Хемминга получилась значительной (здесь на четыре информационных разряда приходится четыре контрольных), но это нетипично, поскольку реально контролируются слова большей разрядности, для которых избыточность (относительная) быстро уменьшается с ростом разрядности слов. Короткое слово взято, чтобы пример не был громоздким.
Рассмотрим теперь процесс исправления и выявления ошибок. Пусть, например, передавалось информационное слово 0110 = 610. Не учитывая пока разряд r, получим, что правильная кодовая комбинация имеет вид:
Пусть во втором слева разряде произошла ошибка и принята комбинация:
Первая проверка (по группе разрядов с нечетными номерами) показывает сохранение четности, т. е. в этой группе ошибок нет, результат этой проверки отмечается нулем.
Вторая проверка (по разрядам 2, 3, 6, 7) обнаруживает нарушение четности веса комбинации, ее результат отмечается единицей.
Третья проверка (по разрядам 4, 5, б, 7) также обнаруживает нарушение четности, ее результат отмечается единицей.
Результаты проверок образуют слово, называемое синдромом. Синдром указывает номер разряда, в котором произошла ошибка. Во взятом примере результаты проверок дают слово 0110 = 610. Проинвертировав разряд номер 6, возвращаемся к правильной кодовой комбинации - ошибка исправлена.
Минимальное кодовое расстояние обычного кода Хемминга равно трем. Добавление разряда проверки общей четности веса комбинации приводит к модифицированному коду Хемминга с минимальным кодовым расстоянием, равным 4 и, соответственно, добавляет возможность обнаружения двойной ошибки. Обнаружение двойной ошибки основано на сопоставлении наличия или отсутствия признаков ошибки в синдроме и общей четности. Если обозначить через S любое ненулевое значение синдрома, то возможные ситуации, используемые для обнаружения двойной ошибки, окажутся следующими (табл. 2.11).
Таблица 2.11
Синдром
Свертка кодовой комбинации
Характеристика результата
Все правильно, слово можно использовать
S
Была единичная ошибка, исправлена, слово можно использовать.
S
Эти ситуации могут возникать только вследствие ошибок двойной или большей кратности, слово использовать нельзя.
