Информатика · объяснение и практика

Синдром Хэмминга: как проверки указывают ошибочный разряд

Синдром кода Хэмминга (7,4): проверки чётности, нумерация позиций и граница исправления одной ошибки.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта

В маршруте Цифровая схема и работа вычислителя · 10 тем

Главная мысль

В коде Хэмминга (7,4) три проверки чётности дают синдром. При согласованной нумерации его двоичное значение указывает позицию единственной ошибки. Это заключение требует предположения об одной ошибке: несколько испорченных битов могут дать такой же синдром.

Соглашение важнее красивой таблицы

Пронумеруем позиции слева направо от 1 до 7. Проверочные биты поставим в позиции 1, 2 и 4, остальные четыре позиции займут данные. Используем чётную сумму единиц в каждой проверяемой группе. Порядок записи обязательно сообщаем заранее: нумерация справа налево дала бы другую внешнюю трассу.

Проверка s1 охватывает позиции 1, 3, 5, 7; s2 — 2, 3, 6, 7; s4 — 4, 5, 6, 7. Суммируем биты по модулю два. Синдром записываем как s4s2s1, то есть веса проверок равны 4, 2 и 1. Это описание алгоритма, а не три независимых номера ошибки.

Проследим конкретную одиночную порчу

Пусть передано слово 0110011. Для первой группы сумма равна двум, для второй — четырём, для третьей — двум: все проверки чётные. Теперь в шестой позиции единицу заменили нулём. Получилось 0110001. Важно проверять полученное слово, а не заново кодировать предположительно правильные данные.

Первая группа остаётся чётной, вторая и третья становятся нечётными. Получаем s1=0, s2=1, s4=1. Синдром 110₂ равен шести. Инвертирование шестой позиции возвращает 0110011. После исправления полезно повторить все проверки, но нулевой синдром сам по себе не доказывает, что исходная передача была без многобитовой ошибки.

Пример

0110001: s1=0, s2=1, s4=1; 4+2=6. Исправляем позицию 6.

В каждом проверочном наборе шестая позиция присутствует именно тогда, когда соответствующий разряд числа 6 равен единице.

Почему две ошибки меняют вывод

Если одновременно испорчены позиции 2 и 6, синдром складывает их двоичные номера по XOR: 010 XOR 110 = 100. Обычный декодер одной ошибки решит, что повреждена четвёртая позиция. Он не может восстановить две ошибки только по этому короткому результату.

Поэтому в ответе на учебную задачу нужны два пункта: вычисленный синдром и допустимая модель повреждения. Расширенные коды с дополнительной общей проверкой позволяют различать некоторые случаи лучше, но это уже другая схема. Нельзя приписывать её возможности семибитовому коду только из-за общего имени Хэмминга.

От чтения к действию

А теперь — вы

При соглашении s4s2s1 получены s1=1, s2=1, s4=0. Какая позиция подозревается при ровно одной ошибке?

Частые вопросы

Почему проверочные позиции — степени двойки?

Их номера задают отдельные разряды двоичного адреса позиции; участие в группах становится систематическим.

Синдром 000 гарантирует отсутствие любой ошибки?

Нет. Он сообщает, что проверки выполнены. Некоторые многобитовые изменения переводят одно допустимое слово в другое.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться