Алгоритм Рида-Соломона
Метод помехоустойчивого кодирования, который дополняет данные QR-кода блоками коррекции и позволяет восстанавливать содержимое даже при повреждении до 30% поверхности.
Алгоритм Рида-Соломона — метод помехоустойчивого кодирования, разработанный математиками Irving S. Reed и Gustave Solomon в 1960 году. Алгоритм добавляет к исходным данным избыточные блоки коррекции, вычисленные над конечным полем Галуа. Декодер использует эти блоки для нахождения и исправления ошибок даже тогда, когда часть битов данных повреждена или полностью потеряна.
Применение в QR-кодах
Стандарт ISO/IEC 18004 обязывает кодировать каждый QR-символ с использованием Рида-Соломона над полем GF(256). Данные разбиваются на блоки, каждый из которых дополняется так называемыми кодовыми словами коррекции (error correction codewords). Их количество определяется выбранным уровнем коррекции ошибок: L, M, Q или H. На уровне H до 30% кодовых слов могут быть испорчены — сканер всё равно правильно восстановит исходную строку.
Именно этот механизм позволяет размещать в центре QR-кода логотипы, брендовые иконки и декоративные элементы. Область изображения считается «повреждённой», но коды коррекции компенсируют потерю информации. Подробнее о том, как это работает на практике, читайте в статье QR-код с логотипом: дизайн и сканирование. Для QR-кода с логотипом, закрывающего значительную площадь, рекомендуется использовать уровень H.
Применение за пределами QR
Рид-Соломон применяется не только в QR-кодах. Этот же алгоритм лежит в основе защиты данных на CD и DVD, системах спутниковой связи, глубоководных и авиационных каналах передачи, а также флеш-памяти NAND, где физический износ ячеек неизбежно порождает ошибки. Универсальность алгоритма объясняется его математической элегантностью: исправляющая способность масштабируется выбором степени избыточности без изменения базовой процедуры кодирования.
При создании QR-кода на платформе QRcode.website уровень коррекции задаётся в настройках дизайна. Чем выше уровень — тем крупнее матрица при том же объёме данных, и тем устойчивее код к механическим повреждениям, царапинам и грязи в реальных условиях печати. Создайте QR-код с нужным уровнем коррекции прямо сейчас — это займёт меньше минуты.
Частые вопросы
Почему алгоритм Рида-Соломона позволяет восстановить данные при повреждении кода?
Алгоритм добавляет к исходным данным избыточные кодовые слова коррекции, вычисленные по законам алгебры над конечным полем GF(256). Когда часть матрицы QR-кода повреждена или закрыта, декодер рассматривает повреждённые позиции как «стирания» (erasures) и находит исходное сообщение, решая систему полиномиальных уравнений. Математически это аналогично восстановлению полинома по части его значений — задача имеет однозначное решение, пока число потерянных точек не превышает степень избыточности.
Какой уровень коррекции выбрать, если в QR-код добавляется логотип?
Рекомендуется уровень H (High), обеспечивающий восстановление до 30% повреждённых кодовых слов. Логотип в центре кода физически перекрывает часть модулей матрицы, и декодер воспринимает эту область как повреждение. Уровни L и M (7% и 15% соответственно) могут не дать достаточного запаса при крупном изображении. Уровень Q (25%) — разумный компромисс, если размер матрицы критичен: он создаёт код меньшего размера, чем H, при приемлемой надёжности для небольшого логотипа.
Влияет ли алгоритм Рида-Соломона на читаемость QR-кода обычными смартфонами?
Нет, современные сканеры — в том числе встроенные камеры Android и iOS — применяют алгоритм автоматически при декодировании. Пользователю не нужно ничего настраивать. Единственное практическое следствие: QR-коды с высоким уровнем коррекции содержат больше модулей и выглядят «плотнее». Это не затрудняет сканирование — напротив, плотная матрица с большим числом кодовых слов коррекции считывается надёжнее при плохом освещении или угловом захвате камерой.