Калькулятор кода Хэмминга

Как пользоваться

В режиме «Кодировать» выберите код или задайте своё число бит данных k (до 247) и введите данные. Биты вводятся по порядку: первый — d1, он попадает в позицию 3. В шестнадцатеричном виде младший бит числа D0 — это тот же d1, поэтому биты 1100 по порядку — это 0x3. Калькулятор покажет кодовое слово (позиция 1 — первая), расчёт каждого проверочного бита и таблицу покрытия. Щелчок по биту слова или номер в поле «Инвертировать позиции» вносит ошибку — тут же видно синдром и что сделает декодер.

В режиме «Декодировать» введите принятое слово целиком, начиная с позиции 1: калькулятор посчитает синдром, найдёт ошибочную позицию и вернёт исправленные данные, а с битом общей чётности отличит двойную ошибку. Режим «Чётность» считает обычный бит чётности слова — чётный (even) или нечётный (odd).

Как считается

Позиции слова нумеруют с единицы. Проверочные биты стоят в позициях, равных степеням двойки, — 1, 2, 4, 8, …, данные занимают остальные: 3, 5, 6, 7, 9, … Проверочный бит в позиции 2^j охватывает все позиции, в двоичном номере которых есть разряд 2^j, и делает чётным число единиц в своей группе. Число проверочных бит r — наименьшее, при котором синдром может назвать любую из k + r позиций или сказать «ошибок нет»:

Для кода (7,4) группы такие: p1 охватывает позиции 1, 3, 5, 7, p2 — 2, 3, 6, 7, p4 — 4, 5, 6, 7. Данные d1, d2, d3, d4 стоят в позициях 3, 5, 6, 7, откуда

Приёмник пересчитывает каждую проверку по принятому слову c вместе с проверочным битом. Сработавшие проверки, записанные двоичным числом, — синдром S — и есть номер ошибочной позиции:

где $i \,\&\, 2^j$ — поразрядное И номера позиции и веса проверки: XOR берётся по всем позициям, в номере которых есть этот разряд. Если S = 0, все проверки сошлись.

Для SECDED в конец слова дописывают бит общей чётности P — XOR всех n позиций. После приёма его проверяют вместе с синдромом:

Пример: код (7,4)

Данные 1100: d1 = 1, d2 = 1, d3 = 0, d4 = 0. Проверочные биты: p1 = 1 ⊕ 1 ⊕ 0 = 0, p2 = 1 ⊕ 0 ⊕ 0 = 1, p4 = 1 ⊕ 0 ⊕ 0 = 1. Слово по позициям 1–7 — 0111100; в таблице III статьи Хэмминга это слово под номером 12.

Пусть в канале исказилась позиция 5 и пришло 0111000. Проверка p1 по позициям 1, 3, 5, 7 даёт 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1, p2 по позициям 2, 3, 6, 7 — 1 ⊕ 1 ⊕ 0 ⊕ 0 = 0, p4 по позициям 4, 5, 6, 7 — 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1. Синдром s4 s2 s1 = 101₂ = 5: инвертируем пятый бит и получаем исходное 0111100 — тот же разбор приводит Хэмминг.

С битом общей чётности слово становится 01111000: в 0111100 четыре единицы, P = 0. Если исказить позиции 3 и 5, синдром будет 3 ⊕ 5 = 6, но общая чётность сойдётся — декодер SECDED сообщит о двойной ошибке, а простой код (7,4) «исправил» бы позицию 6 и испортил данные. Этот пример открыт в калькуляторе по умолчанию: щёлкните по биту 3 — код (7,4) «исправит» позицию 6, а после включения SECDED сообщит о двойной ошибке.

Сколько нужно проверочных бит

Полные коды длиной 2^r − 1 — (7,4), (15,11), (31,26), (63,57) — используют все синдромы. Привычные ширины 8, 16, 32 и 64 бита дают укороченные коды: старших позиций просто нет. Поэтому в укороченном коде синдром больше n — числа позиций без бита общей чётности P — не может появиться от одной ошибки, и калькулятор помечает такой случай как неисправимый.

Порядок бит и совместимость

Калькулятор пишет слово с позиции 1 слева, как Хэмминг в таблице III. Данные D0, D1, … занимают позиции 3, 5, 6, 7, 9, … — так же их располагают таблица 1 XAPP383 и таблица синдромов на рис. 1 XAPP645 (бит D60 — в позиции 1000100₂ = 68). Бит общей чётности стоит последним и охватывает всё слово вместе с проверочными битами — так у Хэмминга в §4 и в XAPP383, где P5 занимает позицию 22. Хэмминг в таблице III читал информационные позиции 3, 5, 6, 7 как двоичное число с позицией 3 в старшем разряде, поэтому его «12» — это наши биты 1100, а в шестнадцатеричном виде с D0 в младшем разряде — 0x3.

Чужие таблицы часто пишут слово от старшей позиции к младшей: в таблице 1 XAPP383 позиция 1 стоит справа. Бывает различие и в том, что охватывает общий бит. В XAPP645 восьмой бит CB8 — чётность только 64 бит данных (у него в таблице 1 отмечены все биты D0–D63, а проверочные — нет). Это меняет не только само слово, но и выводы декодера: одиночная ошибка в проверочном бите даёт ненулевой синдром при сошедшейся CB8, и по правилу заметки такое слово считается двойной ошибкой, а калькулятор с общим битом по всему слову её исправит. Перед сравнением с чужой реализацией сверьте порядок бит и состав общего бита — иначе при тех же данных слова и решения декодера не совпадут. Перевести данные между двоичной и шестнадцатеричной записью поможет конвертер систем счисления.

Ограничения и типичные ошибки

• Две ошибки без SECDED. В полных кодах (7,4), (15,11), (31,26), (63,57) любая двойная ошибка выглядит одиночной: декодер «исправляет» не ту позицию и портит третий бит. В укороченном коде бывает так же, а бывает, что синдром указывает за конец слова, — тогда ошибка видна, но не исправима. Если в канале возможны две ошибки на слово, нужен SECDED.
• Три ошибки и больше. SECDED гарантирует только исправление одной и обнаружение двух ошибок; три ошибки могут выглядеть как одна и быть «исправлены» неверно, а некоторые сочетания превращают слово в другое кодовое слово с нулевым синдромом.
• Пакеты ошибок. Код рассчитан на независимые одиночные ошибки в слове — сбой ячейки памяти, помеху в одном разряде. Для проверки целостности длинного блока данных применяют CRC: он не исправляет, но надёжно обнаруживает пакеты ошибок.
• Бит чётности вместо кода. Один бит чётности — как в кадре UART формата 8E1 — замечает нечётное число ошибок, но не говорит, где ошибка, и пропускает две. Как он ставится в кадр, показывает калькулятор кадра UART.

Исключающее ИЛИ, из которого собраны кодер и декодер, и другие логические элементы разобраны в статье «Цифровая логика».