Походження та ширше застосування
Коди Ріда-Соломона описали Ірвінг С. Рід і Густав Соломон у 1960 році. Вони працюють із цілими символами, зазвичай байтами, а не з окремими бітами, тому добре справляються з пакетами пошкоджень, як-от подряпина чи пляма.
Це саме сімейство кодів захищає дані на CD, DVD і дисках Blu-ray, у деяких цифрових телевізійних і супутникових лініях та в інших двовимірних штрихкодах, зокрема Data Matrix ECC 200, Aztec і 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
- Блоки перемежовуються, щоб розподілити пакетні пошкодження