Помехоустойчивое кодирование

Задача и базовые величины

Любой реальный канал искажает данные: радиоэфир добавляет шум, печатная этикетка собирает грязь и царапины, ячейка памяти теряет заряд. Помехоустойчивое кодирование решает эту задачу не повышением качества канала, а добавлением к сообщению рассчитанной избыточности. Из k информационных символов кодер строит n символов кодового слова; отношение k/n называют скоростью кода. Скорость 1/2 означает, что половина передаваемого объёма — проверочные данные.

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

Отдельно различают ошибки и стирания. Ошибка — символ прочитан неверно, но позиция неизвестна. Стирание — известно, что символ утрачен, но неизвестно его значение: так выглядит залитый или закрытый участок печатного кода. Стирание вдвое дешевле: код с расстоянием d исправляет d − 1 стираний против ⌊(d − 1)/2⌋ ошибок. Именно поэтому декодеры двумерных кодов стараются пометить нечитаемые области, а не гадать их содержимое.

Теоретическую границу задала теорема Шеннона 1948 года: у канала есть пропускная способность, ниже которой существуют коды со сколь угодно малой вероятностью ошибки. Теорема не подсказывает, как построить такой код, — практическое приближение к границе заняло полвека и завершилось турбо-кодами и кодами с малой плотностью проверок.

Семейства кодов

Блочные коды обрабатывают данные фиксированными порциями. К ним относятся коды Хэмминга, исправляющие одну ошибку на блок и применяемые в оперативной памяти ECC; коды БЧХ, которыми в QR защищены служебные поля формата и версии; и коды Рида — Соломона, работающие не с битами, а с символами поля Галуа — как правило, с байтами.

Свойство Рида — Соломона, определившее его судьбу в оптических носителях и печатных кодах: искажение любого числа бит внутри байта считается одной ошибкой символа. Пакетное повреждение — царапина, пятно, наклейка — задевает подряд идущие байты, и код тратит на них ровно столько исправляющей способности, сколько байтов задето. Формально код Рида — Соломона с 2t проверочными символами исправляет t ошибочных символов или 2t стираний.

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

Отдельный приём, не являющийся кодом, — перемежение. Символы кодовых слов раскладываются по символу вперемежку, так что физически соседние элементы носителя принадлежат разным блокам. Пакетное повреждение размазывается по многим блокам, и каждый справляется своими силами. В QR-коде перемежение обязательно и работает вместе с блочным делением данных.

Как это устроено в QR-коде и штриховых кодах

QR-код использует коды Рида — Соломона над полем GF(256) и предлагает четыре уровня коррекции ошибок: L восстанавливает около 7% кодовых слов символа, M — 15%, Q — 25%, H — 30%. Данные и проверочные байты делятся на блоки, блоки перемежаются, поэтому потеря целого угла символа распределяется между несколькими независимыми блоками.

Служебная информация защищена иначе. Поле формата, где хранятся уровень коррекции и номер маски, кодируется кодом БЧХ (15, 5) и дополнительно накладывается на фиксированную маску, чтобы исключить полностью нулевую комбинацию; в символе оно продублировано дважды. Логика та же, что и в остальном коде: без корректного чтения служебных пяти бит декодировать данные невозможно, поэтому им дана избыточность выше средней.

DataMatrix в современной редакции ECC 200 построен на тех же кодах Рида — Соломона, PDF417 предлагает девять уровней коррекции, Aztec Code позволяет задавать долю проверочных данных от 5 до 95%. А вот линейные штриховые коды корректирующей способности лишены вовсе: у EAN-13 есть только контрольная цифра, то есть обнаружение без восстановления. Причина историческая и физическая — в узкой полосе штрихов негде разместить проверочные символы, а сканер на кассе всегда может провести повторный проход.

Цена избыточности и выбор уровня

Избыточность не бесплатна: она вытесняет полезные данные. Один и тот же адрес при уровне H требует символа большей версии, чем при L, — модулей больше, каждый модуль при фиксированном физическом размере мельче, а значит, растёт требование к разрешению печати и уменьшается дистанция уверенного считывания. Практический баланс выглядит так:

• L — экран, презентация, чистая поверхность, короткая ссылка; максимум ёмкости при минимуме модулей.
• M — рабочий выбор по умолчанию для печати на бумаге и картоне.
• Q — код с логотипом в центре, наклейки на витрине, полиграфия с риском загрязнения.
• H — промышленная маркировка, наружное размещение, гравировка по металлу, крупный логотип.

Распространённое заблуждение — что уровень H всегда лучше. Он повышает не только устойчивость, но и плотность символа при том же физическом размере, а мелкие модули хуже читаются дешёвой камерой. Если содержимое длинное, разумнее сократить сам payload: перенести длинный адрес на короткую ссылку и оставить уровень M. Влияние размера модуля на дистанцию считывания разобрано в материале про размер QR-кода для печати, а типовые причины отказов — в статье о том, почему QR-код не сканируется.

Частые вопросы

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

Целями и моделью угрозы. Помехоустойчивый код борется со случайными искажениями и добавляет избыточность, чтобы данные пережили шум; содержимое при этом остаётся открытым и легко читается декодером. Шифрование защищает от осмысленного противника и, наоборот, стремится к записи, неотличимой от случайной. Задачи ортогональны: зашифрованные данные всё равно кодируют помехоустойчиво, иначе один потерянный бит испортит расшифровку.

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

Можно, и такая схема работает: голосование по большинству исправляет одиночную ошибку. Но её скорость равна 1/3 — на каждый полезный символ приходится два проверочных. Код Рида — Соломона с той же долей избыточности исправляет не одну ошибку на символ, а целые пакеты повреждений в длинном блоке. Повторение проигрывает по эффективности примерно на порядок, поэтому применяется только в предельно простых схемах.

Всегда ли стоит выбирать уровень коррекции H?

Нет. Уровень H тратит на проверочные данные около 30% ёмкости, из-за чего то же содержимое требует версии символа выше — модулей становится больше, а при неизменных габаритах печати каждый модуль мельче. Мелкий модуль хуже читается камерой с расстояния и требовательнее к качеству печати. Для чистой бумажной поверхности достаточно M, а H оправдан при логотипе, гравировке или уличном размещении.

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

Стирание — символ, о котором известно, что он утрачен: позиция дефекта видна декодеру, неизвестно только значение. Ошибка — символ прочитан неверно, и декодер сначала должен вычислить, где именно. Локализация стоит половины исправляющей способности, поэтому код Рида — Соломона с 2t проверочными символами восстанавливает t ошибок либо вдвое больше — 2t стираний.

Почему в обычном штрих-коде нет коррекции ошибок?

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