Архитектура алгоритма

Как работает коррекция ошибок в QR-кодах: математика Reed-Solomon простыми словами

Задумывались, почему QR-код безупречно сканируется, даже если он порван, залит кофе, частично стёрт или закрыт посередине логотипом компании? Секрет — в полиномиальной коррекции ошибок Reed-Solomon.

Четыре QR-кода одного адреса с уровнями коррекции ошибок L, M, Q и H; у каждого закрашено 7, 15, 25 или 30 процентов площади, чтобы показать, какие повреждения уровень способен восстановить

1. Что такое коррекция ошибок Reed-Solomon?

Коррекция ошибок Reed-Solomon (RS), изобретённая в 1960 году математиками Ирвингом С. Ридом и Гюставом Соломоном, — это недвоичный циклический алгоритм исправления ошибок, который широко применяется в космической связи (NASA Voyager), на оптических дисках CD/DVD, в спутниковом телевидении и в стандарте QR-кодов ISO/IEC 18004.

Код Reed-Solomon не просто обнаруживает ошибки (как простой бит чётности или контрольная сумма CRC), а создаёт избыточные математические блоки контроля, способные точно определить место повреждённых байтов и восстановить исходные данные без повторной передачи.

2. Четыре уровня коррекции ошибок QR-кода

Стандарт ISO/IEC 18004 определяет четыре уровня коррекции ошибок (ECC) на выбор. Каждый уровень означает долю всех кодовых слов, которую можно уничтожить или закрыть, прежде чем код перестанет читаться:

Уровень ECC Объём восстановления Плотность модулей Рекомендуемое применение
Уровень L (Low, низкий) ~7% данных Наименьшая плотность (меньше всего квадратов) Цифровые экраны, объёмные данные, когда QR-код должен оставаться маленьким.
Уровень M (Medium, средний) ~15% данных Сбалансированный стандарт По умолчанию для обычных ссылок, упаковки, листовок и рекламной печати.
Уровень Q (Quartile, четверть) ~25% данных Умеренная плотность Лучший выбор для своих логотипов, настольных табличек и мест, где код быстро изнашивается.
Уровень H (High, высокий) ~30% данных Наибольшая плотность (больше всего квадратов) Уличные билборды, промышленные бирки, условия сильных физических нагрузок.

3. Как логотип использует коррекцию ошибок

Когда вы размещаете логотип или значок в центре QR-кода, оптический датчик сканера воспринимает логотип как физическое повреждение поверхности или отсутствующие модули.

Поскольку уровень коррекции ошибок Q восстанавливает до 25% повреждённых данных, а уровень H — до 30%, математический декодер Reed-Solomon вычисляет недостающие модули под логотипом и за миллисекунды восстанавливает исходный URL.

Золотые правила для QR-кодов с логотипом:

  • Максимальная площадь: логотип никогда не должен занимать больше 20–25% общей площади QR-кода.
  • Берегите три угловых узора: логотип никогда не должен закрывать или касаться трёх больших квадратных поисковых узоров («глазков») в верхнем левом, верхнем правом и нижнем левом углах.
  • Используйте белые поля: всегда оставляйте вокруг логотипа сплошное белое защитное поле, чтобы окружающие модули QR-кода не сливались с графикой логотипа.
  • Автоматический переход на уровень Q или H: qr-code.love автоматически повышает уровень коррекции ошибок до Q или H, когда вы загружаете свой логотип.

4. Математический конвейер в поле Галуа GF(256)

Кодировщик, работающий в вашем браузере, выполняет вычисления в конечном поле из 256 элементов, которое обозначается GF(28) или GF(256). Каждый байт — элемент этого поля, а умножение определено по модулю следующего примитивного многочлена:

P(x) = x8 + x4 + x3 + x2 + 1   (0x11D в шестнадцатеричной записи)

Байты данных рассматриваются как коэффициенты многочлена D(x). Движок умножает его на xE, где E — число кодовых слов коррекции ошибок, которого требует уровень, и делит результат на фиксированный порождающий многочлен G(x) этого уровня. Остаток от деления и есть контрольные данные: E байт, которые размещаются в символе после данных.

5. Восемь масок ISO и штрафные баллы

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

Чтобы решить эту проблему, стандарт ISO/IEC 18004 накладывает на сетку 8 вариантов математических XOR-масок. Движок оценивает каждый вариант по строгой штрафной формуле:

  • Штраф 1 (серии соседних модулей): каждая серия из 5 и более модулей одного цвета подряд добавляет 3 балла плюс 1 за каждый модуль сверх пяти.
  • Штраф 2 (блоки 2×2 модуля): каждый сплошной квадрат 2×2 добавляет 3 штрафных балла.
  • Штраф 3 (ложные поисковые узоры): любая последовательность модулей в пропорции 1:1:3:1:1 добавляет 40 штрафных баллов.
  • Штраф 4 (дисбаланс тёмных и светлых): отклонение от баланса 50/50 добавляет пропорциональные штрафные баллы.

Выбирается маска с наименьшей суммой штрафных баллов, и её номер записывается в биты информации о формате вокруг поисковых узоров.

6. Устойчивость к реальным внешним воздействиям

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

Условия эксплуатации Рекомендуемый ECC Типичный риск повреждений
Уличные билборды и металлические таблички Уровень H (30%) Выцветание от УФ-излучения, потёки дождя, ржавчина и птичий помёт.
Настольные таблички и меню в ресторанах Уровень Q (25%) Пролитая еда, отпечатки пальцев и спиртовые антисептики.
Упаковка товаров и этикетки Уровень M (15%) Лёгкое трение поверхности и потёртости при обращении.
Цифровые экраны и телевещание Уровень L (7%) Никакого физического износа; приоритет — минимальное число пикселей.

7. Кодовые слова данных и коррекции ошибок по версиям

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

ВерсияВсегоL (данные + EC)MQH
12619 + 716 + 1013 + 139 + 17
24434 + 1028 + 1622 + 2216 + 28
37055 + 1544 + 2634 + 3626 + 44

Не все кодовые слова данных — полезная нагрузка. Первые биты занимают индикатор режима и счётчик символов; в байтовом режиме это двенадцать бит до версии 9 и двадцать начиная с версии 10. Поэтому символ версии 1 на уровне L вмещает 17 байт ваших данных, а не 19.

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

Источники и дополнительное чтение

Создавайте QR-коды с коррекцией ошибок

Выберите нужный уровень Reed-Solomon (L, M, Q, H) и добавьте логотип своего бренда — без какой-либо записи на сервере.

Открыть универсальный генератор