Алгоритм Рида-Соломона
Метод помехоустойчивого кодирования, который дополняет данные 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-кода логотипы, брендовые иконки и декоративные элементы. Область изображения считается «повреждённой», но коды коррекции компенсируют потерю информации. Для логотипов, закрывающих значительную площадь, рекомендуется использовать уровень H.
Применение за пределами QR
Рид-Соломон применяется не только в QR-кодах. Этот же алгоритм лежит в основе защиты данных на CD и DVD, системах спутниковой связи, глубоководных и авиационных каналах передачи, а также флеш-памяти NAND, где физический износ ячеек неизбежно порождает ошибки. Универсальность алгоритма объясняется его математической элегантностью: исправляющая способность масштабируется выбором степени избыточности без изменения базовой процедуры кодирования.
При создании QR-кода на платформе QRcode.website уровень коррекции задаётся в настройках дизайна. Чем выше уровень — тем крупнее матрица при том же объёме данных, и тем устойчивее код к механическим повреждениям, царапинам и грязи в реальных условиях печати.