11.8. VcKOPEHHOE ДЕКОДИРОВАНИЕ КОДОВ БЧХ 391

принимает наибольшее значение при /, равном нулю для всех logst значений.

Граница асимптотической сложности алгоритма зависит от асимптотической сложности вычисления свертки в полях Галуа. Напомним, что в алгоритме Винограда вычисления свертки требуется по возможности наличие простых делителей над полем GF (р)- Для минимизации числа умножений показатели степени этих делителей надо выбирать малыми. Но если п велико, то может не оказаться достаточного числа многочленов малой степени и будет необходимо воспользоваться многочленами степени порядка log п. Это приведет к замене свертки длины п некоторым количеством сверток, наибольшая длина которых имеет порядок log п. Этот же процесс приведет к замене свертки длины log h некоторым количеством сверток меньшей длины, самая длинная ИЗ которых имеет порядок длины, равный log (2 log n). Формализуя это рассуждение, можно сказать, что асимптотическая сложность вычисления свертки в поле Галуа равна величине О (n2°s*"), где log* п - число, показывающее, сколько раз надо последовательно проинтегрировать логарифм по основанию 2, начиная с п, для того, чтобы получить число, не превосходящее единицы. Таким образом

logg (logg (... (loga n))) < 1,

и число шагов в этом итеративном процессе равно log* п. Величина 2°s*n стремится к бесконечности медленнее, чем итерированный любое число раз логарифм.

Лучшая известная граница числа С (п) имеет вид О (п2°8*п) и, следовательно, сложность рекуррентного алгоритма Берлекэмпа-Месси оценивается величиной О (n2°s*« log п). Таким образом, сложность рекуррентного алгоритма Берлекэмпа-Месси больше, чем О {п log п), но очень близка к этой границе.

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

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

) Напомним, что автор называет примитивными кодами Рида-Соломона коды над Gf длины п = -1, а непримитивными ~ коды, длина которых делит это п. -Прим. перев.

множество всех кодовых слов длины п нгд GF (q), для которых 2t последовательных компонент спектра равны нулю.

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

Равенство нулю 2t последовательных компонент спектра С определяет 2t компонент синдрома 8,- = Е,- = V,-, j = I, 2t. Многочлен локаторов ошибок

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

1а,е, 1 = о.

Эта свертка задает систему из п уравнений относительно п - t неизвестны, из которых t составляют коэффициенты многочлена Л (х), а п - 2t являются компонентами вектора Е. Из этих п уравнений t уравнений связывают только известные компоненты вектора Е с неизвестными коэффициентами многочлена Л (л:). Используя алгоритмы свертки сложности п logg п и описанный Б предыдущем параграфе рекуррентный алгоритм Берлекэмпа- Месси, можно разрешить эти уравнения относительно неизвестных компонент Л со сложностью, не превосходящей О (п log; п). Остальные компоненты вектора Е можно рекуррентно вычислить по полученному Л и известным компонентам вектора Е в соответствии с равенством

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

Для вычисления Ej, / = 2/+ 1, п, требуется п (п - 2t) умножений, так что сложность этих вычислений имеет порядок п. В оставшейся части этого параграфа мы покажем, как свести вычислительную сложность этого шага к величине, не превосходящей О (п logg п).

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

Е [х) а{х) = 0 (mod л« - 1).

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

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

eki = О, f = О, п-1.

Во временной области эти равенства приводят к неопределенностям, так как решения записываются в виде ei = О/Х и = О, когда =7 0. В таком виде эти равенства решать нельзя.

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

= - i ЛД,., + •

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

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

Е {х) Л {х) = Q{x).

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

Q{x) = Е {х) Л ix) (mod х)

и формальную производную Л [х) многочлена А {х). Затем, применив к многочленам Л (л:), Q [х) и Л (х) обратное преобразование Фурье, вычислим векторы с компонентами Xj, to. и Xl. Тогда, если равны нулю, решение дается (см. задачу 11.5) равенствами

ei = - соД,.

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