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

Q {х) = S {х) А {х) (mod хО

и условиями deg Л (х) < / и deg Q (х) t - 1. Постараемся теперь использовать доказательство алгоритма Евклида для решения этого уравнения относительно А (х) и Q (х). Из этого доказательства легко установить, что

-8С-){х)1ГА[[Цх) ЛИ(х)

./<)(x)J [аЦЦх) АЦх)

и поэтому

* ЦП = t (х) Ag> {х) (mod S (х)).

Если положить t (х) = S (х) и s (х) = х, то последнее равенство можно рассматривать как уравнение, которое нам необходимо решить. Это уравнение выполняется для каждого г. Чтобы решить поставленную задачу, необходимо найти такое значение г (если оно существует), при котором deg Л5> (х) <: / и deg (х) < < - 1. Удовлетворить последним условиям можно, выбрав г равным такому значению г, при котором

deg fC-i) {x)t и deg С) {х) <t-l.

Поскольку deg (х) = 2t и степень (х) строго убывает с возрастанием г, эти неравенства определяют единственное значение г.

По определению г получаем

deg/() (х) t~l.

Степень Л> (х) возрастает с возрастанием г. Остается лишь показать, что

degЛ<p(x)<Л

Это неравенство доказывается с помощью обращения матрицы А (х). Сначала напомним, что

О 1

*« = ,n ,L.-«<"WJ

откуда следует что deg Л(> (х) deg Л<5> (х). Напомним также, что deg s) (х) > deg(х). Из этих неравенств и матричного равенства

s(x) lt{x)j

= (-ir

AgHx) 1-А<[Цх)

-A[r>{x) А[[Цх)}

Г5<-)(л;) () (х).

вытекает, что degs (х) = deg А> (х) + degs<> (х), и, поскольку (х) = (х), получаем

deg Л() (х) = degs (х) - deg/(-i) (х) < 2/ - / =

где неравенство следует из определения г.

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

Теорема 7.7.3. Пусть заданы s° (х) = х"*, т (х) = S (х), где S (х) - синдромньсй многочлен кода БЧХ, исправляющего t ouiu-

- 1 О]

. Будем решать следующие ре-

бок, и пусть А(°> [х) =

куррентные уравнения до тех пор, пока не будет выполнено неравенство deg 6"> <; - 1:

AC+i) (X) = s(+) {х)

Тогда многочлены

С) {X)

О 1 1 -Q<> (х).

1 -Q(-{x)

t(-> (х)

Л(х) = д->лг>М,

где А = Л<Г (0), являются единственным решением, уравнения Q{x) = S{x)K{x) (modxO,

удовлетворяющим условия и deg Л (х) < Лц = 1 и deg Q (х) < < 1.

Доказательство. Деление на А обеспечивает равенство Ац = 1. С другой стороны, из предыдущих рассуждений следует, что последнее уравнение и все условия удовлетворяются. Единственность полученного решения вытекает из того факта, что для синдрома кода БЧХ, исправляющего t ошибок, существует только одно такое решение. □

После того как А (х) и Q (х) найдены, декодирование можно завершить любым из методов, предложенных для алгоритма Берлекэмпа-Месси. Блок-схема соответствующего декодера представлена на рис. 7.8, где декодер завершается алгоритмом Форни (хотя его можно завершить и иначе).

Вычисление компонент синйромо,

A{x) = Д-МггИ

Вычисление локатсров ошибок, с помощью вычисления корней А(х)

5(JC)

t(x) А(х)

.1 -Q(x)

1 ~0(х)

А(х)

Moc)=I.UAj)x-

Быхоо

Рис. 7.8. Дгкодирование кодов БЧХ при помощи алгоритма Евклида.

7.8. КАСКАДНЫЕ (ГНЕЗДОВЫЕ i)) КОДЫ

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

) Гнездовые (nested) коды называются также каскадными (concatenated) кодами, поскольку кодеры и декодеры для них группируются в каскады. Мы предпочитаем резервировать термин «каскадный» за каскадными кодовыми словами, которые выписываются одно за другим, образуя единую цепочку. [Поскольку в русскоязычной литературе по теории корректирующих кодов термин «гнездовые коды» вообще не применяется, а термин «каскадные коды» является общепринятым, мы будем везде пользоваться последним. - Яерее. ]