Заметим, что У; 6 GF (q), а Xt, € GF ("). БЧХ-код с исправ-З лением t ошибок строится таким образом, что а, а, а, . . ., af являются корнями порождаюн1,его многочлена кода ) и, следова-1 тельно, корнями любого кодового многочлена. Таким образом, пер-] вым шагом процедуры декодирования БЧХ-кодов является вычис- ление суммы = Е {а) для к = i, 2, . . ., 2t.

Для определения местоположения и значений ошибок полезное ввести в рассмотрение два многочлена. Первый из них, а (z), так1 называемый многочлен локаторов ошибок, определяется, тем, что его корни взаимны к локаторам ошибок:

(10.11)

a{z)-W{i-Xtz).

Второй многочлен, co(z), так называемый многочлен значений ошибок,% задается равенством

(10.12)

{z)o{z)YljzXtYi П (1-Х,-2).

г 1ф1

Заметим, что определения 10.11 и 10.12 в двоичном случае сводятся к определениям 7.21 и 7.22. В противоположность многочлену локаторов ошибок для негациклических кодов, рассмотренных в гл. 9 многочлен локаторов ошибок (10.11) не имеет кратных корней.! Но степень многочлена локаторов ошибок (10.11) равна числу ошибок! в метрике Хэмминга, подобно тому, как степень многочлена локато- ров ошибок в гл. 9 равна числу ошибок в метрике Ли и степень! многочлена ошибок (7.21) равна числу ошибок в двоичном канале.! Отметим также, что многочлен значений ошибок (10.12) зависит! и от локаторов и от значений ошибок, в то время как многочлевд локаторов ошибок (10.11) зависит только от локаторов ошибок.!

Так как а (0) = 1, то можно определить производящую функцию! 5 (z) отношения со (z)/a (z). Ее коэффициенты задаются соотношением!

где S{z)= 2 Shz". Значит,

(1 + 5)о.= сй.

Для БЧХ-кода, исправляющего t ошибок, декодер вычисляет! только Si, S2, . . ., St- Таким образом, известны только первые 2i

1) Согласно другому, более общему определению (см. разд. 10.3), корняд должны быть а, a+i, . . ., a+-i для I ф I.

коэффициентов производящей функции S (z), и декодер должен попытаться определить о и со из ключевого уравнения

(10.13)

{i + S)a = u3modz2+i.

Декодер может решить это уравнение относительно многочленов (т (z) и со (z), используя алгоритм 7.4. Это дает второй шаг процедуры декодирования.

После вычисления многочлена локаторов ошибок о (z) декодер .\к)жет определить локаторы ошибок, находя взаимные корни а (z) = - Xiz). Определение величин {X;} по заданным коэффи-

циентам 1, Oj, о2, Оз Odega многочлена а (z) = Ojz составляет третий шаг процедуры декодирования.

Найдя локаторы ошибок, декодер может вычислить значение многочлена ы (z) в точке z = Xj:

<o{XV)--Yi П {i-XjXl}.

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

(10.14) Yi =

ш(Хг)

a{Xi)

[] (1--ХДТ1) Xil\(XiXj) Xill(Xi-Xj)

]фг ]ф1 Ш

Знак - для обозначения взаимного многочлена не следует путать со знаком которым мы обозначили нечетную часть функции.

Подытожим описанную процедуру декодирования для недвоичных ]>ЧХ-кодов в виде алгоритма 10.15.

10.15. Алгоритм декодирования.

10.151. Определить взвешенные степенные симметрические функ-нии Si, S2, . • ., S2t по формулам S = гС) (а), где ri") (х) - остаток от деления полученного дшогочлена R (х) на минимальный дигогочлен М* (х) элемента а над GF (q), к =i, 2, . . ., 2t.

10.152. Составить ключевое уравнение (10.13) для найденной ([)ункции S (z) mod z+i и решить его, согласно алгоритму 7.4, относительно многочленов o(z)** и о)<) (z).

10.153. Используя процедуру Ченя определения корней n-ii степени из единицы над GF (q), найти взаимные корни многочлена локаторов ошибок а (z). Это определит локаторы ошибок.

10.154. По формуле (10.14) найти значения опшбок.

10.2. Примеры

Возьмем код с блоковой длиной и = 15 над GF (2), синдром кото-] рого задается координатами S, S, и = S. Имеем

g = 4 - число букв алфавита; ге = 15 = 4 - 1- блоковая длина; t = 2 - число исправляемых ошибок; к = 9 - число информационных позиций; 7- = 6 - число проверочных позиций.

Пусть I - примитивный элемент в GF (2), где + + 1 = 0.1 Пусть а - примитивный элемент поля (2*), удовлетворяюп],ий уравнению а* + а + 1 = О над GF (2) или уравнению + а + + 1 = 0 над GF (4); I = а. Все элементы поля GF (2*) могут быть записаны в виде степеней а, как это сделано в табл. 4.1.

10.21. Пример.

1 + 5 = 1 + az + az + az + a"z* + . . . .

k D (h) в (h)

Разложение многочлена о*) имеет вид

а(4) = (1 + a*z) (1 + az),

так что

со*> z2 -

Zi = а*, = а,

, „11 Y - («*Р + «" а

(a) + aii

а(«* + «) а(аЗ)

10.22. Пример.

1+5 = 1 + a"z + aV + az + ai*z* + . . . .

0 0 0 1 1 1 0 аЗ

1 1 1 1+аЗг а-з 1 «"З О

2 1 1 l+az а-Зг 1 «-Зг а-1

3 2 0 l + a3z + aiiz2 a(l+a3z) l + aiiz2 а О

0)4 = 1 + az,

= -V = aV=!

10.23. Пример

1 + 5 = 1 + a"z + az + aV + a"*

z* +

Хг = a\ 1=--

= a« = .

*10.3. БЧХ-коды общего типа и 1-удлиненные БЧХ-коды

В разделе 10.1 мы определили БЧХ-код с исправлением t ошибок как код, среди корней порождающего многочлена которого содер-Ихатся элементы а, а, аЗ, . . ., а. Хотя это определение хорошо согласуется с двоичным случаем, оно содержит лишние ограничения. В более общем случае БЧХ-код с исправлением t ошибок можно определить как циклический код, порождающий многочлен которого равен произведению различных минимальных многочленов элементов а, а+, . . ., а+2- для произвольного I. Если I Ф i, то это

определяет БЧХ-коды общего типа с исправлением t ошибок; при I = 1 получаем частные БЧХ-коды с исправлением t ошибок.I Не ограничивая общности, можно считать, что I > О, так как слу- чай I = О совпадает со случаем I = п, где п - блоковая длина.

Декодирование БЧХ-кодов общего типа с исправлением ошибок может быть осуществлено следующим образом. В общем случае] справедливо равенство

(1 + 5) о = со,

или, что то же самое,

(1+ S 5,24 S 5.2") о =

fe=l

fe=i

Так как левая часть этого равенства делится на z, то права* часть также делится на z, и поэтому можно определить многочле!

Q-=--+о.

Очевидно, что deg £2 < deg а и (2 5ftZi+*-0 а = й -о, или

(1Q.31)

l+2t-l

(1+ 2 5ftzi+-0o = qmodz2+i.

Для решения уравнения (10.31) относительно многочленов о (г) и Q (z) можно использовать алгоритм 7.4. Многочлен 3ha4ehnf ошибок задается формулой

Общая формула (10.14) для значений ошибок в данном случае запи-9 шется в виде

(10.32)

xl~Q (Хг1)

xfQ jXi) П {Xi-Xj)

Здесь й (2) = z-JegoQ (z-i).

Таким образом, для декодирования БЧХ-кодов общего типа можно использовать следующий алгоритм:

10.33. Алгоритм декодирования. 10.331. Определить взвешенные симметрические функции Si, Si+i, . . ., Si+t-i-Функции Sk, к = I, I + i, . . ., Z 4- 2 - 1, можно найти по формуле 5ft = /•() (а), где /•() (ж) - остаток от деления полученного .многочлена R (х) на минимальный многочлен М*) (х) элемента а" над GF (q).

10.332. Используя алгоритм 7.4, решить уравнение (10.31) относительно многочленов о (z) и Q (z).

10.333. Используя процедуру Ченя отыскания корней ге-й степени из единицы над GF (q), найти взаимные корни многочлена локаторов ошибок. Это определит локаторы ошибок.

10.334. Найти значения ошибок по формуле (10.32).

При 1 = 1 алгоритм 10.33 сводится к алгоритму 10.15. Случай 1 = 0 также заслуживает специального рассмотрения. Если положить

(10.34)

так что

a{z)

Q{z)o{z) + zYi П (i-Xjz),

i ]ф1

i h

(1+2 Sh)a{z) = Q{z).

Следовательно, уравнения (10.31) и (10.32) остаются справедливыми при I ~ 0.

БЧХ-код с Z = О на самом деле является 1-укороченным вариантом i-удлиненного ) БЧХ-кода, обладающего тем же числом проверочных позиций и одной дополнительной информационной позицией. В общем случае 1-удлиненные БЧХ-коды с блоковой длиной п могут быть построены путем добавления общей проверки на четность к циклическому БЧХ-коду с блоковой длиной п - i. Например, проверочная матрица расширенного БЧХ-кода с блоковой длиной 16, исправляющего две ошибки, получается путем добавления общей

) С целью единообразия терминологии в переводе вместо обычно употребляющегося термина «расширенный» используется, как правило, термин «1-удли-ненный». Точное определение операций удлинения, укорочения, расширения н сужения кодов дается в гл. 14. -Прим. перев.