3.3. Архитектура кодирования и декодирования кодов Рида-Соломона

Кодирование и декодирование кодами Рида-Соломона может осуществляться в программном обеспечении или в специальной аппаратной реализации.

Конечные (Галуа) арифметические поля

Коды Рида-Соломона основаны специальной области математики известной как поля Галуа или конечные поля. Конечное поле использует такие же операции, как и в арифметике (+,-,x,/ и т.д.), которые оказывают влияние на элементы поля и образуют результат. Для кодера и декодера Рида-Соломона необходимо выполнять эти же арифметические операции. Эти операции требуют специального оборудования или программного обеспечения для осуществления функций.

Полиномиальный генератор

Кодовое слово кода Рида-Соломона формируется с помощью специального многочлена. Все допустимые кодовые слова делятся на порождающий полином. Общий вид генератора многочлена:

и кодовое слово построено с помощью:

c(x) = g(x).i(x)

где g(x) является генератором многочлен, i(x) информационный блок, c(x) является действительным кодовым слово и называется примитивным элементом поля.

Пример: Генератор для RS(255,249)

3.1 Архитектура кодера

Паритетные символы 2t в систематическом кодовом слове Рида-Соломона, определяются по формуле:

Следующая диаграмма показывает архитектуру для систематического RS(255,249) кодера:

Каждый из регистров имеет 6 символов (по 8 бит). Арифметические операции осуществляют ограниченное дополнение поля или умножение на полный символ.

3.2 Архитектура декодера

Общая архитектура для декодирования кодов Рида-Соломона показано на следующей диаграмме.

r(x)	Поступившее кодовое слово
Si	Синдром
L(x)	Полином локализатора ошибки
Xi	Место ошибок
Yi	Ошибка в количестве исправляемых ошибок
c(x)	Восстановленное кодовое слово
v	Число ошибок

Поступившее кодовое слово r(x) является оригинальным (передаваемым) , кодовое слово c(x) -это оригинальное кодовое слово плюс ошибки:

r(x) = c(x) + e(x)

Поступившее кодовое слово r(x) является оригинальным (передаваемым) , кодовое слово с (х)-это оригинальное кодовое слово плюс ошибки: Декодер Рида-Соломона осуществляет попытку определить место и количество (до t) ошибок (или 2 t стирающих сигналов), а также исправляет ошибки или стирающие сигналы.

Расчёт синдрома

Это аналогичные вычисления паритетности расчёта. Кодовое слово Рида-Соломона имеет 2t синдромов, которые зависят только от ошибки (кодовое слово не передаётся). Синдромы могут быть рассчитаны путём замены 2t порождающего полинома G (х) на корни R (X).

Поиск месторасположения ошибочного символа

Это предполагает решение системы уравнений с t неизвестным. Некоторые алгоритмы могут сделать это быстро. Эти алгоритмы используют специальную матричную структуру кодов Рида-Соломона, что значительно сокращает требуемые вычислительные нагрузки.

Поиск ошибки полиномиальным локатором

Это может быть сделано с помощью алгоритма Берлекэмпа-Мэсси или алгоритма Евклида. Алгоритм Евклида имеет тенденцию быть более широко использующимся на практике, поскольку его легче осуществить: однако, алгоритм Берлекэмпа-Мэсси как правило, приводит к более эффективным аппаратным и программным реализациям.

Поиск корней этого полинома

Для этого используется алгоритм поиска Чин.

Поиск значения ошибки в символе

Опять же, для этого предполагает решение системы уравнений с t неизвестными. Для этого широко используется алгоритм быстрого поиска Форни.