Reed-Solomon
Reed-Solomon — алгоритм помехоустойчивого кодирования, используемый в QR-кодах, Data Matrix, CD, DVD и цифровом телевидении для коррекции ошибок.
Определение Reed-Solomon
Reed-Solomon — семейство алгоритмов помехоустойчивого кодирования, опубликованное в 1960 году математиками Ирвингом Ридом и Густавом Соломоном из MIT Lincoln Laboratory. Алгоритм позволяет обнаруживать и исправлять многократные ошибки в блоках данных за счёт добавления избыточных байтов (кодовых слов). Reed-Solomon (RS) является основой практически всех систем хранения и передачи цифровых данных: QR-кодов, Data Matrix, компакт-дисков, DVD, Blu-ray, цифрового телевидения DVB, глубокого космоса (Voyager, Mars Rover) и каналов связи спутникового Интернета.
Ключевое свойство Reed-Solomon — способность восстановить данные даже при потере или искажении значительной части кодового блока. В QR-коде при уровне коррекции H восстанавливается до 30% повреждённой поверхности: код читается, даже если его наполовину оторвали, нанесли логотип или частично покрасили. Этот феномен делает QR-коды устойчивыми к реальным условиям печати, сканирования и износа.
Математическая основа
Reed-Solomon работает в конечных полях Галуа GF(2^m), обычно GF(256) для байтовых данных. Каждое сообщение представляется как полином над GF(256), к которому добавляются байты, равные остаткам от деления на порождающий полином. При декодировании из принятого полинома вычитаются известные данные, а остаток показывает положения и значения ошибок. Для QR-кода порождающий полином имеет степень, равную количеству байтов коррекции (от 7 до 30 в зависимости от уровня ECC).
Если код добавляет 2t избыточных байт, Reed-Solomon может исправить до t ошибок в случайных позициях или до 2t «стираний» (erasure — потерь в известных позициях). Это свойство двукратного выигрыша для известных позиций активно используется в QR-коде: когда область кода физически оторвана, декодер знает, что эти байты потеряны, и применяет соответствующий алгоритм.
Применение Reed-Solomon
- QR-код — уровни коррекции L (7%), M (15%), Q (25%), H (30%)
- Data Matrix — обязательная коррекция до 30% площади
- Aztec Code — настраиваемая коррекция 5–95%
- Компакт-диски (CD) — CIRC (Cross-Interleaved Reed-Solomon Code)
- DVD, Blu-ray — каскадные коды RS на двух уровнях
- Цифровое ТВ DVB — RS(204,188) в транспортном потоке
- Космическая связь — Voyager, Mars Rover, Hubble
- RAID-6 массивы — защита от потери двух дисков
Уровни коррекции в QR-коде
| Уровень | Восстановление | Избыточность | Применение |
|---|---|---|---|
| L (Low) | ~7% | Минимальная | Чистые условия, минимальный размер |
| M (Medium) | ~15% | Базовая | Обычный маркетинг, упаковка |
| Q (Quartile) | ~25% | Повышенная | Промышленность, открытая среда |
| H (High) | ~30% | Максимальная | С логотипом в центре, сложные условия |
История открытия
Алгоритм опубликован Ирвингом Ридом и Густавом Соломоном в 1960 году в статье «Polynomial Codes Over Certain Finite Fields» в Journal of the Society for Industrial and Applied Mathematics. Первое практическое применение — в 1977 году, когда NASA использовало Reed-Solomon для связи с зондом Voyager. В 1979 году Philips и Sony выбрали RS как основу помехоустойчивого кодирования компакт-дисков, что сделало алгоритм массовым. С 1994 года RS встроен в QR-код по стандарту ISO/IEC 18004.
Связанные концепции
- Уровень коррекции ошибок (ECC) — практическое применение RS в QR.
- QR-код — массовый пользователь алгоритма.
- Data Matrix — тоже основан на Reed-Solomon.
Частые вопросы
Почему QR-код с логотипом в центре работает?
Благодаря алгоритму Reed-Solomon QR-код восстанавливает до 30% повреждённой площади при максимальном уровне коррекции H. Логотип в центре перекрывает 10–15% модулей, и декодер воспринимает это как «стирания» в известных позициях, которые успешно исправляются за счёт избыточных байтов. Поэтому при добавлении логотипа всегда выбирают уровень Q (25%) или H (30%) — иначе код может стать нечитаемым.
Кто изобрёл Reed-Solomon?
Алгоритм разработали американские математики Ирвинг Рид и Густав Соломон, работавшие в MIT Lincoln Laboratory. Статья «Polynomial Codes Over Certain Finite Fields» опубликована в 1960 году в Journal of the Society for Industrial and Applied Mathematics. Рид также известен как один из разработчиков алгоритма коррекции Рида-Маллера. Соломон занимался теорией кодирования для космических коммуникаций. Оба получили премию IEEE Information Theory Society Paper Award в 1995 году за этот вклад.
Сколько ошибок может исправить Reed-Solomon?
Если код добавляет 2t избыточных байтов, Reed-Solomon гарантированно исправляет до t случайных ошибок или до 2t «стираний» (потерь в известных позициях). Например, при 20 избыточных байтах можно исправить 10 ошибок или 20 стираний. В QR-коде уровня H добавляется 30% избыточности, что даёт восстановление 15% случайных искажений или до 30% стёртых участков. Это огромный резерв надёжности по сравнению с другими схемами коррекции.
Где ещё применяется Reed-Solomon кроме QR?
Reed-Solomon встроен практически во все системы хранения и передачи цифровых данных. Компакт-диски и DVD используют каскадные RS-коды для защиты от царапин. Цифровое телевидение DVB применяет RS(204,188). Спутниковая связь, 4G/5G мобильные сети, WiMAX, DSL-модемы — везде RS. NASA использует RS для связи с Voyager (до сих пор работает с 1977), Mars Rover, телескопом Hubble. В RAID-6 массивах жёстких дисков RS защищает от одновременной потери двух дисков.
Замедляет ли Reed-Solomon сканирование QR?
Нет, Reed-Solomon декодируется очень быстро — на современных процессорах смартфона распознавание QR-кода занимает 20–50 миллисекунд, включая поиск меток, декодирование матрицы, проверку и коррекцию через RS. Алгоритм оптимизирован для аппаратной реализации и работает с линейной сложностью от объёма данных. Пользователь не замечает задержек: от момента наведения камеры на код до отображения ссылки проходит доля секунды, и Reed-Solomon — лишь малая часть этого времени.