Кратко: QR-код продолжает исправно считываться, даже если вы закрасите четверть его поверхности, наложите поверх логотип или случайно повредите один из углов. Это не случайность, а результат математически выверенной избыточности. В режиме максимальной коррекции ошибок полезные данные занимают лишь около 40% структуры кода, а всё остальное — это алгоритмическая «подушка безопасности». Разбираемся, как это работает, причём здесь математика Рида-Соломона и почему успеху технологии мы обязаны инженерам Toyota образца 1994 года.
Эксперимент на практике
Попробуйте взять любой QR-код, ведущий на habr.com, и нарисуйте поверх него что угодно — хоть абстрактный узор, хоть кота. Сканер без труда распознает зашифрованную ссылку.
Закрасите 25% площади плотным чёрным маркером? Распознает. Отрежете ножницами угол? Тоже распознает.
Это легко проверить самостоятельно: вооружитесь смартфоном и любым онлайн-генератором QR-кодов. Постепенно увеличивайте уровень шума на изображении, и вы увидите, что предел работоспособности системы наступает гораздо позже, чем кажется на первый взгляд.
Причина проста: внушительная часть QR-кода — это избыточные данные, зарезервированные специально для восстановления информации при повреждениях.
Цена надежности
Стандарт QR предусматривает четыре уровня коррекции ошибок:
|
Уровень |
Допустимый урон |
Избыточность |
|
L (Low) |
~7% |
~14% |
|
M (Medium) |
~15% |
~30% |
|
Q (Quartile) |
~25% |
~50% |
|
H (High) |
~30% |
~60% |
Указанный процент означает долю поврежденных кодовых слов, которую алгоритм может успешно восстановить. Для исправления одной ошибки требуются два «контрольных» байта. Поэтому на уровне H полезная нагрузка составляет всего около 40%, остальное — это служебная информация, маркеры позиционирования и корректирующие коды Рида-Соломона. Именно поэтому логотип бренда в центре QR-кода — это не трюк, а грамотное использование высокого уровня коррекции.
Алгоритмы Рида-Соломона: суть на пальцах
В основе коррекции лежит математика конечных полей GF(2⁸). Представьте, что вам нужно передать число «5». Вместо простой отправки его восемь раз подряд (где большинство определяет правильный ответ), мы используем более элегантный метод:
-
Данные представляются как коэффициенты многочлена степени k-1.
-
Вычисляются значения этого полинома в n > k точках.
-
Получателю передаются все n значений.
Согласно алгебре, многочлен степени k-1 однозначно определяется любыми k точками. Это значит, что если мы передадим n значений, то даже при потере n-k фрагментов, данные будут успешно восстановлены. Если же значения не просто стерты, а искажены, в дело вступают алгоритмы Берлекэмпа-Мэсси или Форни, способные «вычислить» и исправить до (n-k)/2 ошибок.
Арифметика в поле GF(256)
Чтобы избежать ухода значений в бесконечность, расчеты ведутся в конечном поле Галуа GF(2⁸). Это позволяет всем операциям (сложению, умножению и т.д.) оставаться в рамках одного байта (0–255).
# Генерация таблиц для операций в GF(256) (полином 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):
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]]
print(hex(gf_mul(0x80, 0x02))) # Результат: 0x1dЭта арифметика повсеместна: она защищает данные на CD/DVD, в спутниковой связи, в работе зондов «Вояджер» и даже при шифровании AES, которое защищает ваш HTTPS-трафик.
Служебная архитектура QR
Помимо коррекции, значительное пространство занимают:
-
Позиционные маркеры: три крупных квадрата, помогающие сканеру определить ориентацию и границы кода.
-
Маркеры выравнивания: для компенсации искажений при съемке под углом.
-
Тайминг-паттерны: полосы, задающие шаг сетки.
-
Информация о формате и версии: параметры кодирования, защищенные кодами BCH.
-
Маскирование: специальные узоры, инвертирующие цвета для предотвращения появления длинных однотонных зон, сбивающих сканер.
На минимальной версии (21×21 модуль) для данных остается совсем мало места — всего 19 байт. Поэтому эффективность кодирования (цифровой, алфавитно-цифровой или байтовый режимы) критически важна для экономии пространства.
Маскирование: борьба за читаемость
Чтобы QR-код не превращался в сплошной массив, энкодер пробует восемь вариантов наложения маски (XOR-паттернов) и выбирает тот, где меньше «штрафных» зон (слишком длинных линий, крупных блоков одного цвета или подобий позиционных маркеров).
Выводы и нюансы
- Логотипы: благодаря уровню H, центральная часть QR-кода может быть скрыта — это штатная возможность стандарта.
- QR-арт: современные нейросети (например, через ControlNet) позволяют интегрировать код в полноценные изображения, сохраняя его валидность.
- Риски подмены: коррекция Рида-Соломона защищает от случайных повреждений, но не от намеренной правки данных злоумышленниками.
- Мифы о размере: крошечные QR-коды неэффективны, так как львиную долю площади все равно съедают служебные маркеры.
- Конкуренты: Data Matrix, Aztec и PDF417 имеют свои ниши (промышленность, билеты), но QR стал стандартом де-факто благодаря открытой спецификации.
Исторический контекст
QR-код был создан в 1994 году командой Denso Wave (подразделение Toyota) под руководством Масахиро Хары. Целью была маркировка автозапчастей, которые часто попадали на конвейер в масле, грязи и с царапинами. Идея с позиционными маркерами в углах возникла у Хары во время игры в го. Инженеры заложили избыточность в стандарт сознательно, чтобы обеспечить безотказное чтение в экстремальных производственных условиях. И этот подход сделал технологию практически «неубиваемой» — от сканера в смартфоне до промышленного оборудования.
