О, / = L„j i,.. .,т-1,

Am =5 О, / = т,

и по предположению индукции

Ц-1 = -f-m = max [L„ ,, m - = m - L i,

поскольку L,„ > L„ i. Теперь выберем новый многочлен

Л< (X) = Л--" (х) - Л, Д-/-"Л<"--" (X)

и положим L,. = deg Л {х). В этом случае поскольку deg ДС-) (х) < и deg [х-А("-) (х) ] <: г - m + L-i, то

Lr < max [L,, ,, г - m -Ь £-m-i] < max [L,, i, r - L,. i].

Из последнего неравенства и леммы 7.4.2 при условии, что Л*) (х) генерирует S, S,., следует, что = max [Lj, г - Осталось доказать, что регистр сдвига (Lr, Л (х)) генерирует требуемую последовательность. Докажем это непосредственным вычислением разности между Sj и сигналом на выходе обратной связи регистра сдвига:

- i ЛГ5; ,] = Sri- £ЛГ"5; , -1=1 / £=1

- ДлД

Sj~r+m

О, ; = L„L,-f l,...,r-1,

Д, - ДлДтДт = О, i =r.

Итак, регистр (L, А<-"> (х)) генерирует 5i.....S,.; в частности,

(Lgt, Л(2> (х)) генерирует 5, Sgj. Лемма доказана. □

7.5. БЫСТРОЕ ДЕКОДИРОВАНИЕ КОДОВ БЧХ

Уяснение работы декодера Питерсона-Горенстейна-Цирлера - лучший путь к пониманию процесса декодирования кодов БЧХ. Но при построении декодера приходится жертвовать концептуальной ясностью во имя вычислительной эффективности. Они-

Если Дг = о, то регистр (L,..,, Л"- (х)) также генерирует первые г символов, и, таким образом,

L, == L, i и Л(0 (X) = Л--) (X).

Если Дг ф О, то необходимо построить новый регистр сдвига. Напомним, что изменение длины регистра произошло при к = т. Следовательно,

5. 4 2] А("-)5, , =

AM = n(l--vX,).

Определим синдромный многочлен

и многочлен значений ошибок Q, (х):

Q (х) = 5 (х) Л (X) (mod xt).

Многочлен значений ошибок будет иногда использоваться в дальнейших рассуждениях. Его связь с локаторами и значениями ошибок устанавливается следующей теоремой.

Теорема 7.5.1. Многочлен значений ошибок можно записать в следуюием виде:

Доказательство. Из определения сомножителей, входящих в равенство для Q (х), получаем

г 2t V

fi(x) =

Ii I YXixl- L/=i i=i

Uil-XiX) (modxO =

Li=l

= I YiXi

(1 - XiX) I {XiX)~ П (1 - ix) (modx20-

санный в § 7.2 декодер Питерсона-Горенстейна-Цирлера предполагает обращение двух матриц размера t X t. Хотя обращение матрицы в конечном поле не приводит к ошибкам округления, вычислительная работа, особенно для больших значений /, может оказаться чрезмерно большой. В то же время обращения обеих матриц можно избежать. Обращение первой матрицы, необходимое для вычисления многочлена локаторов ошибок, можно обойти, используя алгоритм Берлекэмпа-Месси. Обращение второй матрицы, необходимое для вычисления значений ошибок, можно обойти, воспользовавшись процедурой, носящей название алгоритма Форни. Этот параграф начнется с описания алгоритма Форни, а затем будет продолжено рассмотрение алгоритма Берлекэмпа-Месси.

Для описания алгоритма Форни нам понадобится многочлен локаторов ошибок

Л (л:) = Лл: Л.л:- + ... + Лх 4- 1,

имеющий кopн Xj\ I = I v:

Выражение в квадратных скобках является разложением для (1 -Xfx). Таким образом, •

Q(x)=t Y,X, (1 - П(1 - Xix) (mod

Последнее выражение, взятое по модулю х*, совпадает с выражением, которое требуется доказать. Тем самым теорема доказана.

□

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

Теорема 7.5.2 (алгоритм Форни). Значения ошибок получаются из равенства

n(i-/V) A-(V) •

Доказательство. Используя равенство из утверждения теоремы 7.5.1 при X = ХТ\ получим

й(хг) = УлП(1-/г).

откуда вытекает первая часть теоремы.

С другой стороны, производная многочлена Л (х) равна

л(х)=-1]х,П(1-Д

и, таким образом,

Л (хг) = -х,П(1-/г).

откуда сразу следует утверждение теоремы. □

Алгоритм Форни обладает существенным преимуществом перед обращением матрицы, но использует деление. В гл. 9 будет предложено другое решение, не использующее деление.

Теперь вернемся к вычислению многочлена локаторов ошибок, использующему алгоритм Берлекэмпа-Месси теоремы 7.4.1. Предложенный Месси вариант решения этой задачи показан на рис. 7.4, а. По заданным Sj, j = I, 2t, находится вектор Л минимальной длины, удовлетворяющий t уравнениям

Sj+ hsjnAk = 0, j = t-l,...,2t.

Это означает, что требуется по заданным 2t компонентам вектора S из свертки вычислить вектор А, если априори известно.