Коды Хэмминга: самокорректирующиеся данные

Представьте: научные данные с межпланетной станции летят к Земле несколько часов, и по дороге в них портится один-единственный бит — частица от солнечной вспышки переворачивает ноль в единицу. Переспросить нельзя, повторная передача стоит месяцев. Данные обязаны чинить себя сами. Эту задачу решил Ричард Хэмминг в Bell Labs: он предложил код, который не просто замечает порчу, а называет адрес битого бита. Тот же код сегодня охраняет оперативную память серверов (маркировка ECC) и микросхемы, работающие под радиацией.

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

Расстояние Хэмминга: насколько различаются слова#

Двоичное слово — строка из нулей и единиц фиксированной длины. Расстояние Хэмминга между словами — число позиций, в которых они различаются: $d(1011,0101)=3$, потому что первые три позиции не совпали, а четвёртая совпала. Эквивалентный способ: посчитайте число единиц в поразрядном XOR — получится то же самое. Это расстояние ведёт себя как настоящая метрика: неотрицательно, симметрично и подчиняется неравенству треугольника, так что слово не может быть одновременно близким к двум далёким друг от друга словам.

Передаётся не произвольная строка, а кодовое слово из заранее согласованного набора. Ошибка веса $r$ уводит слово на расстояние $r$ от оригинала. Вся механика обнаружения и исправления живёт в расстояниях. Пусть ближайшие кодовые слова отстоят друг от друга на $d_{\min }$. Тогда шары радиуса $r$ вокруг слов не задевают друг друга при $d_{\min }\ge 2r+1$ — и любая принятая строка внутри шара однозначно указывает на свой центр, ошибку можно исправить. Для обнаружения $r$ ошибок хватает слабее условия $d_{\min }\ge r+1$: ошибка такого веса не способна превратить одно кодовое слово в другое.

Бит чётности из урока об основах кодирования — код с $d_{\min }=2$: одиночную ошибку он видит, но локализовать не может, ведь любая из $n$ позиций даёт один и тот же симптом. Коррекция начинается с $d_{\min }=3$ — именно к этому порогу идёт код Хэмминга.

Простейший исправляющий код известен со времён телеграфа — утроение: ноль отправляем как $000$, единицу как $111$. Расстояние между кодовыми словами $d_{\min }=3$: после одиночной ошибки два «правильных» бита против одного, и мажоритарное голосование восстанавливает исходный бит. Код работает, но дорог: из трёх битов полезен один, скорость $1/3$. Хэмминг искал способ купить те же три единицы расстояния дешевле — и нашёл: три проверочных бита на четыре информационных.

Почему проверочные биты стоят на степенях двойки#

Схема Хэмминга для блока из 7 бит (код $(7,4)$): 4 бита данных и 3 проверочных. Проверочные занимают позиции $1,2,4$ — степени двойки, данные раскладываются по оставшимся местам:

Каждый проверочный бит делает свою группу чётной: сумма единиц по группе должна быть чётной (равна нулю по модулю 2):

• $p_1$ проверяет позиции $1,3,5,7$ — номера с единицей в младшем двоичном разряде
• $p_2$ проверяет позиции $2,3,6,7$ — номера с единицей во втором разряде
• $p_4$ проверяет позиции $4,5,6,7$ — номера с единицей в третьем разряде

Правило выглядит случайным, а устроено глубоко: запишите номер позиции в двоичной системе — бит $p_1$ отвечает за младший разряд номера, $p_2$ за второй, $p_4$ за третий. Позиция $5=101_2$ попадает в группы $p_1$ и $p_4$; позиция $6=110_2$ — в группы $p_2$ и $p_4$. Из-за этого номер испорченного бита кодируется сам собой: если чётность нарушили группы $p_1$ и $p_4$, двоичное число $101$ — готовый адрес ошибки. Три проверки дают $2^3=8$ исходов: ноль означает «всё чисто», оставшиеся семь покрывают все позиции блока. Впритык, и это не совпадение, а конструкция кода: проверок $r$ должно хватать на $n+1$ исходов, отсюда требование $2^r\ge n+1$.

Общая сборка: $r$ проверок держат блок длины $n=2^r-1$, из которых данные занимают $n-r$ позиций. Проверки встают на $1,2,4,\dots ,2^{r-1}$ — каждое место с единственной единицей в двоичной записи, данные стекаются на остальные. Хотите защитить 11 битов — берите $r=4$: $2^4=16\ge 15+1$, выходит код $(15,11)$ с проверками на позициях 1, 2, 4, 8. Защитить 26 — $r=5$, код $(31,26)$. Чем длиннее блок, тем выше скорость, а гарантия та же: одна ошибка на блок.

Полный пример: от битов данных до исправленной ошибки#

Три проверочных бита купили способность исправлять любую одиночную ошибку в семи. Обратная сторона: две ошибки код вводит в заблуждение. Переверните биты 2 и 5 — синдром сложится как $2\oplus 5=7$, потому что номера-«подписи» ошибок складываются по модулю 2. Декодер «починит» седьмой бит и испортит слово окончательно: расстояние 3 обещало двойные ошибки лишь обнаруживать, без коррекции. Поэтому в серверной памяти код Хэмминга расширяют ещё одним битом общей чётности до $d_{\min }=4$: одиночная ошибка исправляется, двойная обнаруживается, схема носит имя SECDED.

Тренировочный второй раунд: испорчен бит 6, на приёмнике слово $0110001$. Группа $p_1$ чиста, группы $p_2$ и $p_4$ провалились — синдром $110_2=6$. Прогоните группы вручную и убедитесь: декодер вернул слово без единого запроса к отправителю.

Сколько стоит защита: расстояние, граница, избыточность#

Минимальное расстояние кода Хэмминга равно 3, и это проверяется перебором: код линеен — XOR двух кодовых слов снова кодовое слово, ведь суммы, чётные по каждой группе, дают чётные суммы по той же группе, — а среди 15 ненулевых слов нет ни одного веса меньше 3. Например, слову данных $1000$ отвечают проверки $p_1=1$, $p_2=1$, $p_4=0$: кодовое слово $1110000$ весит ровно 3. Любая пара кодовых слов различается минимум в трёх позициях — отсюда и таблица выше: две ошибки обнаруживаются, одна исправляется.

Декодер собирается из трёх XOR-деревьев — по одному на группу — и дешифратора, переводящего синдром в номер бита. Вся проверка — три слоя логики глубиной в пару элементов: память с ECC чинит слово быстрее, чем процессор успевает его запросить. Синдром читается мгновенно: единицы в $s_1$ и $s_4$ при чистой $s_2$ — двоичное $101$, бит 5; единица только в $s_2$ — двоичное $010$, бит 2.

Граница Хэмминга оценивает предел экономности. Шар радиуса 1 вокруг слова длины 7 содержит $1+7=8$ строк: само слово плюс семь его соседей. Кодовых слов $2^4=16$, и их шары занимают $16\cdot 8=128=2^7$ строк — всё пространство заполнено без зазоров и перекрытий. Код совершенный: каждая 7-битная строка либо кодовое слово, либо отстоит на один флип ровно от одного кодового слова. Совершенных кодов немного — $(7,4)$, $(15,11)$, $(31,26)$ при $n=2^r-1$, и все они исправляют ровно одну ошибку на блок.

Теперь цена. Три проверочных бита на четыре информационных: скорость кода $4/7\approx 0,57$ — почти половина пропускной способности уходит на страховку. У кода $(15,11)$ скорость уже $11/15\approx 0,73$, у $(31,26)$ — около $0,84$: избыточность тает с ростом блока. Но растёт и уязвимость: чем длиннее блок, тем вероятнее в нём вторая ошибка, которую код не переживёт. Выбор длины — торг между экономией и надёжностью, а прикидки вроде «сколько строк покроют шары» — прямое приложение счёта из урока про перестановки, размещения и сочетания.

Геометрия здесь красивая: все 7-битные слова — вершины семимерного куба, рёбра соединяют слова на расстоянии 1 (анатомию графов напоминает урок про основы графов). Код Хэмминга — упаковка 16 непересекающихся кубиков радиуса 1 в куб из $2^7$ вершин. Аппарат XOR-проверок вырос из булевой алгебры; операции с таблицами истинности собраны в статье таблица истинности. Упаковка шаров в кубе — наглядная картинка того, почему граница Хэмминга вообще работает: пустот нет, двойных соседей нет. Закрепить руки — в тренажёре по комбинаторике, там же пригодится счёт соседей куба.

• Расстояние Хэмминга — число различающихся позиций; обнаружение при $d_{\min }\ge r+1$, исправление при $d_{\min }\ge 2r+1$
• Проверки на степенях двойки покрывают позиции по разрядам номера; синдром — готовый двоичный адрес ошибки
• Код (7,4): $d_{\min }=3$, скорость $4/7$, код совершенный: $16\cdot 8=128=2^7$
• Двойные ошибки только обнаруживаются; для их коррекции нужно расстояние 5 — например, коды БЧХ