Код Рида-Соломона - это недвоичный код, один из очень немногих нетривиальных кодов МДР (т.е. кодов удовлетворяющих с равенством границе Синглтона, что означает, что минимально расстояние этого кода на 1 больше чем число проверок, иными словами каждая проверка участвует в создании минимального расстояния). Существует, по крайней мере, два способа интерпретации: как полиномиальный код (именно так он вводится в исходной статье И. Рида и Г. Соломона) и как частный случай кода БЧХ. Первый способ самый простой: если взять полином степени не выше k-1 над конечным полем (или расширением конечного поля), то кодом Рида-Соломона (n,k,d=n-k+1) называется набор значений такого полинома во всех точках поля (в этом случае n=q) или во всех точках за исключением 0 (n=q-1).
Как “работает” код, во многом зависит от того, как Вы его используете: для декодирования ошибок и стираний (или только ошибок) – способ который используется в системах связи и некоторых системах хранения данных (таких как Blue-Ray) или для исправления только стираний (как это делается в некоторых криптографических приложений и многих системах хранения данных, таких как облачные хранилища, пиринговые сети и дисковые массивы ). В последнем случае можно считать, что декодирование сводится к решению уравнений соответствующих нестертым символам (но на практике этот подход не используется т.к. эта процедура имеет сложность порядка куба от числа уравнений в системе). В общем случае (декодирования ошибок и стираний) декодирование требует решения нелинейных уравнений в поле. Для решения этой задачи вводится вспомогательный многочлен локаторов. В общем случае декодирование состоит в отыскании коэффициентов многочлена локаторов , факторизации этого многочлена (нахождения корней по которых определяются позиции ошибок (позиции стираний известны)), нахождении значений символов на позициях ошибок и стираний. Существует множество алгоритмов декодирования, которые по разному подходят к каждому из этих этапов (некоторые из них могут опускаться , так для декодирования одних стираний локаторы находить не надо): алгоритм Берлекампа-Месси, алгоритм Сугиямы (он же расширенный алгоритм Евклида), спектральные методы, основанные на использовании преобразования Фурье, алгоритмы, основанные на интерполяции полиномов (вроде алгоритма Гурусвами-Судана) и т.п.