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



Системы уравнений (2.69) и (2-70) могут быть представлены в матричной форме

(2.71а) (2,7]б)

где о = (gq - \, аь СГ2, . - . , сг„) ; ~ (<о. - • . *п-0 -д гг,п- \ ганкелевы матрицы, причем Лд треугольная матрица порядка п- I, лЛу

прямоугольная матрица размера « X (и - I), имеющие соответственно вид

-4д =

-1 "/1-2

«2

«1

2 - -

• /7 + 1

п + \

2ft-l

где в матрице Лд для простоты не проставлены нули (на свободных местах) Уравнения (2.71) можно объединить в одно матришюе уравнение

Л а - П,

где по-прежнему

i, ai, «2, . . . , (J,, } ;

(cjo, cji, , . . , uj, j, О, . . . , 0) ,

n раз

(2,72)

a Л - ганкелева, продолженная вверх, матрица

. . 02

Oq ~ 1

аг аъ

• п~2

п~\

2п-3

2Я-2

2п-\



в уравнениях (2.71) известны лишь матрицы Лд и . а векторы а и ш неизвестны. Тривиальный путь решения состоит в первоначальном нахождении сГ нз Уравнения (2-716), а затем в определении to из уравнения (2.7Ja). Однако можно заметить, что t3 - R, где R - введенный ранее "остаток", точнее полу-

НОД полиномов 2 и у1(2) = /42„(2). Поэтому, как было показано выше, полином c3(z) может бьп-ь найден методом Гаусса или с помощью алгоритма Евклида (деление, начиная со старших разрядов). Затем из соотношений (2.42) и (2.46)

находится обращенный вектор а = ш : Л и искомое продолжение -4-1-= -со : а.

Совершсиио аналогично можно осуществить аппроксимацию Падэ дробно-рациональной функцией ф{2)1а(2) для обращенного полинома;

В результате будет получено матричное уравнение, подобное уравнению (2.72);

А о = \{/, где ф = (Фо,

О, . . . , 0) ; вектор "а такой же, как и в уравнении

(2.72), а матрица А

п раз

- ганкелева, продолженная вниз;

2П--2

2П--1

2п-\

% 1

%-2

- • (2

CTq - 1

2

On 1

пл-Х

Опл-2

2n-2

2n~X

% + 1

2и-1

- 0

Можно заметить, что ф = ~р, где Р

введенный ранее "избыток", точнее

полу-НОД полиномов z *"* и A2ni) который может бьп-ь рассчитан по алгоритмам Гаусса или Евклида. Далее из соотношений (2-43) и (2.47) находится вектор

о= - ф : А и искомое продолже1ше А ~ : о,

Модифицированный алгоритм Евклида для вычисления полу-НОД. Классический алгоритм Евклида основам на последовательном делении ряда полиномов -остатков, связанных равенствами (2.56). С другой стороны, мы видели, что операция деления может быть заменена умножениями по схеме алгоритма Гаусса без нахождения мультипликативных обратных элементов. Эта идея может быть использована для модификации алгоритма Евклида при вычислении полу-НОД.

Суть модификационного алгоритма состоит в следующем [61]. Пусть даны два полинома /(2)=z и g (z) = A2fi(z)



Задача состоит в нахождении такого остатка rf{z), удовлетворяющего соот-нощению (2.57) и имеющего степень менее п при условии, что степень предьщу-щего остатка rf- i{z) не менее п. Итак, необходимо найти полиномы rf(z)y u(z) HV(z), связанные равенством

rfiz) =f{z)Uf{z) g{z)Vf{z)

при deg rfi;{z) < n, ho deg r] y{z) > n.

В этом случае vj{z) = 7(7) = 7o*() и i/;(z) = 7Qtj(z), гДе полином 7(2) имеет вид (2.31), а полиномы (j(z), tj(z) удовлетворяют соотнощению (2.36).

Вычисления осуществляются по формулам [60]:

;..(z) = X. M,- j(0+X. j.,. j(z);

r,,.(z) = X. jr,. j(z)+X. j... j(z),

где / - 1 -1 - старшие коэффициенты полиномов j (z) и (z); / = = Meg i?/ i(z) - deg (2/ i(2)

= 1, если ? > 0; = 0, если / < 0.

Начальные условия модифицированного алгоритма; roiz) =z2"; (2о(2) =a{z);

i/o(2) = мо(2) = 1; 1-0(2) = T7o(z) = 0.

Для нахождения полу-НОД достаточно вычислять только значения r, qf, и xi y\ при этом допустимо на любом шаге сокращать, т. е. покомпонентно делить, данный остаток r на произвольный элемент. Для нахождения полинома o(z) приходится вычислять также значения и м/, а для нахождения полинома cj(2) - значения и т?у. В последних двух случаях указанное сокращение не-допу стимо.

Читателю рекомендуется в качестве упражнения проделать все шаги модифицированного алгоритма для рассмотренного примера с л = (2, 3, 1, 3, 11, 21).

Заметим, что в качестве rf будут получены (с точностью до постоянного множителя) частные остатки из прошлого примера:

/?1 = - (3z +z* + 3z + llz + 21z);



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