В каждом QR-коде зашита половина лишней информации. Намеренно

TL;DR QR-код продолжает работать, если замазать маркером четверть его площади, наклеить сверху логотип или оторвать угол. Это математически точная избыточность, которая на максимальном уровне коррекции занимает около 60% всех модулей кода. Под катом — почему так, как это устроено, немного кода на Python и при чём здесь Toyota 1994 года.

Маленький эксперимент

Если вы возьмете обычный QR-код, ведущий на habr.com. Откроете редактор и нарисуете поверх него кошку. Кривую, фломастером — какую угодно, то сканер всё равно прочитает ссылку.

Закрасите четверть площади сплошным чёрным? Прочитает.

Вырежете угол ножницами? Прочитает.

Это легко проверить: возьмите телефон, любой генератор QR-кодов, и постепенно увеличивайте площадь поверхностного шума. В какой-то момент сканер сдастся, но «какой-то момент» наступит сильно позже, чем кажется.

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

Сколько именно «лишнего»?

У QR-кода есть четыре уровня коррекции ошибок:

Цифра «можно повредить N%» означает: вы можете стереть, замазать или испортить эту долю кодовых слов (байт), и код всё равно будет прочитан корректно. Чтобы алгоритм исправил одну ошибку, ему нужно держать в коде два дополнительных байта-страховщика. То есть на уровне H собственно полезной информации в коде — около 40%. Остальное — служебка, маркеры и Reed-Solomon.

Именно поэтому маркетологам разрешают вставлять логотипы посреди QR-кодов: задают уровень H, накрывают центр чем угодно, и оно работает.

Reed-Solomon на пальцах

В основе коррекции лежит код Рида-Соломона над конечным полем GF(2⁸) = GF(256). Звучит зловеще, но идея на пальцах формулируется без потерь.

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

Рид-Соломон — это толковое обобщение. Вместо дефолтного повторения мы:

1. Берём k исходных байт данных и интерпретируем их как коэффициенты многочлена степени k-1.

2. Вычисляем значения этого многочлена в n > k точках.

3. Передаём все n значений.

Теперь школьная теорема: многочлен степени k-1 однозначно восстанавливается по любым k своим значениям. Значит, получатель может потерять до n-k значений из n — и всё равно восстановить полином, а с ним и данные.

Если же значения не потеряны, а искажены (мы не знаем, какие из них правильные) — потребуются более хитрые алгоритмы: Berlekamp-Massey, метод Форни. Они находят, какие байты «врут», и исправляют их. Лимит: до (n-k)/2 искажений.

То есть чем больше «лишних» значений добавили, тем больше потерь стерпит код.

GF(256), или почему оно вообще конечное

Тут резонный вопрос: мы считаем значения многочлена — но байт-то всего 256 разных, а значения многочлена с ростом x улетают в бесконечность. Что делать?

Ответ: работать в конечном поле. В GF(256) есть ровно 256 элементов (все возможные значения байта), и в этом поле определены сложение, вычитание, умножение и деление так, что они «замкнуты» — результат любой операции снова попадает в эти же 256 значений.

Конкретно для QR-кода используют поле GF(2⁸), построенное по неприводимому многочлену x⁸ + x⁴ + x³ + x² + 1. Реализуется тривиально. Сложение в GF(2⁸) — это просто XOR. А умножение можно сделать через две таблицы: экспонент и логарифмов.

# Построение таблиц GF(256) для QR-кода (полином 0x11D)
gf_exp = [0] * 512
gf_log = [0] * 256
x = 1
for i in range(255):
    gf_exp[i] = x
    gf_log[x] = i
    x <<= 1
    if x & 0x100:           # если "вышли за байт" — приводим по модулю
        x ^= 0x11D
for i in range(255, 512):   # дублируем для удобства, чтобы не делать % 255
    gf_exp[i] = gf_exp[i - 255]
def gf_mul(a, b):
    if a == 0 or b == 0:
        return 0
    return gf_exp[gf_log[a] + gf_log[b]]
# Проверка: 0x80 * 0x02 — это сдвиг на разряд влево, дающий 0x100;
# вылезший девятый бит убираем XOR'ом с полиномом 0x11D, остаётся 0x1D.
print(hex(gf_mul(0x80, 0x02)))   # 0x1d

Двенадцать строк, и у вас есть всё умножение в поле, на котором держится коррекция ошибок не только QR, но и CD, DVD, Blu-ray, спутникового телевидения и связи с «Вояджерами». Семейство таких полей (GF(2⁸) с разными полиномами редукции) вообще на удивление вездесущее: MixColumns в AES работает в GF(2⁸), только с полиномом 0x11B вместо QR-шного 0x11D. То есть когда вы открываете HTTPS-страницу, под капотом несколько раз в секунду прокручивается арифметика того же типа.

Что ещё занимает место (кроме коррекции)

Помимо избыточности под Reed-Solomon, в QR-коде довольно много вещей вообще не несут пользовательских данных:

• Позиционные маркеры — три больших квадрата по углам. По ним сканер находит код в кадре и ориентирует его (в любом повороте). Внутри каждого маркера — соотношение 1:1:3:1:1 чёрно-белых полос; именно его сканер ищет в кадре по горизонтали и вертикали.

• Маркеры выравнивания — маленькие квадратики (их количество растёт с размером кода). Компенсируют перспективные искажения, если код сфотографирован под углом.

• Тайминг-паттерны — чередующиеся черно-белые полоски между угловыми маркерами. По ним вычисляется размер одного модуля и линейные искажения.

• Формат-информация — 15 бит, кодирующих уровень коррекции и номер маски. И они тоже защищены отдельным BCH-кодом, восстанавливающимся при трёх ошибках из пятнадцати.

• Версия-информация — для версий 7 и старше: ещё 18 бит, говорящих сканеру размер кода. Тоже BCH-защищённые.

• Маска — XOR-паттерн, накладываемый поверх всего кода (об этом ниже).

В сумме на «версии 1» (сетка 21×21, итого 441 модуль) при уровне L под собственно данные остаётся 152 бита. Это 19 байт. Меньше длины твита 2007 года.

Четыре режима кодирования

Чтобы выжать из этих 19 байт максимум, QR умеет кодировать данные четырьмя разными способами:

Заметили: «3.33 бита на цифру»? Это потому что цифры кодируются группами по три: три десятичные цифры — это число от 0 до 999, которое влезает в 10 бит. Получается 10/3 ≈ 3.33 бита на цифру.

Аналогично для alphanumeric: символы кодируются парами, каждая пара — число от 0 до 44² = 1935, влезает в 11 бит. То есть 5.5 бит на символ.

В один QR-код можно складывать сегменты разных режимов подряд. Поэтому для строки вида HABR42 оптимальный кодировщик использует alphanumeric (а не byte) и экономит 30% бит. Энкодеры по умолчанию обычно делают это автоматически.

Маски: зачем они и почему их восемь

Если бы QR-код выводился «как есть», часто получались бы длинные одноцветные полосы, большие чёрные блоки или совпадения с позиционными маркерами. Сканеру было бы плохо: он не сможет надёжно отличить модули данных от служебной разметки.

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

• штраф за длинные одноцветные ряды и столбцы (5 модулей и больше);

• штраф за блоки 2×2 одного цвета;

• штраф за паттерны, похожие на позиционные маркеры (соотношение 1:1:3:1:1);

• штраф за общий перекос баланса чёрного и белого.

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

Номер выбранной маски записывается в формат-инфрмацию, чтобы декодер знал, что снимать.

Практика: посмотрим разницу на коде

Установим библиотеку и сгенерируем один и тот же URL с четырьмя разными уровнями коррекции:

# pip install qrcode[pil]
import qrcode
from qrcode.constants import (
    ERROR_CORRECT_L, ERROR_CORRECT_M,
    ERROR_CORRECT_Q, ERROR_CORRECT_H,
)
URL = "https://habr.com/ru/articles/000000/"
levels = {
    "L": ERROR_CORRECT_L,
    "M": ERROR_CORRECT_M,
    "Q": ERROR_CORRECT_Q,
    "H": ERROR_CORRECT_H,
}
for name, ecc in levels.items():
    qr = qrcode.QRCode(error_correction=ecc, box_size=10, border=2)
    qr.add_data(URL)
    qr.make(fit=True)
    side = qr.modules_count            # сторона матрицы в модулях
    total = side * side
    img = qr.make_image()
    img.save(f"qr_{name}.png")
    print(f"{name}: версия {qr.version}, {side}×{side} = {total} модулей")

L: версия 3, 29×29 = 841 модулей

M: версия 3, 29×29 = 841 модулей

Q: версия 4, 33×33 = 1089 модулей

H: версия 5, 37×37 = 1369 модулей

Одна и та же ссылка в 42 символа. При L и M помещается в версию 3 (29×29). При Q уже нужна версия 4. При H — версия 5, в полтора раза больше по площади. Эти «лишние» модули — и есть та самая страховка.

А вот вторая половина эксперимента: возьмите получившийся qr_H.png, откройте в Paint и закрасьте чёрным любую четверть. Сканер вашего телефона всё равно его прочтёт.

Любопытные следствия

1. Логотип в центре — это by design. При уровне H центральные ~25% можно безболезненно закрасить чем угодно. Большинство онлайн-генераторов делают это автоматически: ставят H, рисуют поверх лого. Тут никакого особого алгоритма — одна избыточность.

2. QR-арт. Существуют алгоритмы (а в последнее время — и нейросети) которые подбирают значения «свободных» модулей так, чтобы код визуально превращался в осмысленное изображение, оставаясь валидным. Stable Diffusion + ControlNet — самый известный из современных подходов. Получаются фотореалистичные QR-коды, которые работают.

3. Атаки подменой. Reed-Solomon защищает от случайного шума, но не от целенаправленных правок. Если злоумышленник аккуратно изменит несколько модулей данных так, что результат станет указывать на другой URL, — сканер прочитает «исправленные» данные как валидные и не заметит подмены.

4. Малюсенький QR-код — миф. Чем меньше код, тем большую долю его площади занимает обязательная служебка (маркеры, тайминги, формат-информация). Поэтому «маленький код с одной короткой ссылкой» на практике почти всегда не такой уж и маленький.

5. Старший брат: версия 40. Самый большой стандартный QR-код имеет размер 177×177 модулей и вмещает до 2953 байт двоичных данных (на уровне L). На уровне H — уже 1273 байта. Разница ровно того порядка, что мы обсуждаем.

6. Чёрно-белая инверсия. Стандарт допускает инверсию: белые модули на чёрном фоне. Современные сканеры это понимают, хотя старые могли спотыкаться.

Соседи по семейству

QR — не единственный 2D-код в мире, просто самый известный. Соседи решают похожие задачи с разными компромиссами:

• Data Matrix — квадратный или прямоугольный код, тоже на Reed-Solomon, но компактнее на коротких данных. Стандарт в фарме и электронике (маркировка деталей).

• Aztec Code — концентрический, без quiet zone (свободного поля по краям), хорошо читается на билетах и пропусках. Используется в авиа- и ж/д-билетах.

• PDF417 — полосчатый (stack-based), читается линейными сканерами. На задней стороне водительских прав в США.

• MaxiCode — фирменный код UPS, шестиугольные модули. Оптимизирован под чтение на быстром конвейере.

• HCCB (High Capacity Color Barcode) — короткоживущий проект Microsoft с цветными модулями, чтобы запихнуть больше данных. Не взлетел.

Но QR победил потому, что Denso Wave открыли спецификацию и не стали брать роялти. Все остальные изобретатели 2D-кодов теперь тихо сидят в сторонке.

История и почему именно столько

Цифры 7/15/25/30% — компромисс между:

• размером кода (больше избыточности, больше модулей, больше места на упаковке);

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

• скоростью декодирования (в 1994 году процессоры были, мягко говоря, не современные).

QR разрабатывался в 1994 году в компании Denso Wave — дочке Toyota — для маркировки автомобильных деталей на производственной линии. Деталь могла прийти в масле, царапинах и грязи; сканер должен был успеть прочитать её за доли секунды. Команда из двух человек под руководством Масахиро Хары потратила на разработку полтора года. Идея с позиционными маркерами в углах, говорят, пришла Харе в обед, когда он играл в го: фишки на доске — это, в каком-то смысле, тоже двоичная сетка.

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

Зато ваш QR-код на меню в кафе всё ещё читается, после того как официант пролил на него соус и протёр салфеткой. А промышленные коды на автозапчастях читаются после поездки в контейнере через половину Тихого океана.