Б ЭТОМ хвосте ошибок. Предположим, что эта проверка на четность указывает на ошибку. Тогда во внутреннем векторе содержится не более t- 1 ошибок. У нас имеется 2t~ 3 внутренних компонент синдрома. Это позволяет исправить t-2 и обнаружить t- 1 ошибок во внутреннем векторе. Если во внутреннем векторе обнаружено t- 1 ошибок, то символ v ошибок не содержит, величина Sq является правильной и может быть использована для еще одной итерации при вычислении многочлена локаторов t- 1 ошибок. Это завершает декодирование в случае, когда проверка на четность в символе v+ указывает ошибку.

В противном случае, когда проверка на четность в символе не указывает ошибки, в этом хвосте имеется четное число ошибок. Тогда для иЙ1равления t- 3 ошибок во внутреннем векторе выполним, начиная с Si, 2i-6 итераций алгоритма Берлекэмпа- Месси (используя тем самым 2t - 3 компонент внутреннего синдрома) и зарезервируем остальные три итерации для обнаружения t или меньше ошибок во внутреннем векторе. Если t- 3 ошибки не исправились, то внутренний вектор содержит t- 2, или t- 1, или ошибок, и, следовательно, граничные символы содержат не более двух ошибок. Следовательно, либо правилен, либо содержит две ошибки, а w правилен.

Хотя бы одна из граничных компонент синдрома правильна. Присоединим S i или Sq к одному концу внутреннего синдрома и S2; i или S2( к другому концу. Это даст нам два синдрома с 2t- 1 компонентами, хотя бы один из которых правилен. Для каждого из синдромов воспользуемся алгоритмом Берлекэмпа- Месси для исправления t- 1 и обнаружения / ошибок во внутреннем векторе. Если во внутреннем векторе содержится t ошибок, то оба синдрома должны указать на это, и в таком случае граничные символы не искажены. Если одна или обе попытки декодирования не обнаруживают во внутреннем векторе t ошибок, то в нем содержится не более t- 1 ошибок и тогда вычисленный многочлен локаторов ошибок является правильным и позволяет завершить декодирование.

Наконец, если во внутреннем векторе обнаружено t ошибок, то в граничных символах оишбок нет и в нангем распоряжении имеются 2t-\- I компонент синдрома, позволяющих исправить i ошибок.

9.5. ДЕКОДИРОВАНИЕ ВО ВРЕМЕННОЙ ОБЛАСТИ

В § 9.1 было показано, что задача декодирования кодов БЧХ может быть сформулирована как задача спектрального оценивания Декодер состоит из преобразователя Фурье (вычислителя синАрома), авторегрессионного спектрального анализатора (алго-

9.5. ДЕКОДИРОВАНИЕ BO ВРЕМЕННОЙ ОБЛАСТИ 305

ритма Берлекэмпа-Месси) и обратного преобразователя Фурье. Задание декодера такими блоками облегчает его исследование, однако практическая реализация декодера может существенно отличаться от этой схемы.

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

Чтобы исключить из вычислений преобразование Фурье, при.меним это преобразование ко всем величинам, входящим в формулировку теоремы 7.4.1. Преобразование вектора Л, обозначающее вектор локаторов ошибок во временной области, обозначим через ) = {Kili = О, п- 1}. Преобразование вектора В обозначим соответственно через b = j&j 11 = О, п-1}.

.Алгоритм Берлекэмпа-Месси превращается во временной области в рекуррентный процесс, который описывается следующей теоремой.

Теорема 9.5.1. Пусть v - принятое зашумленное слово кода БЧХ, и пусть величины t = О, п- 1, вычисляются

с помощью рекуррентных уравнений

А, = "fa4M0.

L, = б, (г - L, i) f 6,L, i,

1 ~- A,a

где г = 1, 2t, начальные условия ижют вид = 1, bf = 1 для всех i, а б,, = (1 - б,.) = 1, если одновременно ¥= О и 2Ь,. 1 <г - 1, и 6 = 0 в противном случае. Тогда kf* = О тогда и только тогда, когда Ф 0.

Доказательство. Применим преобразование Фурье ко всем входящим в формулировку теоремы векторным величинам. Тогда все рекуррентные уравнения запишутся в виде, указанном в фор-

Принятое слово

Un-3,Vn-Zin-\

Буфер

Койовое иоео

Алгоритм Берлекзмпа-месси 60 временной области

Буфер

/1окаторы ошибок

Рис. 9.6. Временной декодер для двоичного кода БЧХ.

мулировке теоремы 7.4.1, за исключением уравнения для невязки

в котором вместо вектора S стоит вектор V. Но Af~ - О для />2< и = Sj- для /= 1, It. Следовательно,

Д, = "Е АГ5, ,.

и алгоритм во временной области формулируется аналогично теореме 7.4.1. □

Так как в двоичном случае t-я координата принятого слова содержит ошибку тогда и только тогда, когда = О, то с вычислением вектора 1- исправление ошибок почти заканчивается. Декодер для двоичного кода с декодированием во временной области показан на рис. 9.6.

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

£fc = - i] A,£ft ,., /г =-2/-И.....п-1.

Как только многочлен локаторов ошибок вычислен, можно согласно этой рекурсии по известным It компонентам вектора Е вычислить все остальные его компоненты, проведя п -2 итераций.

Следующая теорема описывает соответствующий этому процесс во временной области. В этом случае нельзя просто воспользо-