Как данные сами исправляют свои ошибки

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

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

Любая передача данных грязна. Радиосигнал ловит помехи, диск стареет, провод наводит шум. Биты иногда переворачиваются: был ноль — стала единица. Если бы мы передавали данные «как есть», ни один файл нельзя было бы доверять. Спасает избыточность — добавочные биты, которые сами по себе не несут смысла, но позволяют проверить и починить остальное.

Самый простой страж: бит чётности

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

Но у бита чётности есть слабости. Он замечает только нечётное число ошибок (две перевернувшиеся единицы он пропустит) и не говорит, где именно сбой — только что он есть. Для серьёзной защиты этого мало.

Контрольная сумма: проверка для больших данных

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

Код Хэмминга: найти и обезвредить

А можно ли не просто заметить ошибку, но и точно указать сломанный бит — чтобы перевернуть его обратно? Можно. В 1950-м Ричард Хэмминг придумал код, который это умеет. Идея: расставить несколько битов чётности так, чтобы каждый отвечал за свою группу позиций. Группы пересекаются хитрым образом — и если один бит перевернулся, набор «провалившихся» проверок складывается в число, указывающее точный адрес ошибки.

Звучит как фокус, но это чистая арифметика на чётностях. Память серверов нередко использует похожий механизм (ECC-память): если космическая частица перевернёт бит в микросхеме, ошибка исправляется на лету, и программа даже не узнает о происшествии.

Когда ошибок много: коды для дисков и космоса

Если повреждения большие — целая царапина на диске или потеря пакетов на линии связи, — применяют более мощные коды (например, коды Рида-Соломона). Они умеют восстанавливать сразу множество подряд испорченных байтов и работают на CD, DVD, в QR-кодах и в дальней космической связи.

Логика всегда одна: чем больше избыточности добавлено заранее, тем сильнее повреждение можно пережить без переспроса. Зонд у границ Солнечной системы не может попросить «повторите, пожалуйста» — сигнал идёт часами. Поэтому он отправляет данные с такой избыточностью, что даже изрядно потрёпанный помехами поток на Земле собирается обратно без единой ошибки. Немного лишних битов сегодня — спасённая информация завтра.