f-----т

Канал г г г

I-----!

Смешанная реализация: временной кобер гибрибный бекойер

; = 1,...,2<

Вычисление синбромй

Буферный регистр

К пользователю

Преобразование Фурье

Койер

Частотная реализация

Буферный регистр

Алгоритм Месси

-SH Канал i-* I I 1 J

Преобразование Фурье

Рекуррентное пройолкение

к пользователю

Смешанная реализация: временной койер частотный Оекобер

Буферный регистр

Алгоритм

Барлекзмпа-

Месси

Рекурришное проВолжение

ПрроВра-

Койер Канал зование

1 Фурье

I !

Смешанная реализация временной коВер частотный йекойер

Алгоритм Берлеиэмпа-Месси

Peityppmmioe пройолжеше

Буферный регистр

Рис. 9.2. Некоторые схемы кодера/декодера для кодов БЧХ.

Обратное

преобразование

Фурье

К пользователю

Обратное

преобразование

Фурье

It пользователи

ные алгоритмы вычисления преобразования Фурье. Помимо выбора алгоритма вычисления преобразования Фурье и способа реализации декодера конструктор может так модернизировать декодер, чтобы вычислять только часть спектральных компонент. Например, в четвертом варианте схемы декодера на рис. 9.2 требуется вычислить только It компонент спектра. Возможно

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

v(x) = Q(x)g{x) +s{x),

где g (х) - порождающий многочлен кода БЧХ, а s (х) - синдромный многочлен. Синдромный многочлен можно вычислить с помощью цепи деления на g (х). Тогда

S, = V («О Q (аО g (аО + s («О = s (а),

/==/о f I, ..-,/о + 2/,

так как для этих значений индекса / выполняется равенство g (а) = 0. Теперь компоненты синдрома могут быть вычислены как преобразование Фурье многочлена s {х), который имеет не п, а только п - k ненулевых коэффициентов. Этот метод оказывается полезным тоутько тогда, когда легче осуществить деление на g (х), чем вычислять преобразование Фурье в п входных точках. При малых значениях п это иногда имеет место.

Существует и другой алгоритм декодирования, основанный на алгоритме Евклида и совершенно отличный от описанного в § 7.7. Этот метод, ориентированный на частотную область, будет описан в данном параграфе.

В поле GF (<7") имеет место разложение

1 = П(х-а).

Определим истинно-локаторный многочлен Л" (х) = (л:" - l)/A{x). Он действительно является многочленом, так как Л (х) представляет собой произведение различных линейных множителей, каждый из которых делит х" - 1. Корни многочлена Л° (х) определяют правильные компоненты принятого вектора.

Теорема 9.1.1. Многочлен ошибок Е (х) и многочлен локаторов А (х) удовлетворяют равенству

HOJX[x" ~1, Е (х)] = (х" - 1)/Л (х) = Л» (х).

Доказательство. Многочлены Е (х) и А (х) не имеют общих корней, так как по определению Л (а) = О тогда и только тогда, когда Е (а) Ф 0. Каждый элемент a должен быть корнем либо Е (х), либо Л (х). Следовательно,

А (х) Е (X) Р (х) {X" - \)

ДЛЯ некоторого многочлена Р (х), взаимно простого с Л {х). Тогда

НОД [х" ~\, Е {х)] = (х" - 1)/Л (х) = Л» (х),

что и требовалось доказать. □

Применим описанный в теореме 7.7.1 алгоритм Евклида с S (х) = х" - 1 и t (х) = Е (х), временно игнорируя тот факт, что в общем случае известны только 2t старших коэффициентов многочлена Е (х). Поскольку

Л (х) НОД [х" - 1, Е (х)] = х" - 1,

то, согласно следствию 7.7.2,

A{x) = i-lfAi§{x)

определяет многочлен Лгг (х), вычисляемый в процессе выполнения алгоритма Евклида.

Если многочлен Е (х) известен, то с помощью алгоритма Евклида мы таким образом можем вычислить Л (х). Но нам известны только те коэффициенты многочлена Е (х), для которых соответствующие коэффициенты многочлена С (х) равны нулю, и, таким образом, на первый взгляд эта формула для Л (х) кажется бесполезной. На самом деле ее можно использовать и в том случае, когда известны лишь 2t коэффициентов многочлена Е (х), если только они правильны.

Рассмотрим код БЧХ, корнями порождающего многочлена которого являются элементы а"~..... а"~\ (Если использовать

в качестве примитивного элемента поля а-, то это обычные корни с показателями от 1 до 2t.) Построим алгоритм декодирования для такого кода БЧХ. Нам надо показать, что если произошло не более t ошибок, то итерации алгоритма Евклида зависят только от 2t старших коэффициентов многочлена Е (х). Остальные коэффициенты могут выбираться произвольно.

Теорема 9.1.2. Пусть заданы Ej для j = п - 2t, п - 1.

Тогда имеется не более одного способа задания Ej, fj = 0, ... n~2t-1, такого, что уравнение

А{х)НОЛ[х"~1, Е{х)] = х"~-1

разрешимо относительно А (х) степени t или меньше.

Доказательство. Доказательство теоремы показывает, что она является одной из форм границы БЧХ. Предположим, что степень многочлена Л {х) не больше / и что он удовлетворяет усло-10*