Как работает QR-код: структура матрицы, кодирование и коррекция ошибок

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

Что описывает стандарт ISO/IEC 18004

QR-код придумали в 1994 году в японской Denso — производителе автокомпонентов, связанном с группой Toyota; разработку вело подразделение, ставшее позже компанией Denso Wave. Задача цеховая: маркировать автозапчасти на конвейере. Линейный штрихкод там не справлялся: данных мало, читается только под правильным углом, а сканировать нужно было быстро и с любой стороны. Название Quick Response как раз про скорость распознавания.

Через несколько лет описание кода стало международным стандартом ISO/IEC 18004: первая редакция вышла в 2000 году и с тех пор несколько раз пересматривалась. Стандарт задаёт всё — геометрию служебных узоров с точностью до модуля, набор допустимых размеров, алгоритм кодирования, схему коррекции ошибок, правила маскирования, требования к контрасту и ширине пустого поля. Поэтому код, сгенерированный любым сервисом, читается любым сканером: обе стороны опираются на один документ.

Denso Wave владеет патентами на QR-код, но не требует отчислений за использование стандарта, оставив за собой только торговую марку QR Code. Открытая спецификация плюс защищённое имя — эта связка и сделала код повсеместным. Описаны в стандарте две разновидности: обычный QR (Model 2 — квадрат с тремя «глазами») и Micro QR с одним поисковым узором для совсем тесных мест. Дальше речь про обычный QR.

Модуль, матрица и что вообще считается «квадратиком»

Базовая единица QR-кода называется модулем. Это один квадратик сетки: тёмный — логическая единица, светлый — ноль. Никакого «полутона» не бывает, декодер приводит картинку к чёрно-белому виду ещё до разбора.

Модули собраны в квадратную матрицу. Размер матрицы не произвольный: он задаётся номером версии по формуле «сторона = 17 + 4 × версия». Версия 1 — это 21×21 модуль, версия 2 — 25×25, версия 10 — 57×57, версия 40 — 177×177. Промежуточных размеров не существует: если данные не влезли в 25×25, генератор берёт следующую ступень 29×29, и код заметно подрастает.

Модуль — понятие логическое, а не физическое: на этикетке он может быть 0,4 мм, на билборде — 4 см, важно лишь чтобы сканер его различил. Отсюда следствие, о котором забывают: чем длиннее содержимое, тем больше модулей в матрице, а при неизменном физическом размере кода каждый модуль мельчает. Длинная ссылка в QR — это не «много букв», это физически более мелкая сетка.

Карта матрицы: где данные, а где служебное

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

К функциональным относятся:

• Поисковые узоры — три крупных «глаза» 7×7 модулей в трёх углах;
• Разделители — светлая рамка шириной один модуль вокруг каждого поискового узора;
• Синхронизирующие дорожки — чередующаяся линия тёмных и светлых модулей между поисковыми узорами;
• Выравнивающие узоры — квадратики 5×5, появляются начиная со второй версии;
• Тихая зона — пустое поле вокруг всей матрицы.

Отдельно стоят два служебных поля: информация о формате (уровень коррекции и номер маски) и информация о версии для крупных кодов. Плюс один вечно тёмный модуль-маркер на координатах (4 × версия + 9, 8) — в любом валидном QR он всегда чёрный.

Всё остальное — рабочая площадь: 26 кодовых слов по 8 бит у версии 1 и 3706 у версии 40. Часть уйдёт на данные, часть на коррекцию, пропорцию задаёт выбранный уровень.

Поисковые узоры: как камера вообще находит код

Три квадрата в углах — это поисковые узоры (finder patterns). Каждый устроен одинаково: тёмный квадрат 3×3 в центре, вокруг него светлое кольцо толщиной в модуль, вокруг — тёмное кольцо толщиной в модуль. Итого 7×7 модулей.

Хитрость в пропорциях. Любая прямая через центр такого узора — горизонтальная, вертикальная, диагональная — пересекает полосы в соотношении 1:1:3:1:1 (тёмное-светлое-тёмное-светлое-тёмное). Соотношение сохраняется при любом повороте и почти при любом наклоне, поэтому декодер просто сканирует изображение строками и ищет эту сигнатуру — операция дешёвая, её можно гонять десятки раз в секунду на слабом процессоре.

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

Вокруг каждого узора обязателен разделитель — светлая полоса шириной один модуль со стороны данных. Без неё тёмные модули содержимого примыкают к «глазу» вплотную, ломают соотношение 1:1:3:1:1 и делают узор ненаходимым. Отсюда и беда дизайнерских QR с «залитыми» углами: на дешёвых сканерах они отваливаются.

Синхронизирующие дорожки и выравнивающие узоры

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

Шаг сетки задаёт синхронизирующая дорожка (timing pattern) — строка и столбец с шестым индексом, соединяющие поисковые узоры, где модули строго чередуются тёмный-светлый-тёмный-светлый. Декодер считает переходы и получает и шаг, и число модулей в стороне, то есть определяет версию, ещё не читая служебных полей.

С искажениями борются выравнивающие узоры (alignment patterns) — квадратики 5×5: тёмный модуль в центре, светлое кольцо, тёмное кольцо. В версии 1 их нет, в версиях со 2-й по 6-ю он один, дальше количество растёт ступенями: 6 штук с версии 7, 13 с версии 14, 22 с версии 21, 33 с версии 28 и 46 с версии 35. Координаты центров жёстко прописаны в стандарте, генератор не выбирает их сам.

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

Тихая зона: пустота, которая часть кода

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

Причина в той же сигнатуре 1:1:3:1:1: последняя светлая полоса соотношения у углового узора — как раз внешняя пустота. Если вплотную к коду идёт тёмный фон, текст или рамка, сигнатура ломается и поисковый узор не находится. Классический провал — QR, вставленный впритык в цветной блок макета или обрезанный «в край» при печати. Четыре модуля — минимум, а не рекомендация; на практике берут пять-шесть: стоит это почти ничего, а нечитаемых сканов заметно меньше.

Версии 1-40: как объём данных задаёт размер

Версия QR-кода — это его размерная ступень. Всего их сорок: от 21×21 модуля до 177×177. Генератор подбирает минимальную версию, в которую влезает содержимое при выбранном уровне коррекции, — и увеличивает её, если не влезло.

Полезной ёмкости достаётся не всё: часть кодовых слов уходит на проверочные байты. Крайние точки диапазона такие. Версия 1 с уровнем L вмещает 41 цифру, 25 буквенно-цифровых символов или 17 байт. Версия 40 с тем же уровнем — 7089 цифр, 4296 буквенно-цифровых символов, 2953 байта или 1817 иероглифов. Поднимите коррекцию до максимума — и версия 40 удержит уже 3057 цифр или 1273 байта, почти вдвое меньше.

Отдельно стоит запомнить границу версии 7: начиная с неё в код добавляется поле информации о версии — 18 бит в двух копиях. До седьмой версии его нет, размер там надёжно берётся из синхронизирующей дорожки, и тратить площадь незачем.

Если данные не влезают даже в версию 40, стандарт предлагает структурированное присоединение (structured append): содержимое режется и распределяется между несколькими символами, до шестнадцати. Каждый несёт заголовок с номером части и контрольной суммой набора, декодер склеивает их в правильном порядке. Встречается редко — почти всегда проще положить в QR короткую ссылку.

Четыре режима кодирования: цифры, буквы, байты, иероглифы

Хранить любой текст просто как последовательность байтов было бы расточительно, поэтому стандарт определяет четыре основных режима — каждый со своей плотностью упаковки.

• Числовой. Только цифры 0-9. Символы группируются по три и кодируются десятью битами, то есть 3,33 бита на цифру. Хвост из двух цифр занимает 7 бит, из одной — 4. Самый плотный режим.
• Буквенно-цифровой. Алфавит из 45 знаков: цифры, заглавные латинские буквы и девять символов — пробел, знак доллара, процент, звёздочка, плюс, минус, точка, слэш, двоеточие. Символы кодируются парами по 11 бит, то есть 5,5 бита на знак; одиночный хвост — 6 бит. Строчных букв и кириллицы здесь нет.
• Байтовый. Восемь бит на символ, по умолчанию кодировка ISO 8859-1. Универсальный режим: в него попадает всё, что не уложилось в предыдущие два, — русский текст, строчные буквы, произвольные бинарные данные.
• Кандзи. Японские иероглифы в кодировке Shift JIS упаковываются в 13 бит вместо 16, которые ушли бы в байтовом режиме. Ради этого режима код когда-то и создавался.

Есть и служебные режимы: ECI (Extended Channel Interpretation) объявляет декодеру нестандартную кодировку вроде UTF-8, без которого кириллица в байтовом режиме читается корректно далеко не везде, а FNC1 помечает данные как структурированные по правилам GS1 — это товарные и логистические коды.

Режимы к тому же можно смешивать внутри одного символа. Строку «HTTPS://EXAMPLE.COM/ORDER/8891» умный генератор разложит на буквенно-цифровой сегмент и числовой хвост, сэкономив десятки бит; каждый сегмент получает свой индикатор режима и свой счётчик длины.

Как текст превращается в битовый поток

Сборка идёт по строгой последовательности. Сначала четыре бита индикатора режима: 0001 — числовой, 0010 — буквенно-цифровой, 0100 — байтовый, 1000 — кандзи. Затем счётчик количества символов, длина которого зависит от режима и версии: для байтового это 8 бит в версиях 1-9 и 16 начиная с десятой, для числового — 10, 12 или 14 бит.

Дальше собственно данные по правилам режима, за ними терминатор — до четырёх нулевых битов, отмечающих конец полезной информации. Если результат не кратен восьми, поток дополняется нулями до целого числа байтов. Оставшееся до нормы место забивается чередующимися байтами 11101100 и 00010001 (в шестнадцатеричном виде EC и 11): значения выбраны не случайно, их чередование даёт достаточно «шумную» картинку без крупных однотонных пятен, которые мешают маскированию.

Именно поэтому два QR с почти одинаковым содержимым выглядят совершенно по-разному. Замена одного символа сдвигает весь битовый поток, меняет проверочные байты и часто приводит к выбору другой маски — код перестраивается целиком. Сравнивать QR «на глаз» бессмысленно.

Коррекция ошибок: четыре уровня и что стоит за процентами

Способность QR читаться порванным и заляпанным обеспечивает алгоритм Рида — Соломона — тот же класс кодов, что защищает данные на компакт-дисках и в спутниковой связи. К данным добавляются вычисленные проверочные байты; если часть кодовых слов при чтении оказалась неверной или нечитаемой, декодер по проверочным байтам восстанавливает исходное содержимое.

Математика работает в конечном поле Галуа GF(256): байт трактуется как элемент поля, сообщение — как многочлен, проверочные байты получаются остатком от деления на порождающий многочлен. Практическое свойство схемы: блок с n проверочными байтами гарантированно исправляет до n/2 ошибок в неизвестных позициях — и вдвое больше, если позиции повреждений известны заранее (модуль вовсе не удалось распознать).

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

Плата за надёжность — площадь. Проверочные байты занимают место данных, поэтому при переходе с L на H тот же текст требует более крупной версии. Версия 1 на уровне L держит 17 байт, на уровне H — только 7. Разница радикальная, и на коротких строках она особенно заметна.

Уровни коррекции указываются в служебном поле формата двумя битами, причём кодировка нелинейная: M — 00, L — 01, H — 10, Q — 11. Порядок битов не совпадает с интуитивным порядком «слабый-сильный», и это регулярно всплывает у тех, кто пишет свой декодер.

Блоки и чередование: почему пятно не убивает код

Если бы все проверочные байты защищали один сплошной кусок данных, локальное повреждение выбивало бы подряд идущие кодовые слова и быстро исчерпывало лимит исправлений. Стандарт решает это разбиением на блоки и перемешиванием.

Начиная с определённых версий поток данных режется на несколько блоков, для каждого блока независимо считаются свои проверочные байты. У крупных версий с высоким уровнем коррекции таких блоков десятки. Затем кодовые слова всех блоков чередуются: сначала первое слово каждого блока, потом второе каждого блока и так далее. Проверочные байты чередуются точно так же и укладываются после данных.

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

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

Маскирование: восемь узоров и штрафные баллы

Готовый битовый поток нельзя выкладывать в матрицу как есть. Реальные данные часто дают артефакты: длинные однотонные полосы, крупные квадратные пятна, а иногда — фрагменты, случайно повторяющие сигнатуру 1:1:3:1:1 поискового узора. Первое сбивает сэмплирование сетки, второе снижает локальный контраст, третье прямо путает декодер.

Лекарство — маска. Стандарт определяет восемь узоров, каждый задан формулой от координат модуля: маска 000 инвертирует модули с чётной суммой строки и столбца, маска 001 — все чётные строки, маска 010 — каждый третий столбец, маска 011 — диагонали с шагом три, остальные комбинированные вроде «(строка × столбец) mod 2 + (строка × столбец) mod 3 = 0». Применяется маска операцией XOR только к области кодирования: функциональные узоры и служебные поля не трогаются никогда, иначе поисковые узоры перестали бы быть узнаваемыми.

Выбор не произвольный. Генератор обязан построить все восемь вариантов, оценить каждый по четырём штрафным правилам и взять минимальную сумму:

• Правило 1 (вес 3). Серии из пяти и более одноцветных модулей подряд в строке или столбце. Штраф растёт с длиной серии.
• Правило 2 (вес 3). Каждый одноцветный блок 2×2 модуля.
• Правило 3 (вес 40). Появление в строке или столбце последовательности вида 1:1:3:1:1 с четырьмя светлыми модулями рядом — то есть ложного поискового узора. Самый тяжёлый штраф, и понятно почему.
• Правило 4 (вес 10). Отклонение доли тёмных модулей от 50%: за каждые полные 5% отклонения начисляется 10 баллов.

Номер выбранной маски записывается в поле формата — три бита, — чтобы декодер знал, какой узор снимать. Именно поэтому «случайный» вид QR-кода на самом деле оптимизирован: генератор перебрал восемь раскладок и выбрал ту, которая меньше всего мешает чтению.

Служебные поля: формат и версия

Поле информации о формате — 15 бит, которые декодер читает раньше всего остального. Полезных из них всего пять: два бита уровня коррекции и три бита номера маски. Остальные десять — проверочные по коду БЧХ, они позволяют восстановить поле, даже если часть его повреждена. Перед записью в матрицу эти 15 бит складываются по XOR с константой 101010000010010 — чтобы поле никогда не оказалось полностью светлым или полностью тёмным: сплошное пятно рядом с поисковым узором сломало бы распознавание.

Записывается формат в двух копиях: одна полоса огибает левый верхний поисковый узор, вторая разбита между областями у правого верхнего и левого нижнего. Дублирование не декоративное — если один угол уничтожен, формат читается со второй копии и декодирование продолжается.

Поле информации о версии появляется только с версии 7: 18 бит, из которых 6 — номер версии, 12 — проверочные БЧХ. Тоже в двух копиях, блоками 3×6 и 6×3 рядом с правым верхним и левым нижним узорами. Для версий 1-6 размер однозначно вычисляется по числу модулей в стороне, поэтому поле не нужно.

Как биты раскладываются по матрице

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

Функциональные узоры при укладке пропускаются: дойдя до поискового или выравнивающего узора, до синхронизирующей дорожки или служебного поля, алгоритм перешагивает занятые ячейки и продолжает со следующей свободной. Отдельное правило для вертикальной дорожки в шестом столбце: колонка данных её не пересекает, а сдвигается, иначе шаг двухмодульных колонок сбился бы на всю оставшуюся ширину. У некоторых версий после укладки остаётся от трёх до семи неиспользованных модулей — остаточные биты; их заполняют нулями, на декодирование они не влияют.

Что происходит при сканировании: путь от кадра до строки

Со стороны кажется, что телефон просто «видит» код. Внутри же выполняется вполне конкретная последовательность шагов.

1. Захват и бинаризация. Кадр переводится в чёрно-белый вид, порог считается адаптивно по локальным участкам — иначе тень от пальца или блик лампы съедят половину кода.
2. Поиск узоров. Изображение сканируется строками в поисках соотношения 1:1:3:1:1; кандидаты проверяются перекрёстно по вертикали и диагонали, ложные отсеиваются.
3. Определение геометрии. По трём найденным центрам вычисляются поворот, масштаб и положение четвёртого угла; выравнивающие узоры уточняют перспективное преобразование.
4. Сэмплирование сетки. По синхронизирующей дорожке определяется версия, затем декодер вычисляет центр каждого модуля и берёт его цвет, получая матрицу нулей и единиц.
5. Чтение формата. Извлекаются уровень коррекции и номер маски; при повреждении идёт в ход вторая копия или восстановление по БЧХ.
6. Снятие маски. К области кодирования применяется тот же XOR с тем же узором — операция обратима сама себе.
7. Сборка потока. Модули читаются зигзагом в порядке кодирования, собираются в кодовые слова, затем деинтерливинг разносит их обратно по блокам.
8. Коррекция ошибок. Каждый блок прогоняется через декодер Рида — Соломона. Если повреждений больше лимита, блок невосстановим и всё чтение проваливается.
9. Разбор данных. Читается индикатор режима, счётчик символов, сами данные — и так до терминатора; сегментов может быть несколько подряд.
10. Выдача результата. Строка уходит приложению, которое решает, что делать: открыть ссылку, показать текст, подключиться к Wi-Fi, добавить контакт.

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

Что из теории реально влияет на практику

Устройство матрицы объясняет большинство практических правил, которые обычно подают списком без обоснования.

• Логотип в центре. Он работает не «потому что так можно», а потому что перекрытая площадь съедается коррекцией. Центр выбирают из-за того, что там нет ни одного функционального узора. Безопасный ориентир — не больше 15-20% площади даже на уровне H: формальные 30% относятся к кодовым словам, а не к геометрии, и запас нужен на потери при печати.
• Длина ссылки. Каждый лишний десяток символов может поднять версию на ступень, а с ней вырастет число модулей. При фиксированном физическом размере модуль мельчает и дистанция считывания падает. Короткий адрес — инженерное требование, а не эстетика.
• Контраст и инверсия. Декодер ждёт тёмные модули на светлом фоне. Светлый код на тёмном часть сканеров читает, часть нет — стандарт такой вариант прямо не предписывает. Цветной QR допустим при достаточной разнице яркостей, но синий на чёрном нечитаем, даже если человеку узор виден.
• Размер под дистанцию. Отраслевое правило: сторона кода примерно в десять раз меньше расстояния считывания. Полтора метра — сторона около 15 см. Для наружной рекламы считать нужно именно так, а не «на глаз по макету».
• Изгиб поверхности. На бутылке или тубе матрица искажается нелинейно. Выравнивающие узоры это частично компенсируют, но чем крупнее версия, тем сильнее накапливается ошибка. Для цилиндров держите версию пониже — то есть содержимое покороче.

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

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