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



fiz) =g{z)qi{z) +Riiz), degi(z) < deg(z); giz) =7?i(z)(72(2) +2(z), deg2(z) < degi(z);

Riiz) =2(z)3(2) +лз(2), deg3(z) < deg2(z); (2.56)

% 2() =>t-i()?(2) +>t(). deg7?(z) < deg7?t j(z); л 1(2) =%(2)?i(z).

остаток л(2) нацело делит предыдущий остаток Rj i(z). поднимаясь снизу вверх и подставляя R/ii) нз последнего соотнощения в предьщущее и т. д., заключаем, что Rff;iz) также нацело делнт все предыдущие остатки и полиномы g (z) и f{z). с другой стороны, на любой общий делитель полиномов g (z) и f{z) нацело делятся обе части во всех равенствах (2-56). поэтому Rfi) ~ остаток, надело делящий предыдущий остаток, является нод исходных полиномов f{z) и g{z). однако нод определен только с точностью до постоянного множителя (нулевой степени).

наибольший общий делитель можно представить в виде так называемого полиномиального уравнения [33]

Rfiz) =/(z)w(z) +(z)v(z);

deg u{z) < deg/(z), deg viz) < deg/(z),

где полиномы m(z) и J (z) определяются рекуррентными соотношениями Uiiz) = ?,-(z)w, j(z) +m, 2(z); Viiz) = qiiz)Vi iiz) +Vi 2(

при следующих начальных условиях:

(2.57)

(2.58)

W-i(z) = 0; UQiz)=l; v i(z) = l; »o(2) = 0. (2.59)

алгоритм евклида последовательного деления полинома fiz) на giz) соот ветствует разложению дробно-рациональной функции hiz) = /(2)/(z) в конечную цепную дробь:

hiz) =qi +

Я2 +

Яз +

4 + . . .

hiz) + (?2 + (?з+- + %kl\ + (2.60)



ограничиваясь в представлении (2.60) одним, получаем соответствующие подходящее дроби:

fii = qi; ь2 = дх+я2; лз = ?1 + (2+3 *)

4 = 1 + [?2 + (3 +?4*)~] ит. д.

двумя и т. д. слагаемыми,

приведем подходящие дроби к одному знаменателю, обозначив = uf/v тогда

"1 1 21 + 1 - , 2 = 1+---

2"1 +"о

q2 l + vq

qi +

q2 +яз

ql +q3 + q\ q2qz i + q2q3

iq2+q3 )"1 +"0

iq2 + ?3 + 0

?3"2 + wl q3v2 +

1 +?1 2 +1 ?4 +34 + ql q2q3q4

q2 +q4 q2qzq4

q4u3 + u2 q4v3 + v2

и т. д,

по индукции можно показать [32], что для подходящих дробей справедлива рекуррентная формула

hi =

г "

где числитель и знаменатель определяются равенствами (2.58), а начальные условия w i = о, uq = 1, v -i = 1,vq= о совпадают с условиями (2.59).

формула для разности двух соседних подходящих дробей, полученная л. эйлером (1707-1783), имеет вид

i -1

(-1)

z -1

(2.61)

уравнения (2.58) можно представить в матричной форме:

"/ (2)

v.iz)

l~2

(2.62)

со скалярным умножением матриц в правой части, т. е. со сложением покомпонентных произведений элементов строк первой матрицы на элементы столбцов второй.

от матричного уравнения (2.62) перейдем к уравнению с расигаренными крайними матрицами:



W, i (Z)

QiU) 1

(2.63)

В свою очередь, среднюю матрицу в уравнении (2.63) также можно разложить в скалярное произведение:

(2) W/ 2() Vfliz) i/ 2()

?,- l(2) 1

и т. д. В результате получаем представление

w/(2)

"/-1 (2)

-

"1 0

I = I

Г?у(2) Г

I/ (2)

0 1

} = 1

1 0

(2.64)

Где П - символ цепочки скалярных произведений, а матрица перед П учитывает начальные условия (2.59).

Обозначим матрицу в левой части уравнения (2.64) через D,-, заметив, что ее определитель, т. е. определитель для правой части этого уравнения, согласно формуле Эйлера (2.61) равен (-1):

"/(2)1/ 1 (Z) - i/(z)M, i(z) = (-1).

Поэтому обратная матрица имеет вид

D7 = (-1)

-viiz) uiz)

(2.65)

Действительно, непосредственная проверка дает

DiDf = (-1)

"i

= (-1)

"с "i -

- ( 1)

0 "

- "i

"/-1-

(-1)

1

0"

"1 0"

-0 1

где для простоты опущен аргумент z.

Подобным образом составим матричные уравнения и для системы (2.56). Двум ее последним уравнениям соответствует запись

3 - 1610



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