Главная Помехоустойчивое кодирование



т. е.

зен лишь при невысоком порядке матрицы (о..;, ..х ровании кодов, способных исправлять небольшое число ошибок.

при декодй-(до 6 ... 8)

Два других метода, по существу, позволяют по известному ному синдромов S (z) решить относительно полиномов a{z) и уравнение Падэ над полем Галуа:

5(2)сг(2) modz".

поли-co(z)

(6.24)

В теории помехоустойчивого кодирования ключевым [8].

После вычисления корней полинома o{z) а следовательно, и опре-

деления локаторов = а ошибок, их величина может быть рассчитана по формуле Форни (6.15).

Заметим, что в полном решении уравнения (6.24) нет необходимости, так как достаточно найти полином локаторов a(z), а по нему - продолжение вектора синдромов (см. § 6.3).

Пример 63. Декодирование итеративным ТБМ-методом, Итеративный метод был изложен в конце гл. 2 для бесконечного поля; он без изменения переносится на конечные поля. В табл. 6.1 приведены результаты вьмислений по этому методу для вектора-синдрома S (6.146).

Итак. a(z) = I4z + 13z + 1; aJ(2)

полем GF(2), x* = x + 1, имеет корни zi = a

Полином

-i. -

= Of= 6= и ~

= 13 = 4

и Z2 =

можно убедиться, например, непосредственной проверкой, т. е. /1 = 3, /2 - Ю. Учитьшая соотношение (6.16) для произ-

формуле Форни (6.15) найдем выра-

получим

величин ошибок: в,* = (7а+ 8) • + П. Откуда следует: 63 = 8; вю = 12. Корректируя вектор (6.13) с помощью вектора Е (6.12), получим верное кодовое слово U (6.11).

Исправление ошибок и стираний. Как уже отмечалось в гл. 1,в принятом кодовом слове могут содержаться искажения двух типов -

Таблица 6.1

Пример выполнения итеративного алгоритма для вектора

5= (8,13,7,13,15,15)

0/ iz )

(z )

l + 8z

1 + 6z

l + 6z + 12z

13z +32

1 + 13z + I4z2

13z2 +3z3

8 + 72

1 + I3Z +I4z

I3z3 +3z*

8 + 7z

1 + 13z + I4z2

8 + 7z



стирания, местоположение которых известно, и ошибки, местоположение которых не известно. В этом случае удобно различать многочлен a(z) локаторов ошибок, определяемый, как и раньше, и многочлен Г (z) локаторов стираний, задаваемый следующим равенством:

Г(2)

= т /.

П (1-za) i = i

/ = т

П (1-zZO, i = i

где 7 - число стираний; if - позиция /-го стирания; = стирания.

Тогда ключевое уравнение Падэ примет вид 5(2)Ф(2) =co(z), modz"*,

где Ф(2) = r(z)a(z).

локатор

(6.25)

Уравнение (6.25) можно решить теми же методами, что и уравнение (6.24), если ввести обобщенный полином синдрома Форни T(z) = = 5(z)r(z) по модулю z"*. Однако при итеративном ТБМ-методе (см. конец гл. 2) нет необходимости в оперировании с полиномом Форни T(z), а достаточно заменить a(z) на Ф(z), переобоэначить v - deg Ф(z) и изменить начальные условия, приняв/ = т,ь. = т, - -1, Ф- (z) =

Пример 6.4. Пусть над полем G¥(2 ), х =

(6.13), которому соответствует синдром S (6.14а); причем стиранием является символ на позиции /3 = 3 (отсчет справа налево, начиная с нуля). Этому символу соответствует локатор =0: - 4 и полином стираний r(z) =4z + 1.

Таблица 6.2 иллюстрирует применение ТБМ-метода.

Итак, имеем Ф(2) = 1 + 13z + 14z.

x + 1, задан вектор

таблица 6.2

Пример выполнения итеративного алгоритма для вектора

s = (8,13,7,13,15,15) с учетом стирания

@j (z)

т = 1

Г (г) = 1 + 4г

z + 4z

J + 7z2

13z +z

1 + 13Z +14z2

13z2

1 +13z + 14z2

13z3+z*

l + 13z + 14z2

13z*+zs

1 + 13z + 14z2



Полином локаторов ошибок можно найти, разделив Ф{г) на r(z). Однако в вычислении этого полинома также нет необходимости. Используя "частотный подход", достаточно найти продолжение вектора синдромов S по рекуррентной формуле типа (2.29) с естественной заменой o{z) на Ф(z), л - на 5.

6-3. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ КОДОВ РИДА - СОЛОМОНА в ЧАСТОТНОЙ ОБЛАСТИ

Кодирование РС-кодом. Кодирование в частотной области РС-кодами над полем GF( = 2*) состоит в следующем. Информационное сообщение б из к = п ~ т = q - 1 - т символов принимается в качестве старших компонент спектра V, а остальные т символов этого спектра

полагаются равными нулю.

Кодовое слово v в несистематической форме, передаваемое в канал, получается за счет обратного л-точечного ФМС-преобразования (ФМСП) спектра V длины «. Это преобразование может вьшолняться по быстрым алгоритмам.

Пример 6.5. Пусть над полем GF(2*) выбран {п- 15, к= ll,d-3)-код PC и задано сообщение

Q = (Gib Gio,..., Gl) = (13. 7, 15, 5, 9,1, О, О, О, О, 0). (6.26)

Сформируем спектр

V=iQ; р) =

= (13,7, 15, 5, 9, 1, О, О, О, О, 0; О, . .. , 0)-(Vo,Vu Уг, Кз, F4, Fs, V, Ц, Fg, F9, Уго\ Fu,..., F14), (6.27)

где р = (О,... , 0) - нулевой вектор длины т = п - к.

Согласно соотношению (4.19), обратное ФМС-преобразование спектра V можно найти как прямое ФМСП, но с перестановкой (4.20) компонент входного либо выходного вектора. Так как длина л = 15 = = 3 • 5 - составное число, го целесообразно использовать быстрый алгоритм преобразования, например, соотношения (4.25), (4.26) -см. рис. 4.12 ... 4.14. Мы воспользуемся методом взаимно простых множителей, полагая

Фи - (Фз® Фз) = (з ® Ф5)(Фз ® Es),

где знак ~ изоморфизма заменяется знаком равенства при одновременном переупорядочении по правилам (4.9) компонент входного и выходного векторов.

Перекомпоновав вектор (6.27) согласно последовательности (4.9а) й умножив его на матрицу В (рис. 4.14), найдем промежуточные вели-



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 [83] 84 85 86 87 88 89 90 91 92 93 94


0.0248