Происхождение и более широкое применение
Коды Рида — Соломона описали Ирвинг С. Рид и Густав Соломон в 1960 году. Они работают с целыми символами, обычно байтами, а не отдельными битами, поэтому хорошо справляются с серийными повреждениями вроде царапины или пятна.
Это же семейство кодов защищает данные на CD, DVD и дисках Blu-ray, в некоторых линиях цифрового телевидения и спутниковой связи, а также в других двумерных штрихкодах, включая Data Matrix ECC 200, Aztec Code и PDF417.
Как их использует QR-код
QR-код рассматривает каждое 8-битное кодовое слово как элемент конечного поля GF(256), построенного с помощью примитивного многочлена x^8 + x^4 + x^3 + x^2 + 1 (шестнадцатеричное 0x11D). Кодовые слова данных делятся на порождающий многочлен, а остаток становится кодовыми словами коррекции ошибок, которые добавляются к ним.
Крупные коды разбивают данные на несколько блоков, у каждого из которых свои кодовые слова коррекции ошибок. При размещении кодовых слов в сетке блоки перемежаются, поэтому одно повреждение распределяется по многим блокам, а не подавляет один.
Сколько можно исправить
Если в блоке n кодовых слов коррекции ошибок, декодер может исправить до n/2 кодовых слов с неизвестным положением или до n кодовых слов с известным положением — так называемых стираний. В смешанных случаях действует правило: каждая ошибка считается за два, а каждое стирание — за одно.
Поэтому код с чистой сплошной областью, закрытой логотипом, всё ещё может сканироваться: умный считыватель может считать закрытую область стираниями, а случайные повреждения исправить труднее, потому что декодеру сначала нужно их найти.
- Неизвестные ошибки: до половины числа кодовых слов EC
- Стирания (известные позиции): до числа кодовых слов EC
- Поле: GF(256), многочлен 0x11D
- Блоки перемежаются, чтобы распределить серийные повреждения