Корректирующие коды: объяснение

Идеальных каналов не бывает. Космические лучи инвертируют биты в памяти, царапины стирают части диска, а радиосигналы затухают. Вместо того чтобы надеяться на лучшее, цифровые системы хитроумно добавляют избыточность, чтобы получатель мог понять, что было отправлено, даже если часть данных пришла с ошибками. Математика этих кодов, зародившаяся в конце 1940-х годов, незаметно защищает почти каждый бит, который мы храним или передаём.

Три пересекающихся круга с семью битами кодового слова Хэмминга; выделен круг, в котором не проходит проверка чётности
Три пересекающихся круга с семью битами кодового слова Хэмминга; выделен круг, в котором не проходит проверка чётности

Обнаружение ошибок с помощью чётности

Простейшая защита — один бит чётности: добавляется 1 или 0, чтобы общее число единиц было чётным. Если по пути один бит инвертируется, число становится нечётным, и получатель понимает, что что-то пошло не так. Чётность не может сказать, какой бит ошибочен, а две инверсии взаимно компенсируются и остаются незамеченными, но она дёшева и десятилетиями применялась в памяти и последовательных линиях связи. Однако обнаружить ошибку — это лишь полдела: затем данные нужно отправить заново.

Исправление повторением

Чтобы исправить ошибку, не запрашивая данные заново, получателю нужно столько избыточности, чтобы ошибку можно было перевесить голосованием. Если отправлять каждый бит трижды, 000 или 111, получатель может выбрать большинство: одна инверсия в тройке исправляется. Цена высока: три бита на каждый бит данных, а две инверсии в одной тройке всё равно побеждают. Вопрос, с которого началась теория кодирования, звучал так: можно ли сделать лучше?

Код Хэмминга

В 1947 году Ричард Хэмминг работал в Bell Labs на релейной вычислительной машине, которая считывала программы с перфокарт. Обнаружив ошибку на выходных, она просто останавливалась, и в понедельник Хэмминг находил впустую потраченные прогоны. Если машина может обнаружить ошибку, спросил он, почему она не может найти и исправить её? Его ответ, опубликованный в 1950 году, передаёт 4 бита данных как 7. Три бита чётности на позициях 1, 2 и 4 проверяют каждый свою пересекающуюся группу позиций, подобранную так, что любая одиночная ошибка нарушает уникальное сочетание проверок.

Синдром

Получатель заново вычисляет три проверки. Если все пройдены, слово принимается. Если некоторые не пройдены, то, записав не прошедшие проверки двоичными цифрами, со старшим разрядом для проверки 4, получают число от 1 до 7 — синдром, который в точности равен позиции инвертированного бита. Инвертировав его обратно, восстанавливают кодовое слово. Приём работает потому, что позиции пронумерованы так, что двоичная запись каждой перечисляет проверки, в которые она входит; именно поэтому код выглядит так аккуратно, если нарисовать его в виде трёх пересекающихся кругов.

Расстояние Хэмминга

Расстояние Хэмминга между двумя словами — это число позиций, в которых они различаются. В коде (7,4) любые два кодовых слова отстоят друг от друга как минимум на 3. Слово с одной ошибкой по-прежнему находится на расстоянии 1 от отправленного кодового слова и как минимум на расстоянии 2 от всех остальных, поэтому декодирование в ближайшее кодовое слово её исправляет. В общем случае код, кодовые слова которого отстоят друг от друга как минимум на d, обнаруживает d − 1 ошибок и исправляет (d − 1)/2 из них с округлением вниз. Добавление общего бита чётности увеличивает расстояние до 4, и получается расширенный код, который исправляет одну ошибку и обнаруживает две.

Предел Шеннона

В 1948 году, за два года до статьи Хэмминга, Клод Шеннон доказал поразительную теорему. У каждого канала с шумом есть пропускная способность, и данные можно передавать с любой скоростью ниже неё со сколь угодно малым числом ошибок, если использовать достаточно длинные коды; выше неё ошибок не избежать. Шеннон показал, что такие коды существуют, но не показал, как их построить. Поиск практичных кодов, близких к его пределу, занял полвека — от кодов Рида — Соломона в 1960 году до турбокодов в 1993 году и повторного открытия кодов с малой плотностью проверок на чётность.

Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.
Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.

Коды вокруг нас

Коды Рида — Соломона позволяют компакт-дискам играть несмотря на царапины, а QR-кодам — считываться, даже если повреждено до 30 % символа. Серверная память использует расширенные коды Хэмминга, чтобы исправлять одиночные инвертированные биты, вызванные космическими лучами. Снимки внешних планет с «Вояджера» защищались кодами Голея, а позже — кодами Рида — Соломона, а коды LDPC и полярные коды в 5G и Wi-Fi выжимают почти каждый бит, который допускает канал. Даже штрихкод на книге и последняя цифра номера банковского счёта — это простые коды, обнаруживающие ошибки.

Попробуйте сами

Откройте симулятор корректирующего кода, чтобы закодировать любые четыре бита данных кодом Хэмминга (7,4), инвертировать биты щелчком в кругах или в строке и посмотреть, как не прошедшие проверку круги и синдром указывают на ошибку, прежде чем декодер её исправит. Включите дополнительный бит чётности, чтобы увидеть обнаружение двойных ошибок, и отправьте сообщение через канал с шумом, чтобы сравнить, что приходит с кодом и без него.

Часто задаваемые вопросы

Чем обнаружение ошибок отличается от их исправления?

Обнаружение лишь сообщает получателю, что что-то не так, и ему приходится запрашивать данные заново; так работает бит чётности или контрольная сумма. Исправление позволяет получателю восстановить оригинал без запроса, для чего нужно больше избыточности. Системы, которые не могут запросить данные заново, например космический зонд в миллионах километров или DVD, полагаются на исправление.

Почему бы просто не отправлять всё дважды?

Две копии показывают, что ошибка произошла, но не показывают, какая копия верна, и при этом удваивают затраты. Три копии позволяют голосовать большинством, но утраивают затраты. Код Хэмминга исправляет одну ошибку на блок из семи битов, используя менее чем вдвое больше битов, а более длинные коды справляются гораздо лучше.

Кем был Ричард Хэмминг?

Американский математик (1915–1998), работавший в Манхэттенском проекте, а затем тридцать лет в Bell Labs. Помимо своих кодов, он известен окном Хэмминга в обработке сигналов, расстоянием Хэмминга и лекцией «You and Your Research» («Вы и ваше исследование»). В 1968 году он получил премию Тьюринга.

Может ли код исправить любое число ошибок?

Только при достаточной избыточности. Код может исправить до (d − 1)/2 ошибок на блок, где d — минимальное расстояние между кодовыми словами, а более длинные коды с большим числом проверочных битов достигают больших d. Окончательный предел задаёт теорема Шеннона: ни один код не может превзойти пропускную способность канала.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть симулятор корректирующего кода