Коды Рида-Соломона: Полиномиальная алгебра против искажения данных

В отличие от простых кодов Хэмминга, которые оперируют отдельными битами и спасают от одиночных ошибок, Коды Рида-Соломона (RS-коды) оперируют целыми символами (байтами). Это делает их непревзойденными лидерами в борьбе с пакетными ошибками (Burst errors), когда помеха уничтожает сплошной кусок данных (например, широкая царапина на диске повредит тысячи бит подряд, но это будет всего лишь пара сотен байт для RS-кода).

Глубокая математика кодов Рида-Соломона основана на вычислениях в конечных полях Галуа (GF). Алгоритм кодирования рассматривает исходный блок полезных данных (например, 223 байта) как коэффициенты большого многочлена. Этот информационный многочлен умножается на специальный порождающий полином с помощью модульной алгебры полей Галуа. В результате деления с остатком генерируются проверочные символы (например, 32 байта), которые дописываются в конец блока.

Математическое свойство этой алгебры таково: чтобы исправить t неизвестных ошибок (когда мы не знаем ни позицию ошибки, ни её значение), коду требуется добавить 2t проверочных байт. Код RS(255, 223) может безошибочно восстановить любые 16 поврежденных байт (из добавленных 32 проверочных) в любом месте блока.

Процесс декодирования (восстановления) — это высший пилотаж дискретной математики. Когда компьютер читает поцарапанный диск, он:

1. Вычисляет синдромы — проверяет, делится ли принятый многочлен на порождающий полином без остатка. Если делится — ошибок нет.
2. Если есть остаток, применяется Алгоритм Берлекэмпа — Мэсси для вычисления "полинома локаторов ошибок" (он находит точные позиции испорченных байт).
3. Затем используется алгоритм Форни, который вычисляет сами значения ошибок (разницу между правильным и искаженным байтом) и вычитает их, восстанавливая исходный файл.

Коды Рида-Соломона сегодня повсеместны. Они защищают жесткие диски RAID-массивов, используются в стандартах сотовой связи, ADSL, DVB-телевидении и являются главной причиной, по которой QR-коды с напечатанными поверх них логотипами компаний продолжают считываться сканерами.