для / = 2+ 1, п -{-2t, где п = q" - 1. Число различных корней многочлена Л (х) в поле GF {q"") равно степени этого многочлена тогда и только тогда, когда En+j)) = Ej для всех j = = 1, 2t.

Доказательство. Предположим, что число различных корней многочлена Л (х) в поле GF {q") равно его степени. Тогда Л (х) делит х" - 1 и существует многочлен Л" (х), такой, что Л° (х) Л (х) == х" - 1. Следовательно, так как

1] AEj = О,

то выполняется равенство А (х) Е (х) = О, и, таким образом, Л" (х) Л (х) £ (х) = (х" - 1) £ (х) = 0. Отсюда вытекает, что Е; = £((„+/)) для всех /.

Обратно, предположим, что Е] = Еп+п) Для всех /. Тогда (л:" - 1) Е (х) = 0. Но по условию Л (х) представляет собой такой ненулевой многочлен наименьшей степени, что Л (х) Е (х) = = О (mod X" - 1). Согласно алгоритму деления

(х"- l) = A(x)Q(x) + r(x),

так что

(х" - 1) £ (х) = Л (X) Е (X) Q{x) +г (х) Е (х).

Следовательно, г (х) £• (х) = О (mod х" - 1). Но степень г (х) меньше степени Л (х), так что многочлен г (х) должен быть равен нулю. Следовательно, многочлен Л (х) делит х" - 1 и все его корни являются корнями многочлена х" - 1. □

Если нарушается хотя бы одно из двух условий, т. е. если £j Ф £((«/)) для некоторого / или En+j)) ф Ej для некоторого /,

то обнаруживается конфигурация более чем из t ошибок.

Иногда желательно декодировать за пределами конструктивного расстояния. Небольшое продвижение за конструктивное расстояние дает продолжение алгоритма Берлекэмпа-Месси после 21 итераций. Основная идея состоит во введении дополнительных неизвестных синдромов (или дополнительных невязок) и аналитическом продолжении алгоритма декодирования, при котором многочлен ошибок вычисляется как функция от этих неизвестных. Затем, придавая этим неизвестным различные возможные значения, методом проб и ошибок в поле символов кода разыскивается вектор ошибок минимального веса. К сожалению, сложность этого метода очень быстро растет с отходом от конструктивного расстояния, так что его можно использовать не всегда.

Тем не менее описанный выше метод применим во многих случаях; укажем некоторые из них.

1. Двоичные коды БЧХ, у которых проверочные частоты образуют блок длины 2t, но истинное минимальное расстояние превосходит 2 i -Ь 1 • (Одним из примеров такого кода является код Голея. Другой пример дается (127, 43, 31)-кодом БЧХ, конструктивное расстояние которого равно только 29.)

2. Циклический код, проверочные частоты которого не образуют непрерывного блока.

3. Декодирование некоторых ошибок веса -- 1 в коде Рида- Соломона или коде БЧХ, исправляющем t ошибок.

4. Декодер для альтернантных кодов.

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

Начнем с рассмотрения кода Рида-Соломона над GF (q) с конструктивным расстоянием 2--1- Произвольный многочлен Л (х) степени t v с t + v различными корнями в GF (q) представляет собой допустимый многочлен локаторов ошибок, если

"ЁлЛ- = 0. r=l+/ + v, 2/.

Такой многочлен наименьшей степени с Ло = 1 (если он является единственным) соответствует кодовому слову, находящемуся на наименьшем расстоянии от принятого слова. Если степень этого многочлена не выше t, то он будет вычислен алгоритмом Берлекэмпа-Месси. Но даже если произошло больше, чем ошибок, а многочлен наименьшей степени с указанными свойствами является единственным, то принятое слово может быть однозначно декодировано, коль скоро этот многочлен найден. Для кода Рида- Соломона нет необходимости вычислять величины ошибок, так как ошибки всегда лежат в поле GF (q). Если многочлен наименьшей степени не является единственным, то имеется несколько возможных конфигураций ошибок одного и того же веса, и все они согласуются с принятым словом.

Предположим, что произошло t + I ошибок; тогда, чтобы вычислить Л {х), достаточно найти две неизвестные компоненты синдрома 52+1 и 52+2 или две невязки A2;+i и А2;+2.Итак, продолжим аналитически алгоритм Берлекэмпа-Месси на две итерации с двумя неизвестными значениями невязки. Имеем

(2t+2)

А2;+5б2;+2

- Д2;+2Л

. A2;Vl2if+l

- A2;+lX 62+1 X .

Л< (X)

где неизвестные удовлетворяют условиям 211, A2i2 € GF (q); 2t+i, 2t+2 6 0, 1. Bee остальные величины в правой части известны по 2 синдромам. Преобразование частотной области во временную дает

y{2t+2) l){2t+2)

A2t+22i+2

- Аг+гИ б2;+2а~

1 - Aa+ia

A2;4-l62;+I 62;+ia

где мы воспользовались тем фактом, что если Ej - Ej-\, то обратное преобразование удовлетворяет равенству е] = aei. Теперь, если возможно, мы должны выбрать неизвестные так, чтобы вектор ошибок содержал не более / -Ь 1 ненулевых компонент. Рассмотрим два возможных случая ):

(1) = ЯР" - Л,а--ЬР" - A2a-W\

(2) = If - A,a-bf - A.jx-V\

где в первом случае Ау и А.2 - константы, не равные одновременно нулю, а во втором случае Ау отлично от нуля. При Яр"" = О каждое из этих уравнений надо разрешить относительно А и А для ровно t + 1 значения индекса /. Это даст локаторы -Ь 1 ошибок, и дальнейшее декодирование может быть завершено как декодирование стираний.

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

Имеются в виду две возможности, задаваемые уравнением для первой компоненты предыдущего векторного равенства при Sgj+x = 0 и Ьц-г ~ соответственно. - Прим. перев.