11.8. УСКОРЕННОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ

Сейчас мы рассмотрим применение разработанных в предыдущих параграфах методов для построения ускоренного декодера. Достаточно рассмотреть только примитивные кода Рида-Соломона. Коды БЧХ и непримитивные коды Рида-Соломона декодируются таким же образом. Исправляющий ошибок примитивный код Рида-Соломона длины представляет собой

множество всех кодовых слов длины для которых последовательных компонент спектра равны нулю.

Работа декодера основывается на преобразовании Фурье принятого слова . В типичных случаях сложность преобразования Фурье имеет порядок

Равенство нулю последовательных компонент спектра С определяет компонент синдрома Многочлен локаторов ошибок

где число действительно произошедших ошибок, удовлетворяет равенствам

Эта свертка задает систему из уравнений относительно неизвестных, из которых I составляют коэффициенты многочлена являются компонентами вектора Из этих уравнений уравнений связывают только известные компоненты вектора с неизвестными коэффициентами многочлена Используя алгоритмы свертки сложности и описанный в предыдущем параграфе рекуррентный алгоритм Берлекэмпа-Месси, можно разрешить эти уравнения относительно неизвестных компонент со сложностью, не превосходящей Остальные компоненты вектора можно рекуррентно вычислить по полученному и известным компонентам вектора в соответствии с равенстаом

Вычислив таким образом для всех находим компоненты спектра кодового слова согласно равенствам Обратное преобразование Фурье завершает декодирование.

Для вычисления требуется умножений, так что сложность этих вычислений имеет порядок . В оставшейся части этого параграфа мы покажем, как свести вычислительную сложность этого шага к величине, не превосходящей

В варианте Месси алгоритма Берлекэмпа-Месси спектр вектора ошибок рассматривается не только на интервале длины но и периодически продолжается вне этого интервала. Соотношение между многочленами и имеет вид

Преобразование Фурье этой циклической свертки приводит к равенствам

Во временной области эти равенства приводят к неопределенностям, так как решения записываются в виде когда таком виде эти равенства решать нельзя.

Берлекэми подходит к алгоритму декодирования несколько иначе. С точки зрения Берлекэмпа, выход регистра сдвига является периодическим только после начального перехода. В начальный момент времени регистр пуст и в него вводится известный многочлен Уравнения записываются в виде

и возмущения равные нулю при переводят регистр сдвига из начального состояния в описанное выше периодическое состояние.

Спектральный многочлен для вектора ошибок удовлетворяет уравнению

Многочлен можно вычислить с помощью рекуррентного алгоритма без увеличения асимптотической сложности, после чего можно вычислить с помощью деления многочленов. Но сложность последнего шага также растет как Так как выписанное выражение не является ни конечным, ни периодическим, то непосредственное применение метода преобразований невозможно. Можно, однако, воспользоваться для решения задачи алгоритмом Форни. По имеющемуся вычислим

и формальную производную многочлена Затем, применив к многочленам и обратное преобразование Фурье, вычислим векторы с компонентами Тогда, если равны нулю, решение дается (см. задачу 11.5) равенствами

Так как алгоритм Форни можно реализовать с помощью трех алгоритмов преобразования Фурье и алгоритма свертки, то получаем сложность