Построение начнем с более компактной организации алгоритма Берлекэмпа-Месси. Заменим многочлены Л<> (х) и В<") (х) (2 X 2)-матрицей из многочленов

> [ Л) (х) (х). •

Для обозначения элементов матрицы Л<) (х) нам понадобится несколько индексов; символ Л<) . будет означать j-и коэффициент многочлена, стоящего на пересечении строки а и столбца b в г-й итерации.

Напомним, что вычисления алгоритма Берлекэмпа-Месси основываютсяна двух равенствах:

Л--) (х)

1 -А,х 1 Г (х)

Второе равенство можно записать в виде

Определим матрицу Л**") {х) равенством

Через эту матрицу можно выразить многочлены Л<) [х) и (х):

= Л<-) {х)

Л) (х) + ЛИ (X) LAH(x)~fA<?) (X)

Полученное равенство может быть использовано как для вычисления Л<) [х), так и для вычисления многочленов Л) {х) и B*" [х). Непосредственное вычисление матрицы Л< [х) содержит вдвое больше умножений, так как вместо двух элементов в вычислениях участвуют четыре. Поэтому замена итераций многочленов Л) (д;) и В*") [х) итерациями матрицы Л*" (х) удваивает необходимое число умножений. Это ухудшение будет затем устранено реорганизацией вычислений.

В перестроенном виде алгоритм Берлекэмпа-Месси основывается на двух уравнениях, а именно на уравнениях

А.=5 л1г;5. ;+Is л}г;х-/

/=0 /=0

Л--) (X) =

1 -АгХ А;дг (1 -S)x.

Теперь мы хотим уменьшить число вычислений, группируя итерации в пакеты. Определим матрицу

I -

[ А;б, (1 - S,) X J

М*--) (х) =

так что

Л«) (X) = МС) (х) (х) ... М<) (х).

Это произведение должно вычисляться последовательно по одному члену, начиная справа, так как М*) (х) нельзя вычислить до тех пор, пока не вычислена Л-> (х).

Определим следующие частичные произведения рассматриваемых матриц:

Л(г. Г) (х) = МС) (х) М-1) {X) ... М(-+1) (X);

тогда

АС) (х) = АС-.о) {х)

А<-) (х) = А*-- ) (х) Л"") (х).

Определим также вектор модифицированных синдромных многочленов S*) (х):

S(x) [S(x)j

S(-) (х) = Л() (х)

= А(- (х) S<) (х).

Невязка

/=0 /=0

становится равной г-му члену свертки и может быть записана через многочлены:

А (X) = Air" (х) 5 (X) -L Л1Г" W 5 (X) =

= [АГWЛ}Г> (х) + Л1Г-W А;> (х)] S (X) +

+ [Air - WAir (х) f Air- (х) AiP ix)] S (X). Группируя члены, получаем

А (х) = Air- (х) [aV (х) S (X) I- А{Г (X) S (х)] +

j- Air- (X) [Ar W S (X) 1- (X) S (X)].

Стоящие в квадратных скобках многочлены являются компонентами вектора S*") {х) модифицированных синдромных многочленов. Следовательно, выражение для невязки можно переписать Б виде

где Si/ и Ss/ обозначают соответственно /-е коэффициенты многочленов в первой и второй компонентах вектора S**") (х). Для ускорения алгоритма Берлекэмпа-Месси сформируем пакеты но т итераций в каждом. Если т делит 2/, то обращение к каждому из 2 т пакетов одинаково. В противном случае последний пакет содержит меньше т итераций, но мы полагаем его таким же. Индекс г теперь пробегает значения

г = 1, 2, т, т -f 1, 2т, 2т -f 1, Зт,

Зт + 1, ... .

На г-й итерации -го пакета модифицированный алгоритм Берлекэмпа-Месси вычисляет А**"- [х) согласно равенству

1 -

[А;б, {\-Ь,)х\

где г = /гт, а Д вычисляется по формуле

В конце -го пакета, когда г равно (k -f 1) т, матрица локаторов ошибок и вектор модифицированных синдромных многочленов даются соответственно равенствами

А() {х) = Л(- {х) Л() {х) и S(-) (х) = Л(. (х) SC") (х),

где г = kx к г {k + \) X. Теперь ускоренный алгоритм готов начать {k + 1)-й пакет.

На рис. 11.7 приведена блок-схема ускоренного алгоритма Берлекэмпа-Месси с некоторыми очевидными сокращениями. В левой части рисунка приведен стандартный алгоритм, расписанный для т итераций, а в правой показаны блоки, осуществляющие связку пакетов по т итераций каждый. Если правая часть алгоритма выполняется так, как она выписана, то мы не получаем никакой экономии вычислений. Однако умножения многочленов в блоках правой части эквивалентны сверткам, которые могут быть эффективно вычислены с помощью описанных в § 11.1 и 11.3 методов или с помощью быстрого преобразования Фурье и теоремы о свертке. Некоторые возможности иллюстрируются следующим примером.