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



и~ 1

uqX +ai +а2 + .. . + а х , (5.93)

в которую подставляем значения Jc нз п. 2. Затем приводим подобные члены при одинаковых степенях х и решаем линейную однородную систему из v - 1 уравнений относительно v неизвестных коэффициентов д-, i - О, 1, . . ., v - 1. Такая система всегда имеет ненулевое решение.

4. Составляем искомое аффинное кратное в виде полинома

L(x) ~ Q = S ахР - 0.

i о

Например, для полинома /(X) =х*+5+8х + 13х+9, GF(2*) (5.94)

после очевидных преобразований получим:

х* = 5х + 8х2 + 13х+9; х = 12х + х + Пх + 13;

X* 13x2 + lOx + 5; х = гЗх + lQx + 5х; х = 4х + 10х+6.

Составляем линейную форму (5.93): oqX +ai х +а2Х +/73 х® = (5с2 +4дз)х + + (Д1 + 8д2) + (До + 13д2 + 10дз)х + 9Д2 + 6Д3.

Приравнивая нулю выражения в скобках, придем к системе нз трех линейных однородных уравнений относительно четырех неизвестных до,ь 2,з-Полагая, например, Д3 = 1, найдем: Д2 = 15; Д1 = 7; до = 3; 0 = 9д2 + 603 - 14, GF(2 ).

Таким образом, искомое аффинное кратное имеет вид

X (X) ~ Q = аз х +Д2 х +ai х +ДоХ - 3 = = х® + 15х* + 7х2 + Зл- + 14, GF(2*),

т. е. совпадает с полиномом (5.92).

Корни Xj-, ( = 1, 2, ..., 8, этого полинома бьши найдены ранее н составили множество = 3,4.6,8,9,10,11, 15} . Среди этих значений находятся и корни исходного полинома/(х) (5.94). Последовательно подставляя в / (х) значения х-, испытываем /(х-) на нуль, что позволяет в множестве В выделить все искомые корни (3, 6, 8, 10) заданного полинома, найденные в §5.3 другим способом.

Система линейных уравнений с матрицей Вандермонда, Предположим, что символы в кодовом слове искажены только стираниями, число h которых не превышает величины т - числа проверочных символов в коде Рида - Соломона (РС-коде). Тогда задача исправления h стираний (Л <т) приводит к необходимости решения системы из h линейных уравнений:

АХ = S,

где X - вектор-столбец неизвестных переменных, Х = (xi Х2 . -. ); S - вектор-столбец известных синдромов (свободных членов), = («512 • S}); А ~ квадратная матрица размера И X И, составленная из коэффициентов - известных (иразных!) параметров локаторов (дь Дг» - - • .fljj) и их степеней.



Для PC-кода определитель, соответствующий матрице Л, является определителем Вандермонда н имеет вид

• • «Л

д = UI -

2 «1

(5.95)

В правой части соотношения (5.95) приведено известное разложение определителя Вандермонда в произведение линейных сомножителей.

Линейная система уравнений может быть решена одним нз стандартных способов [32, 33]. справедливых длн любых нолей и произвольных матриц. Эффективные методы решения систем уравнений произвольного порядка (линейных, нелинейных и линейно-нелинейных), характерных для процесса декодирования помехоустойчивых кодов, будут приведены в гл.6. Здесь же изложим один из методов, который ослован на использовании симметрических функций н удобен при небольшом числе стираний н ошибок.

Введем над множеством (дь 2» - -» элементарные симметрические функции [33]

1=1

(2 = 1*1 + 1


равные сумме всех Л!/[(Л - /)!/ !] произведений, каждое из которых содержит / сомножителей д- с несовпадаюшями индексами / = 1, 2, Л. Например:

ffp = ai +Д2 + Дз; 2 -12 + fllfl3+fl2fl3; *3~ fli Д2 3-

Практическн удобно вычисление симметрических функций производить по рекуррентной формуле

(Л) (h-i) . Л~1)

л 7-1

(5.96)

где верхний индекс указывает мощность исходного {несущего) множества, а нижний - порядок симметрической функции, т. е. oi - это /-я симметрическая

функция над h элементами \ai, Д2» . - * j, д!} , а

это (/ - 1)-я

симметрическая функция над Л ~ 1 элементами дь Д2, • • •, а* Л , Используя

[рункции о ражение:

можно составить для неизвестной величины Xj следующее вы-

GF(/), х =

г h

£ (-1)

/ = 1

> (-1) Oh-j %

L/ = 1

(5.97)

Зависимость (5.97) представляет интерес благодаря симметричности разложения числителя н знаменателя по симметрическим функциям. Если используется поле GF(2), то получаем

Г h

- / = 1

h

L / = 1

(5.98)



г h

2(/-1)

(5.99)

где и = ШТ(0,5А).

С целью унификации метода поступим следующим образом. Пусть заданы позиции стираний { а, /3,7,...» ; перенумеруем их в некотором порядке и переобозначим, например, tfj, ... ,afj , где ft = i, = д2» * • •» ~ Л • Рассчитаем по формуле (5.98) или (5.99) значение старшей неизвестной х (ей соответствует х). Затем осуществим циклическую перестановку позиций, например, так: [0 у у ... t \, а], п вновь их перенумеруем слева направо; теперь а = а. Следовательно, можно воспользоваться той же самой формулой для расчета величины xj , но теперь ей будет соответствовать х. Осуществив И - I сдвигов и проведя h аналогичных расчетов, найдем все неизвестные х ,х,.., ,х.

Системы лииейно-иеяннейиых уравнений. Часто в сообЦ];ении кроме стираний содержатся также ошибки, причем во многих случаях достаточно ограничиться рассмотрением влияния одной или двух ошибок. Составим системы линейно-нелинейных уравнений следующего вида:

одна ошибка (неизвестного веса е на позиции х) и Л стираний (с неизвестными весами € и позициями а/, i = 1,2,..., Л) -

(5.100)

I = 1

две ошибки (eifXi ие2,Х2) нЛ стираний (,flj-,i = 1,2,... ,Л) -

Л . . .

S e.aj + eix{ +62X2 S

I = 1

/ = 0,1,.., ,Л + 3

(5.101)

Исключая по алгоритму Гаусса стирания из системы (5.100), получим выражение для расчета позиции х ошибки:

/ =0

£ (

/ =0

-1)а

Л-/"/+1

(5.102)

В частном случае двоичных полей GF(2) множители (-1) опускаются. Рассмотрим теперь систему уравнений (5.101), Аналогично предыдущему, исключал стирания по алгоритму Гаусса из системы (5.101), получим промежуточную нелинейную систему из четырех уравнений относительно неизвестных ei.xi не2уХ2:

ei П (xi i = 1

а,-)х{ +€2 П

(х2-а.)х2 S

.£ (-1)-/Л+/+1-Г /=0,1,2,3

i = о



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.0145