Генерация кодов Рида-Соломона для коррекции ошибок

Ирвин Рид и Густав Соломон впервые представили помехозащищенные коды, впоследствии названные кодами Рида-Соломона, в 1959 году [7]. В общем случае при генерации кодов Рида-Соломона используется перемножение и деление полиномов друг на друга. Например, если полином A это кодовое слово (сгенерировано на основе полученной на предыдущем этапе бинарной строки), а B это неприводимый полином, который известен обеим сторонам, обменивающимся информацией, тогда их перемножение сгенерирует новый полином C. Формально все полиномы могут быть определены следующим образом:

Отсюда следует, что когда передаваемое сообщение будет получено, процесс его декодирования будет заключаться в делении полиномов друг на друга. Если при делении полинома C на полином B остается остаток, значит, переданное сообщение содержит ошибку. Остаток от деления образует синдром полинома, благодаря которому можно узнать поврежденные биты. Кроме того в некоторых случаях можно исправить определенное количество ошибок в полученном сообщении. Если степень полинома B отличается от степени полинома A как минимум на 2, тогда возможно не только определить наличие или отсутствие ошибки в передаваемом сообщение, но так же и исправить некоторые из них. В этом случае, приведенное далее уравнение (где k — это степень полинома; t — это максимальное значение возможных исправлений) показывает, что избыточность кодов Рида-Соломона составляет:

k = 2 * t.

Процесс генерации кодов Рида-Соломона, их кодирования и декодирования, описан в приложении спецификации QR кодов [3]. В качестве результата генерации строки с помощью кодов Рида-Соломона для исходного сообщения, будет сгенерирован набор десятичных значений. Их необходимо преобразовать в бинарный формат и конкатенировать с исходной строкой с правой стороны. Результатом всех предыдущих этапов будет строка в бинарном формате, содержащая в себе исходные данные сообщения плюс коды Рида-Соломона, для того чтобы обеспечить возможность коррекции ошибок в декодированном сообщении.