Как QR-код прячет целую ссылку в чёрно-белых квадратиках

Чёрно-белый квадрат — это не картинка, а аккуратно упакованный текст, который читается даже с пятнами и заломами.

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

Сетка из модулей

Если присмотреться, QR-код состоит из множества маленьких квадратиков одинакового размера. Каждый такой квадратик называется модулем. Чёрный модуль — это единица, белый — ноль. Самый маленький код версии 1 имеет сетку 21 на 21 модуль, а большие версии разрастаются до 177 на 177 и вмещают тысячи символов.

Камере не нужно знать, где именно начинается и заканчивается каждый модуль заранее. Она ориентируется по характерным элементам узора, о которых речь ниже, и уже от них отсчитывает сетку. Поэтому код читается под углом, издалека и даже отражённым в стекле.

Три «глаза» по углам

Самая заметная деталь — три больших квадрата в углах. Это позиционные маркеры (finder patterns). Каждый из них устроен как квадрат в квадрате: чёрная рамка, белый промежуток, чёрный центр. Соотношение толщин полос всегда строго 1:1:3:1:1.

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

Зачем четвёртый угол другой

В четвёртом углу большого маркера нет — вместо него маленький квадратик-якорь (alignment pattern). Он помогает выпрямить картинку, если код наклеен на изогнутую банку или сфотографирован под углом. По известным точкам программа математически «расправляет» сетку обратно в ровный квадрат.

Где же спрятана сама ссылка

Свободное поле между маркерами и есть хранилище данных. Сначала идёт служебная зона: формат (какой уровень защиты и какая маска применены) и, для крупных кодов, версия. Затем — сами данные.

Текст кодируется не как попало. Сначала записывается режим: только цифры, цифры с буквами, или произвольные байты (для ссылок обычно байтовый режим UTF-8). Потом — длина, а уже потом байты самого адреса. Биты укладываются в сетку зигзагом снизу вверх и сверху вниз, колонками по два модуля, обходя служебные зоны.

Режим (4 бита) -> Длина -> Данные (https://...) -> Заполнитель

Почему код читается с царапинами

Главная магия — в избыточности. К данным добавляются байты коррекции ошибок по алгоритму Рида — Соломона. Это тот же класс кодов, что спасает музыку на поцарапанном CD и снимки с межпланетных станций.

Идея в том, что исходное сообщение дополняется проверочными байтами так, что любые потерянные или искажённые куски можно вычислить обратно — как недостающее число в уравнении. Есть четыре уровня защиты:

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

Хитрость с масками

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

Кодировщик пробует все восемь стандартных масок, оценивает каждую по «штрафным очкам» за плохие участки и выбирает самую контрастную и равномерную. Номер выбранной маски записан в служебной зоне, так что при чтении инверсию легко отменить.

Что в итоге

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