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

Как устроен код Хэмминга

Код Хэмминга добавляет к данным несколько контрольных битов так, чтобы любую одиночную ошибку можно было не только обнаружить, но и исправить. Биты кодового слова нумеруются с единицы. Контрольные биты стоят на позициях, равных степеням двойки — 1, 2, 4, 8, 16…, а биты данных занимают остальные позиции.

Контрольный бит на позиции 2ⁱ проверяет все позиции, в двоичном номере которых установлен i-й разряд. Например, p1 проверяет позиции 1, 3, 5, 7…, p2 — позиции 2, 3, 6, 7, 10, 11…, p4 — позиции 4–7, 12–15… Значение контрольного бита выбирают так, чтобы в каждой проверяемой группе было чётное число единиц.

Если r — число контрольных битов, то длина блока n = 2^r − 1, а данных в нём k = n − r: получаются коды (7,4), (15,11), (31,26), (63,57). Минимальное кодовое расстояние кода Хэмминга равно 3, поэтому он исправляет одну ошибку в блоке.

Синдром и исправление ошибки

Получатель заново вычисляет все проверки по принятому слову. Номера проверок, которые не сошлись, складываются в двоичное число — синдром. Если синдром равен нулю, ошибок нет. Иначе синдром прямо указывает номер позиции с ошибкой: достаточно инвертировать этот бит.

Пример

Закодируем данные 1011 кодом (7,4). Биты данных занимают позиции 3, 5, 6, 7: d1 = 1, d2 = 0, d3 = 1, d4 = 1. Контрольные биты: p1 = d1 ⊕ d2 ⊕ d4 = 0, p2 = d1 ⊕ d3 ⊕ d4 = 1, p4 = d2 ⊕ d3 ⊕ d4 = 0. Кодовое слово: 0110011.

Пусть при передаче исказился шестой бит, и пришло 0110001. Проверка p1 (позиции 1, 3, 5, 7) сходится, p2 (2, 3, 6, 7) и p4 (4, 5, 6, 7) — нет. Синдром 110₂ = 6: ошибка в шестой позиции. Инвертируем её и получаем исходное слово 0110011 и данные 1011.

Расширенный код Хэмминга (SECDED)

Если к коду добавить ещё один бит — общую чётность всего слова, кодовое расстояние вырастает до 4. Такой код исправляет одиночные ошибки и надёжно обнаруживает двойные (Single Error Correction, Double Error Detection). Именно он используется в памяти ECC серверов. В калькуляторе общий бит чётности ставится в конец блока.

• Синдром 0, общая чётность сходится — ошибок нет.
• Синдром не 0, общая чётность нарушена — одиночная ошибка, исправляется по синдрому.
• Синдром 0, чётность нарушена — ошибка в самом бите общей чётности.
• Синдром не 0, чётность сходится — двойная ошибка: обнаружена, но исправить нельзя.

Где применяется

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