Чередование блоков в QR-коде (Interleaving)

Что такое чередование блоков

Чередование (interleaving) — предпоследний этап сборки QR-кода по стандарту ISO/IEC 18004. Кодовые слова данных и кодовые слова коррекции, посчитанные для разных блоков Рида — Соломона, не идут в матрицу подряд блок за блоком, а перемешиваются в один общий поток. И уже этот перемешанный поток раскладывается по модулям.

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

Зачем разбивать данные на блоки

Рид — Соломон исправляет ограниченное число повреждённых байтов в блоке: если к блоку добавлено 2t проверочных кодовых слов, гарантированно чинится t произвольных ошибок. В QR максимум — 30 кодовых слов коррекции на блок, то есть 15 испорченных байтов. Дальше алгоритм разводит руками.

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

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

Как устроен порядок кодовых слов

Блоки внутри одной версии и уровня коррекции бывают двух длин, отличающихся ровно на одно кодовое слово. Например, версия 5 с уровнем Q даёт 62 кодовых слова данных: два блока по 15 и два по 16, плюс по 18 кодовых слов коррекции на каждый блок.

Дальше сборка идёт так:

• берётся первое кодовое слово первого блока, затем первое второго, третьего, четвёртого;
• затем вторые кодовые слова всех блоков, третьи и так далее;
• когда короткие блоки заканчиваются, их просто пропускают — «хвосты» длинных блоков дописываются следом;
• после всех данных тем же способом чередуются кодовые слова коррекции: первое каждого блока, второе каждого блока и так до конца.

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

Что это даёт на практике

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

Именно поэтому логотип в центре кода работает не как «дырка в данных», а как равномерная потеря по всем блокам. Тот же механизм спасает срезанный угол наклейки, потёртость на упаковке и каплю жира на меню. Разбор сценариев — в термине восстановление ошибок QR.

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

Когда чередования нет

У маленьких кодов блок один, и перемешивать нечего. Версии 1 и 2 при любом уровне коррекции состоят из единственного блока; у версии 3 один блок остаётся на уровнях L и M, а на Q и H их уже два. С ростом версии число блоков увеличивается — и вместе с ним устойчивость к сплошным повреждениям.

Практический вывод для мелкой печати: код версии 1 физически не умеет размазывать повреждение. На грязном носителе или нестабильной печати короткая ссылка в версии 1 может оказаться менее живучей, чем она же в версии 3–5 при том же уровне коррекции.

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