ВИЯМ теоремы. Выпишем последний шаг алгоритма Евклида в форме, приведенной в доказательстве следствия 7.7.2:

х" - 1 L Е{х) J

= (-1)

НОД[х"- 1, E{x)\ 0

Отсюда видно, что (-1)22* (л:) = Л (л:). Вместе с тем в прямой форме последнее равенство имеет вид

A[f\x) А[\х)

"НОД[х"- 1, Е{х)\ О

что приводит к требованию

А\х) Ai\x)\

х" - 1 L Е{х) J

О = (-l) f> ix) (х" - 1) -ь Л (X) £ (х).

Следовательно, многочлен Л (х) Е (х) кратен многочлену х" - 1. Таким образом, многочлен Е (х) имеет корни в тех точках поля GF iq"), в которых не имеет корней многочлен Л (х). Поскольку степень многочлена Л (х) не превосходит t, то он имеет не более t нулей. Тогда компоненты et обратного преобразования Фурье обращаются в нуль по меньшей мере п - t раз. Согласно границе БЧХ, должен найтись такой вектор е, преобразование Фурье которого совпадает с известными коэффициентами многочлена Е (х) в позициях j = п - 2t, п - 1. Это завершает доказательство теоремы. П

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

Рассмотрим алгоритм деления

S (х) = Q (X) t(x) -{-г (х),

где deg t {х) = а и deg s (х) = b.B этом алгоритме степень частного Q (х) равна Ь - а и сам многочлен-частное Q (х) зависит от t (х) только через коэффициенты 4. ta-i, h-a- Для вычисле-

9.1. СПЕКТРАЛЬНЫЕ МЕТОДЫ ДЕКОДИРОВАНИЯ 293

Вычисление синйрома л-1 ..

£у= Z aJv, j=n-2t.....п-1

Q{x) =

Hx) =A22 (X)

S(X)

A(x) ~

J -Qix)

1 -Q(x)

"~Г"

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

; = 0,...,л-2М

ВыхоО

Рис. 9.3. Декодер для кодов БЧХ, основанный на алгоритме Евклида.

ния Q (х) воспользуемся следующей итеративной процедурой при г = О, Ь - а:

Qb-a-r =

b-r ~ 2j Qb-a-lf.,+J-r

Данный алгоритм является слабой модификацией обычного алгоритма деления многочленов.

Используем эту процедуру вычисления частного на каждом игаге алгоритма Евклида. В г-й итерации теоремы 7.7.1 вычислим только коэффициенты sY~ и ty~ для значений у от п - 2

+ Ij/=i deg Q (x) до n - 1. Эти старшие фрагменты многочленов s""* (ж) и (х) являются именно теми многочленами, которые необходимы для выполнения итерационных шагов алгоритма Евклида при построении рассматриваемого ряда многочленов-частных. Так как

Н0Д[х"-1, Е{х)] О

о г

/=д-1

х" - 1 L Е{х) J

то можно записать

/=r-iL 1 о

НОД[х"- 1,Е{х)] О

Поскольку степень НОД [л:" - I, Е (х)] равна по меньшей мере п - t, отсюда следует, что степень многочлена (х)

равна по меньшей мере п - t + 1f=r+i deg Q\x). Таким образом tf" известны для всех / от / = п - 2 -j- J][=i deg Q" (x) до n - 4- J]f=r+i deg Q (x) при ненулевом верхнем индексе. Этого диапазона достаточно для вычисления (х) и продол-

жения итерации.

9.2. ИСПРАВЛЕНИЕ СТИРАНИЙ И ОШИБОК

Контролирующие ошибки коды могут быть использованы в каналах, в которых кроме ошибок происходят и стирания. Принятое по такому каналу слово состоит из входных символов канала (часть из них может быть ошибочными) и пробелов (или эквивалентных символов), обозначающих стирания. Декодер должен исправить ошибки и восстановить стертые символы. Код с минимальным расстоянием d* позволяет декодировать любую конфигурацию, содержащую v ошибок р стираний, при условии, что

d* 2v +1 -f p.

Наибольшее v, удовлетворяющее этому неравенству, обозначим через tp.

Чтобы декодировать принятое слово с р стираниями, необходимо найти кодовое слово, которое в нестертых позициях отличается от принятого слова не более чем в tp символах. Поскольку