чины Zf (5.87),/ = О, 1,. .. , 14. Затем, умножив вектора = (2o,Zi,. . ., 214) на матрицу Л (рис. 4.14), вычислим составляюндае (5.88) вектора у. Переупорядочив последний в соответствии с правилом (4.96), получим вектор (5.85). Наконец, воспользовавшись перестановкой (4.20), найдем искомое кодовое слово как обратное ФМСП:

v=(14, О, 1, 10,0. 5, О, 10,2, О, 2, 14, 15, О, 3) =

= (Vo, 1, 2, э, V4, Vs, Ve, V7, V8, V9, Vio,Vii, V12, Vi3, V14),

где Vi G GF(2), / = 0, 1,. . ., 14. "

Укрупненный алгоритм декодирования РС-кода в частотной области. Ориентируясь на структуру рис. 6.4,5, вьщелим основные этапы декодирования:

1) преобразование Фурье - Мэттсона - Соломона;

2) нахождение полинома локаторов;

3) рекуррентное продолжение синдрома;

4) коррекция и извлечение сообщения.

На первом этапе принятое кодовое слово v \ возможно, искаженное помехами, подвергается л-точечному ФМС-преобразованию. Полученный вектор С = (Со, Cl, Cft-i) соответствует спектру для суммы кодового слова v и ошибки е, т. е. С= (у \-е)Фп= V + Е, Так как т составляющих pj- вектора F= (2; р) являются нулевыми, то соответствующие им т компонент вектора S = (5о = С;,51 = C;t +1 > • • >- i ~ = C/2 i) "в чистом виде" характеризуют конфигурацию ошибок е. Другими словами, эти т компонент аналогичны синдрому во временной области; причем если все они равны нулю, то считается, что в принятом слове V нет ошибок (иначе v обязательно искажено).

Второй этап упрощается (по сравнению с временным декодированием), так как отпадает надобность в полном решении ключевого уравнения (6.24), а достаточно найти лишь полином локаторов o{z). Поэтому сокращается количество операций при решении уравнения (6.24) с помощью ТБМ-метода, алгоритма Евклида или другого приема.

Например, для вычисления полинома o{z) воспользуемся методом, изложенным в гл. 2. Построим на w-компонентном векторе синдрома S усеченную побочно-диагональную ганкелеву матрицу типа (2.54), которую методом Гаусса приведем к трапецеидальному виду. Тогда в ее последней строке будет сформирован остаток R, т.е. полу-НОД [z, S(z)]. Далее используем безрекуррентную процедуру,основанную на соотношении типа (2.42), которое в нашем случае удобно представить в форме

(6.29)

где S - нормализованный синдром, получаемый из вектора S при умножении всех компонент последнего на (Sj - его самый левый ненулевой коэффициент); - старший коэффициент полинома o(z)]

ф - нормализованный вектор, полученный из вектора о при умножении компонент последнего на а JI

Третий этап сводится к вычислению спектра Е ошибок. Для этого осуществляется рекуррентное продолжение синдрома или, что то же самое, особое продолжение ганкелевой матрищ11, построенной на разрядном векторе синдрома. Подробно приемы вычисления указанных продолжений бьши рассмотрены в § 2.3. Заметим, что достаточно найти к составляюпщх продолжения. Однако для косвенной проверки правильности вычисления полинома o{z) и вектора £* целесообразно найти еще т продолжений последнего, которые должны совпадать с т компонентами синдрома. Цродолжения синдрома находятся на основании соотношения типа (2.27). Но в нашем случае вычисления удобно производить по рекуррентной формуле

(6.30)

+ GF(2),

где = 1, / = О, 1, ..., и - и; v - степень полинома а(2), т. е. число ошибок, исказивших принятое кодовое слово. При этом т старших составляющих спектра Е совпадают с соответствующими компонентами синдрома, характеризуюпщми "чистую" ошибку е, а именно:

Коррекция (четвертый этап) состоит в сложении векторов С, Е и вьщелении сообщения Q после отбрасывания нулевого вектора р длины т из суммы: V = СЕ = (Q; р).

Пример декодирования (с помощью алгоритма Гаусса, безрекуррентного вычисления полинома локаторов и продолжения синдрома по рекуррентной процедуре). Предположим, что кодовое слово (6.28) с символами G GF (2*) принято в виде следующего блока:

v- (О, 3, 1, 10, О, 5, О, 10, 2, О, 2, 14, 15, О, 3) =

= io, Vi, v2, v3, vi,Vs,vi,v;,vi,Vg, v[oyv[i,Vi2 , Via, v), (6.31)

гдеуеОЕ(2*), i =0,1,...,14.

Следовательно, v = v + где e - вектор ошибки, пара левых разрядов которого отлична от нуля: Cq = Ы; е i = 3,

Подвергая принятое слово v (6.31) и-точечному ФМС-преобраэо-ванию (реально вьшолняемому по быстрым алгоритмам), можно найти спектр С = F + £ для суммы безошибочного кодового слова v и ошибки е. Мы предоставляем читателю самостоятельно убедиться, что

(6, 15, 11, 4, 3, 11, 4, 11, 10, 5, 2; О, 3, 7, 13)

- (Со, Cl, С2, Сз, с4, Cs, Сб, с7, Cg, с9, Сю; Сц, Ci2,Ci3, с14)

(6.32)

Так как четьфе (т = 4) правых разряда, составляющих синдром 5, отличны от нуля, то принятое слово v ошибочно. Нормализованный

синдроме=5 5"= (0,1,5,11), где5л =5i = 3; =

Построим на векторе S = (13, 7,3, 0) усеченную побочно-диагональную матрицу, которую приведем к трапецеидальной форме:

13 7

3 ] О 0] О

3 0 0 О

13 7 3 0 О 15 3 О

О 7 3 0

13 7 ] 3 О О 15 ] 3 О

О 0 15 0

Переход ко второй матрице от первой осуществляется путем выравнивания левых коэффициентов во всех ее строках [вторая строка по правилам поля GF(2 ) умножается на элемент 7, а третья - на И], после чего первая строка добавляется к остальным. Для перехода к третьей матрице от второй нижняя строка умножается на элемент поля 9 и к ней прибавляется вторая строка, В последней строке трапецеидальной матрицы сформирован полу-НОД R= (5,0).

Используя соотношение (6.29), найдем нормализованный полином локаторов ф(г):

О, 5, О, О, О, О О, 5, 9, 15

О, 1, 5, 11 =5, 9, 6 = 6- (15,4,1)

О, 9, 15, О, 9, 13,

О, 6, 4, О О, 6, 10, 1

(2, 1)

где Си = 6 - старшая компонента полинома локаторов a(z); Р - полу-НОД [z*, S (z) ]; далее Р не используется.

Итак, безразмерный полином локаторов суть z -v Az 15. Можно убедиться, что полином 1 + 4х + 15х = 15 • (2 + 5xi- х) позиций оши-

бок получаемый иэ предьщущего при z = х~ , имеет корни: Ху - \ -

= а * = 2°; = 2 = = 2\ где а = 2- примитивный элемент поля. Следовательно, /1 = О, /2 = 1, что совпадает с позициями ошибок, введенными в кодовый блок (6.31).