Кодовое слово (codeword) в QR-коде
Кодовое слово — базовая единица данных QR-кода размером 8 бит. Из кодовых слов складывается и полезная нагрузка, и коррекция: Рид — Соломон восстанавливает именно их, а не отдельные модули.
Что такое кодовое слово
Кодовое слово (codeword) — базовая единица данных QR-кода. В QR Code Model 2, то есть в том формате, который печатают на чеках, упаковке и афишах, кодовое слово всегда равно 8 битам — одному байту. Битовый поток, полученный после кодирования текста, режется на восьмёрки, и дальше вся арифметика стандарта оперирует уже не битами и не модулями, а кодовыми словами.
Это принципиальный уровень абстракции. В кодовых словах считается ёмкость версии и деление на блоки, а коррекция Рида — Соломона восстанавливает целые кодовые слова, а не отдельные испорченные модули. Поэтому «код с уровнем H переживает 30 процентов повреждений» означает долю кодовых слов, а не долю площади.
Сколько кодовых слов в QR-коде
| Версия и уровень | Всего | Данные | Коррекция |
|---|---|---|---|
| 1-L (21 × 21) | 26 | 19 | 7 |
| 1-H | 26 | 9 | 17 |
| 40-L (177 × 177) | 3706 | 2956 | 750 |
| 40-H | 3706 | 1276 | 2430 |
Общее число кодовых слов зависит только от версии — это вся свободная площадь символа за вычетом функциональных узоров и служебных полей. А вот пропорция между данными и коррекцией задаётся уровнем: у версии 1-L под коррекцию уходит 7 кодовых слов из 26, то есть больше четверти, у 1-H — 17 из 26, почти две трети. Знакомые «7 процентов для L» и «30 процентов для H» — про другое: столько повреждённых кодовых слов уровень способен восстановить, а не столько отдано под избыточность. Отсюда и разница в ёмкости в два с половиной раза между L и H на одной и той же версии.
Блоки и чередование
Начиная с определённых версий поток данных не остаётся единым куском: стандарт ISO/IEC 18004 режет его на блоки, и каждый блок получает собственный набор кодовых слов коррекции. Версия 1 обходится одним блоком, крупные версии дробятся на десятки.
Смысл дробления — в характере повреждений. Reed-Solomon в одном блоке исправляет ограниченное число ошибочных кодовых слов: два кодовых слова коррекции на каждое восстановленное с неизвестной позицией и одно — на стирание, когда позиция дефекта известна. Будь код одним большим блоком, кофейное пятно в углу выело бы весь запас. Данные режут на блоки и раскладывают в матрице вперемешку (interleaving), так что пятно бьёт по каждому блоку понемногу, и каждый чинит свою долю сам.
Терминатор, добивка и остаточные биты
Полезные данные редко занимают целое число кодовых слов. Пустоту заполняют по строгому ритуалу:
- После последних данных ставится терминатор — до четырёх нулевых бит.
- Поток добивается нулями до границы кодового слова, то есть до кратности восьми битам.
- Оставшиеся кодовые слова данных заполняются двумя чередующимися байтами-заполнителями: 11101100 и 00010001.
- После укладки всех кодовых слов в матрицу может остаться 0, 3, 4 или 7 остаточных бит — в зависимости от версии. Они не образуют кодового слова и просто заполняются нулями.
Чередование двух разных байтов-заполнителей вместо сплошных нулей — не прихоть, а борьба за равномерный рисунок модулей: длинный ряд одинаковых байт дал бы регулярный узор, который штрафные правила выбора маски стараются разбить. Увидеть это на практике просто: наберите адрес в конструкторе QR-кодов, добавляя по символу, и заметите момент, когда версия скакнёт на следующую.
Связанные концепции
- Reed-Solomon — алгоритм, оперирующий кодовыми словами как элементами поля GF(256).
- Ёмкость данных — прямое следствие числа кодовых слов данных в версии.
- Модуль QR — один модуль равен одному биту, восемь модулей области данных дают кодовое слово.
Частые вопросы
Сколько бит в одном кодовом слове QR-кода?
Восемь бит, то есть один байт — для всех версий QR Code Model 2 от 1 до 40. Исключение есть только у младшего родственника: в Micro QR символах типов M1 и M3 последнее кодовое слово данных укорочено до четырёх бит. В обычном QR-коде, который вы видите на чеках и афишах, любое кодовое слово — ровно восемь бит, и вся арифметика стандарта на этом построена.
Чем кодовое слово отличается от модуля?
Модуль — это один чёрно-белый квадратик матрицы, физическая единица изображения. Кодовое слово — логическая единица данных из восьми бит. В области данных один модуль несёт один бит, так что кодовое слово занимает восемь модулей, уложенных змейкой по правилам стандарта. При этом модули функциональных узоров — поисковых, временных дорожек, узоров выравнивания — вообще не входят ни в какие кодовые слова.
Сколько кодовых слов исправляет коррекция ошибок?
Правило простое: на восстановление одного кодового слова с неизвестной позицией уходит два кодовых слова коррекции, на стирание с известной позицией — одно. Значит, блок с 20 кодовыми словами коррекции вытянет до 10 ошибочных кодовых слов. Реальные декодеры чуть консервативнее: часть запаса резервируется под проверку, поэтому заявленные «до 30 процентов при уровне H» — это верхняя граница, а не гарантия при любом дефекте.
Зачем данные делят на блоки?
Чтобы локальное повреждение не съело весь запас коррекции. Reed-Solomon работает внутри блока и ограничен его собственными кодовыми словами коррекции. Если бы крупный код был одним блоком, царапина в углу исчерпала бы лимит целиком. Стандарт режет данные на блоки и укладывает их в матрицу вперемешку, так что физически соседние модули принадлежат разным блокам — и каждый чинит свою долю ущерба независимо.
Что за байты 11101100 и 00010001 в конце потока?
Это байты-заполнители (pad codewords), которыми добивают остаток области данных, когда полезное содержимое короче ёмкости версии. Они идут по очереди: 11101100, затем 00010001, снова 11101100 и так далее. Декодер их просто отбрасывает — до них он всё равно не доходит, потому что длина полезной части указана в заголовке потока. Чередование двух разных значений вместо нулей помогает получить более равномерный рисунок модулей.