Перемежение кодовых слов (Interleaving)
Перемежение — чередование кодовых слов разных блоков в QR вместо их последовательного размещения; локальное повреждение рассыпается по блокам, и Рид-Соломон восстанавливает каждый.
Зачем чередовать кодовые слова
Начиная с определённой ёмкости, QR-код делит данные не на один, а на несколько блоков — у каждого свой набор проверочных байтов Рид-Соломона. Рид-Соломон восстанавливает блок, только если число повреждённых байтов в нём не превышает предела. Если бы блоки лежали в коде подряд, любое компактное пятно грязи или царапина выбили бы много байтов одного блока сразу — и он бы не восстановился, хотя соседние остались бы целыми.
Как устроено чередование
Перемежение решает это перестановкой. Сначала в поток выкладываются первые кодовые слова всех блоков данных, затем вторые, затем третьи и так далее; следом тем же образом чередуются проверочные байты всех блоков. Порядок задан стандартом ISO/IEC 18004 и одинаков у кодера и декодера, так что при чтении поток раскладывается обратно по блокам однозначно. В версиях с одним блоком перемежать нечего — там байты идут подряд.
Что это даёт при повреждении
После перемежения соседние в коде байты принадлежат разным блокам. Локальное повреждение — капля, блик, наклейка — рассыпается по нескольким блокам, и на каждый приходится лишь несколько испорченных байтов, в пределах исправляемого. Именно перемежение вместе с уровнем коррекции и позволяет коду переживать частичные загрязнения. Собрать многоблочный код и оценить его стойкость можно в генераторе QR.
Частые вопросы
Зачем в QR-коде перемежают кодовые слова?
Чтобы локальное повреждение не выбило целиком один блок данных. Если байты блоков лежат подряд, царапина или пятно уничтожат много байтов одного блока сразу, и Рид-Соломон его не восстановит. Перемежение распределяет повреждение по всем блокам, оставляя каждый в пределах исправляемого.
В каких QR-кодах есть перемежение?
Только в версиях, где данные делятся на два и более блока — это коды средних и больших версий, число блоков зависит и от уровня коррекции. В маленьких кодах с одним блоком перемежать нечего: кодовые слова данных и коррекции идут в них подряд, как есть.
Как декодер восстанавливает исходный порядок?
Порядок чередования жёстко задан стандартом ISO/IEC 18004 и известен обеим сторонам. Декодер знает число блоков и их размеры для данной версии и уровня коррекции, поэтому раскладывает считанный поток обратно по блокам однозначно, без всякой служебной метки внутри данных.
Перемежаются ли байты коррекции тоже?
Да. Сначала чередуются кодовые слова данных всех блоков, затем тем же порядком — проверочные байты Рид-Соломона всех блоков. Так и данные, и их избыточность оказываются равномерно размазаны по коду, что и обеспечивает устойчивость к пятнам и царапинам.