Как данные чинят сами себя: коды коррекции ошибок Хэмминга

Что, если бы текст умел сам подсказывать, в каком месте опечатка, и тут же её исправлять? С битами это возможно.

Избыточность — не расточительство, а страховка: добавь немного лишнего, и сообщение переживёт повреждение.

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

Сначала научимся замечать ошибку

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

Беда в том, что бит чётности лишь сигналит «здесь что-то не так», но не говорит где. Исправить он не может. Хэмминг пошёл дальше.

Идея Хэмминга: несколько проверок сразу

Вместо одного контрольного бита Хэмминг расставляет несколько, каждый из которых следит за своим, пересекающимся набором позиций. Контрольные биты ставятся на позиции — степени двойки: $1, 2, 4, 8, \dots$ Остальные позиции занимают данные.

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

Почему проверки указывают точное место

Хитрость в том, что позиции пронумерованы в двоичной системе, а каждый контрольный бит отвечает за позиции, у которых в номере стоит единица в определённом разряде. Если ошибся бит на позиции $5$, то $5 = 101_2$ — сработают проверки разрядов $1$ и $4$, давая в сумме ровно $1 + 4 = 5$. Координаты ошибки складываются автоматически.

Геометрия исправления: расстояние между кодами

Глубинная причина, почему это работает, — понятие расстояния Хэмминга: число позиций, в которых два кода различаются. Например, $1011$ и $1110$ различаются в двух позициях, расстояние равно $2$.

Если все допустимые кодовые слова отстоят друг от друга минимум на $3$, то одиночная ошибка сдвигает слово только на $1$ шаг — и оно по-прежнему ближе всего к исходному коду, чем к любому соседнему. Получатель просто выбирает ближайший правильный код. Чем больше минимальное расстояние, тем больше ошибок можно исправить:

$$t = \left\lfloor \frac{d - 1}{2} \right\rfloor$$

где $d$ — минимальное расстояние, а $t$ — число исправимых ошибок.

Где это спасает данные прямо сейчас

Оперативная память серверов (ECC-память) исправляет одиночные сбои на лету. QR-коды читаются, даже если часть закрашена. Сигналы из дальнего космоса, искажённые шумом за миллиарды километров, восстанавливаются благодаря потомкам идей Хэмминга. Спутники, жёсткие диски, мобильная связь — все они тихо чинят данные, пока вы об этом даже не подозреваете.

Цена надёжности

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