Код Хэмминга

Задача, которую решил Хэмминг

Ричард Хэмминг работал в Bell Labs с релейной вычислительной машиной, которая по выходным считала без оператора. Обнаружив ошибку по контролю чётности, машина останавливалась, и результат двух суток счёта пропадал. Раздражение от этого и породило в 1950 году статью в Bell System Technical Journal, где впервые был описан класс кодов, умеющих не только заметить сбой, но и починить его на лету.

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

Формально это выражается через кодовое расстояние. Классический код Хэмминга имеет минимальное расстояние 3: любые два допустимых кодовых слова различаются не менее чем в трёх позициях. Расстояние 3 даёт исправление одной ошибки либо обнаружение двух — но не то и другое одновременно.

Схема (7,4): как это выглядит в битах

Самый известный представитель семейства — код Хэмминга (7,4): четыре информационных бита плюс три проверочных, итого семь. Позиции нумеруются с единицы, и проверочные биты занимают степени двойки: 1, 2 и 4. Информационные попадают на позиции 3, 5, 6 и 7.

Каждый проверочный бит отвечает за те позиции, в двоичной записи номера которых стоит соответствующий разряд. Бит на позиции 1 контролирует позиции 1, 3, 5, 7; бит на позиции 2 — позиции 2, 3, 6, 7; бит на позиции 4 — позиции 4, 5, 6, 7. Значение бита выбирается так, чтобы чётность его группы была нулевой.

При приёме проверки повторяются, и результаты записываются как двоичное число — синдром. Синдром 000 означает, что ошибок нет. Любое другое значение читается напрямую как номер сбойной позиции: синдром 101 — это позиция 5, синдром 111 — позиция 7. Изящество схемы в том, что декодер не ищет ошибку перебором, он получает её адрес готовым числом.

Семейство строится по общей формуле: r проверочных бит защищают блок длиной 2^r − 1, из которых информационных 2^r − r − 1. При r = 3 получается (7,4) с избыточностью 75%, при r = 4 — код (15,11) с избыточностью 36%, при r = 7 — код (127,120) с избыточностью менее 6%. Чем длиннее блок, тем дешевле защита, но тем выше риск, что в блоке окажется больше одной ошибки, а вторую такой код уже не исправит и вдобавок «починит» не тот бит.

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

SEC-DED и другие расширения

У базовой схемы есть опасный сценарий: две ошибки в блоке дают ненулевой синдром, который указывает на третью, ни в чём не повинную позицию. Декодер «исправит» её и выдаст испорченные данные, не подав ни одного сигнала тревоги. Чтобы этого избежать, к коду добавляют ещё один бит — общую чётность всего слова. Кодовое расстояние вырастает до 4, и схема становится SEC-DED: single error correction, double error detection. Одну ошибку она чинит, две обнаруживает и честно сообщает об отказе.

Именно так работает память с ECC в серверах: расширенный код Хэмминга (72,64) хранит 8 проверочных бит на каждые 64 бита данных, то есть добавляет 12,5% объёма. Одиночный сбой ячейки, вызванный космической частицей или деградацией, исправляется прозрачно для операционной системы, двойной — фиксируется в машинном журнале и приводит к аварийной остановке вместо тихой порчи данных.

Хэмминг рядом со штриховыми и двумерными кодами

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

Зато прямые родственники Хэмминга в двумерных кодах присутствуют. Коды Хэмминга — частный случай кодов БЧХ с расстоянием 3, и служебные поля QR-символа защищены именно БЧХ: строка информации о формате использует BCH(15,5), а информация о версии для символов начиная с седьмой — BCH(18,6). Логика та же самая: короткое служебное поле, ошибка в котором делает нечитаемым весь код, поэтому оно продублировано и снабжено собственной коррекцией. Подробности — в термине код БЧХ и в описании информации о формате QR.

Общая иерархия методов — от чётности к CRC, от CRC к корректирующим кодам и криптографическим хешам — разобрана в термине помехоустойчивое кодирование.

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

Сколько ошибок исправляет код Хэмминга?

Классическая схема с кодовым расстоянием 3 исправляет ровно одну ошибку в блоке. Расширенная схема SEC-DED с дополнительным битом общей чётности исправляет одну и надёжно обнаруживает две, не пытаясь их чинить. Если ошибок больше, код либо промолчит, либо испортит данные ещё сильнее — для таких условий берут коды с большим расстоянием или коды Рида — Соломона.

Почему проверочные биты стоят на позициях 1, 2, 4, 8?

Потому что тогда синдром сразу читается как номер ошибочной позиции в двоичном виде. Каждый проверочный бит отвечает за позиции, у которых в номере выставлен его разряд, и не участвует в чужих группах. Разместить проверочные биты можно и в конце блока, но тогда декодеру придётся отдельно пересчитывать соответствие синдрома и позиции — лишняя работа без выигрыша.

Чем код Хэмминга отличается от CRC?

Разные задачи. CRC только обнаруживает искажения, зато гарантированно ловит длинные пакеты ошибок и стоит очень дёшево — его ставят там, где повреждённый кадр можно запросить заново. Код Хэмминга обнаруживает меньше, но исправляет одиночную ошибку без повторной передачи. В памяти и на печатной этикетке повтор запросить не у кого, поэтому там нужна коррекция, а не сигнализация.

Что такое синдром простыми словами?

Это результат повторной проверки на стороне приёмника, записанный как двоичное число. Нули означают, что все проверочные группы сошлись и данные целы. Ненулевое значение равно номеру позиции, в которой бит перевернулся. Декодер просто переворачивает бит с этим номером обратно — вычислять ничего больше не нужно.

Применяется ли код Хэмминга в QR-кодах?

В области данных нет — там работает алгоритм Рида — Соломона, потому что типичные повреждения печатного кода локальные и затрагивают группы соседних модулей. Но служебные поля QR защищены кодами БЧХ, обобщением кодов Хэмминга: BCH(15,5) для информации о формате и BCH(18,6) для информации о версии. Плюс эти поля физически продублированы в разных углах символа.