Код Хэмминга

Урок о том, как добавить несколько контрольных бит так, чтобы приёмник сам нашёл и починил испорченный бит.

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

Зачем это нужно

Бит чётности и контрольная сумма умеют лишь поднять тревогу: «данные испорчены». Но в реальной связи переспросить отправителя получается не всегда — спутник далеко, запись на диск уже произошла, поток идёт в реальном времени. Хочется не обнаружить ошибку, а сразу её исправить на приёмной стороне. Именно это делает код Хэмминга, придуманный Ричардом Хэммингом в 1950 году. Цена — несколько дополнительных контрольных бит, зато одиночная ошибка чинится автоматически.

Сколько нужно контрольных бит

Пусть у нас $m$ информационных бит и мы добавляем $k$ контрольных. Всего в кадре $m+k$ бит. Чтобы исправить одиночную ошибку, проверки должны различать $m+k$ вариантов «испортился бит номер i» плюс ещё один вариант «ошибок нет» — итого $m+k+1$ ситуаций. Каждый контрольный бит даёт нам один бит ответа, а $k$ бит кодируют $2^k$ значений. Отсюда основное неравенство Хэмминга:

$$ 2^k \ge m + k + 1 $$

Подберём $k$ для четырёх информационных бит ($m=4$). При $k=2$: $2^2=4$, а $4+2+1=7$ — мало. При $k=3$: $2^3=8 \ge 4+3+1=8$ — подходит впритык. Значит, четырём битам данных нужно три контрольных, всего семь бит. Так получается знаменитый код Хэмминга (7,4): 7 бит кадра, 4 из них информационные.

Где стоят контрольные биты

Хитрость Хэмминга — расставить контрольные биты на позициях, равных степеням двойки: 1, 2, 4, 8, ... Нумерация позиций идёт слева, с единицы. Тогда позиции 1, 2, 4 занимают контрольные биты $p_1, p_2, p_3$, а позиции 3, 5, 6, 7 — информационные $d_1, d_2, d_3, d_4$.

Позиция	1	2	3	4	5	6	7
Бит	p1	p2	d1	p3	d2	d3	d4

Зачем именно степени двойки? Запишем номер каждой позиции в двоичном виде. Контрольный бит $p_1$ (позиция 1 = $001_2$) отвечает за все позиции, у которых младший двоичный разряд равен 1: это 1, 3, 5, 7. Бит $p_2$ (позиция 2 = $010_2$) — за позиции со средним разрядом 1: 2, 3, 6, 7. Бит $p_3$ (позиция 4 = $100_2$) — за позиции со старшим разрядом 1: 4, 5, 6, 7. Каждый контрольный бит выбирают так, чтобы чётность «его» группы была нулевой.

Кодируем пример

Пусть данные $d_1 d_2 d_3 d_4 = 1011$. Расставим их по позициям 3, 5, 6, 7 и посчитаем контрольные биты по чётности (even parity, XOR):

$$ p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0 $$

$$ p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1 $$

$$ p_3 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0 $$

Собираем кадр по позициям 1..7: $p_1 p_2 d_1 p_3 d_2 d_3 d_4 = 0\,1\,1\,0\,0\,1\,1$, то есть 0110011. Это и уходит в канал.

Как это работает: синдром

Приёмник для каждой из трёх групп заново считает чётность — получает три бита $s_3 s_2 s_1$, которые называют синдромом. Если все проверки сошлись, синдром равен $000$ — ошибок нет. А если какой-то бит перевернулся, синдром, прочитанный как двоичное число, укажет точную позицию испорченного бита. Это и есть главная магия: номер ошибки получается сам собой.

Пусть в канале седьмой бит испортился и пришло 0110010 вместо 0110011. Проверяем группы (чётность должна быть 0):

$s_1$ по позициям 1,3,5,7: биты $0,1,0,0$ — единиц одна, нечётно $\Rightarrow s_1=1$.
$s_2$ по позициям 2,3,6,7: биты $1,1,1,0$ — единиц три, нечётно $\Rightarrow s_2=1$.
$s_3$ по позициям 4,5,6,7: биты $0,0,1,0$ — единиц одна, нечётно $\Rightarrow s_3=1$.

Синдром $s_3 s_2 s_1 = 111_2 = 7$. Значит, испорчен бит на позиции 7 — переворачиваем его обратно и получаем исходное 0110011. Ошибка исправлена без всякого переспроса.

Проверим всю цепочку на рабочем Python: кодирование, внесение ошибки, вычисление синдрома и исправление.

def encode(d1, d2, d3, d4):
    p1 = d1 ^ d2 ^ d4
    p2 = d1 ^ d3 ^ d4
    p3 = d2 ^ d3 ^ d4
    # позиции 1..7: p1 p2 d1 p3 d2 d3 d4
    return [p1, p2, d1, p3, d2, d3, d4]

def syndrome(frame):
    b = [0] + frame            # сдвиг, чтобы индекс совпал с позицией 1..7
    s1 = b[1] ^ b[3] ^ b[5] ^ b[7]
    s2 = b[2] ^ b[3] ^ b[6] ^ b[7]
    s3 = b[4] ^ b[5] ^ b[6] ^ b[7]
    return s3 * 4 + s2 * 2 + s1   # синдром как число = позиция ошибки

frame = encode(1, 0, 1, 1)
print("Кодовое слово:", frame)

# вносим ошибку в позицию 7 (последний бит)
frame[6] ^= 1
print("Принято с ошибкой:", frame)

pos = syndrome(frame)
print("Синдром (позиция ошибки):", pos)

if pos != 0:
    frame[pos - 1] ^= 1        # переворачиваем испорченный бит обратно
print("Исправлено:", frame)

Вывод:

Кодовое слово: [0, 1, 1, 0, 0, 1, 1]
Принято с ошибкой: [0, 1, 1, 0, 0, 1, 0]
Синдром (позиция ошибки): 7
Исправлено: [0, 1, 1, 0, 0, 1, 1]

Частые ошибки

Считать, что Хэминг чинит любое число ошибок. Базовый код (7,4) исправляет ровно одну ошибку в кадре. Две одновременные ошибки он либо не исправит, либо «починит» неверно.
Ставить контрольные биты не на степени двойки. Только позиции 1, 2, 4, 8 дают красивое свойство «синдром = номер ошибки». При другом размещении этот фокус ломается.
Нумеровать позиции с нуля. В коде Хэмминга позиции считают с единицы; синдром $000$ означает «ошибок нет», а не «позиция 0».
Путать $m$ и $k$ в неравенстве. $m$ — информационные биты, $k$ — контрольные; неравенство $2^k \ge m+k+1$ решают относительно $k$.

Итоги

Код Хэмминга добавляет контрольные биты так, что приёмник находит и исправляет одиночную ошибку.
Число контрольных бит $k$ берут из неравенства $2^k \ge m+k+1$; для $m=4$ получаем $k=3$ и код (7,4).
Контрольные биты стоят на позициях-степенях двойки (1, 2, 4), каждый отвечает за свою группу позиций.
Синдром — три бита проверок; прочитанный как число, он равен позиции испорченного бита (000 — ошибок нет).
Базовый код исправляет одну ошибку на кадр; для большего нужны более мощные коды.