Код Хэмминга: проверки, которые называют место ошибки

Если можешь расставить проверки в позициях степеней двойки, объяснить происхождение синдрома и показать неудачу при двух ошибках, переходи к «Теперь сам».

Как думаешь, что должно сообщать нарушение проверки

Один бит чётности говорит, что в слове нечётное число единиц. Он не называет позицию изменения. Хотелось бы получить несколько ответов «да или нет», которые вместе зададут адрес. Для семи позиций достаточно трёх битов: значения от 1 до 7 различают места ошибки, а значение 0 оставим для отсутствия ошибки.

Проверочные биты тоже передаются по ненадёжному каналу. Если контролировать только данные, ошибка в самой проверке станет неразличимой. Поэтому адресоваться должны все передаваемые позиции. Сейчас построим код для четырёх информационных битов и трёх проверочных.

На что это похоже

В здании семь комнат с двоичными номерами 001…111. Первый датчик наблюдает комнаты, у которых номер оканчивается на 1, второй - комнаты с единицей в среднем разряде, третий - с единицей в старшем. Если событие произошло ровно в одной комнате, набор сработавших датчиков будет её номером.

Если события произошли в двух комнатах, датчики чётности не считают их количество. Два события в одной группе взаимно гасят ответ. Получившийся номер описывает сочетание нарушений, а не обязательно комнату, где что-то случилось. Ограничение на одно событие составляет часть доказательства, его нельзя молча убрать из аналогии.

Механизм: номер позиции как столбец проверок

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

В каждой группе XOR всех битов должен равняться 0. Собственный проверочный бит входит в свою группу, но не входит в две остальные. Например, двоичный номер 4 равен 100, поэтому позиция 4 принадлежит только третьей проверке. Это позволяет после размещения данных независимо вычислить три проверки: каждая компенсирует XOR своей группы.

У получателя результаты проверок называются синдромом. Соберём число S: результат первой проверки - его младший бит, второй - следующий, третьей - старший. Изменение позиции j нарушает ровно те группы, в которые она входит. Их номера разрядов и составляют двоичную запись j, поэтому S=j. В правильном слове все проверки выполнены, S=0.

Есть короткая запись того же вычисления: XOR номеров всех позиций, содержащих единицу. Для правильного слова результат 0. После изменения одного бита в XOR добавится или исчезнет ровно одно слагаемое j; оба действия равносильны XOR с j. Отсюда адрес ошибки.

Правило

В коде Хэмминга проверочные позиции имеют номера 1,2,4,…. Группа проверки 2^i содержит все позиции, у которых в номере установлен бит i. Проверки задают чётную чётность. При нуле или одной ошибке синдром 0 означает целое слово, а синдром S≠0 указывает единственный бит, который надо инвертировать.

Для k информационных и r проверочных битов должно хватить состояний синдрома: 2^r ≥ k+r+1. Справа стоят все позиции и отдельный случай «ошибки нет». Для полного кода длина равна 2^r−1, число данных 2^r−r−1. Укороченные конструкции используют меньше информационных позиций; обычный Хэмминг(7,4) занимает все семь ненулевых адресов.

Разбор: синдром указывает шестую позицию

Сообщение 10 имеет биты 1010. В нашей раскладке в позициях 3,5,6,7 будут 0,1,0,1. Первая проверка получает XOR 0^1^1=0, вторая 0^0^1=1, третья 1^0^1=0. Кодовое слово в порядке позиций 7…1 равно 1010010.

Инвертируем позицию 6. Слово станет 1110010, проверки дадут S=6. Исправление обратит тот же бит. В программе combinations перебирает пары различных позиций без повторения: это позволит сразу проверить и случай, для которого адресная интерпретация не доказана.

from itertools import combinations


def kod(m):
    w = 0
    for i, p in enumerate([3, 5, 6, 7]):
        w |= ((m >> i) & 1) << (p - 1)
    for q in [1, 2, 4]:
        b = 0
        for p in range(1, 8):
            if p & q:
                b ^= (w >> (p - 1)) & 1
        w |= b << (q - 1)
    return w


def sindrom(w):
    s = 0
    for p in range(1, 8):
        if (w >> (p - 1)) & 1:
            s ^= p
    return s


w = kod(10)
r = w ^ (1 << 5)
print("сообщение 10:", f"{w:07b}")
print("ошибка в позиции 6:", f"{r:07b}", "синдром", sindrom(r))
print("после исправления:", f"{r ^ (1 << (sindrom(r) - 1)):07b}")
good = 0
wrong = 0
for m in range(16):
    w = kod(m)
    for j in range(7):
        r = w ^ (1 << j)
        good += (r ^ (1 << (sindrom(r) - 1))) == w
    for i, j in combinations(range(7), 2):
        r = w ^ (1 << i) ^ (1 << j)
        repaired = r ^ (1 << (sindrom(r) - 1))
        wrong += repaired != w and sindrom(repaired) == 0
print("исправлены одиночные:", good)
print("двойные ошибочно приняты после коррекции:", wrong)

сообщение 10: 1010010
ошибка в позиции 6: 1110010 синдром 6
после исправления: 1010010
исправлены одиночные: 112
двойные ошибочно приняты после коррекции: 336

Число 112 - это 16 сообщений, для каждого семь одиночных ошибок. Среди позиций есть и данные, и проверки: оба типа исправляются. Повторять сообщение один раз без помех полезно для контроля кодировщика, но такая передача не вошла в этот счётчик ошибок.

Разбор: две ошибки называют третью позицию

Изменим позиции i и j правильного слова. Синдром станет i ^ j. Два различных номера из 1…7 дают ненулевой трёхбитный результат. Он снова похож на допустимый адрес ошибки, поэтому декодер изменит ещё одну позицию.

Пример для сообщения 10: изменения позиций 2 и 5 превращают 1010010 в 1000000. Синдром равен 2^5=7. Если инвертировать позицию 7, выйдет 0000000 - правильное слово совсем другого сообщения. Проверки после ремонта выполнены. Программа подтвердила такую неудачу для всех 336 двойных повреждений:16 сообщений умножить на число пар из семи позиций.

Что ломается без этого

Адрес ошибки зависит от раскладки. Если отправитель нумерует биты слева, а получатель справа, одинаковое число синдрома исправляет разные физические позиции. Сначала зафиксируй порядок, затем выпиши группы и проверь по одному изменению в каждой позиции.

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

Зачем это в работе

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

Для фиксированного слова часть проверок выполняется параллельно аппаратурой. Программа выше намеренно проходит позиции циклом: так видно, откуда взялись маски. Ширина слова и стоимость конкретной инструкции определяют скорость реализации; сам адресный принцип не зависит от наличия аппаратной команды подсчёта единиц.

Теперь сам

Получено 0100101. Найди единичные позиции, затем синдром. Какое исправление получится, если гарантируется не больше одной ошибки? Почему ответ уже нельзя гарантировать, если допускаются две?