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



предположим, что 10; иначе примем о в качестве второй компокюеты частного и укоротим слева отбрасьюанием с - т*" так же поступаем

ири 12 о и т. д. до тех пор, пока старшим в укороченном слева векторе С не окажется нулевой коэффициент.

вновь применим алгоритм гаусса, яо приняв теперь в качестве делимого полином с* (2):

с(1>

я - m - 2

* 0

в"

• 0

. 0

где вектор в получен укорачиванием вектора В за счет отбрасьшання ирадого нуля и с21

таким образом, можем составить равенство, аналогичное соотношению (2.51):

в результате второго шага вычисляется вторая комгюяента частного с2 i/m* bjf, ФвуН находится второй частньгй остаток С (2).

аналогично пос-с 1-го шага можно составить соотношение

с<*> (z) = bCUz)~ с а -Л\ z « - - (2 ) ,

П-1 + l

0-1)

(2.52)

полтюмы с"(г) и С (г) - соответственно i-йи (/ - 1>-й частные

остатки; cSi +\ " коэффициент при 2~ + * полинома с окончательно после (и - ш + 1)-го шага получим л Q{z) k/?(z) в равенстве (2.50) следующие представления:

(/-i)

(2.53)

(2) = л i d- Ъ 2 ,

i =0

m +1

пиллюсприруем изложенную методику примером. пусть даны делимое

А = с«*> = (2, ~1. -3, 0. о, о, о, о, 0) и делитель = (2, 3, 1, 3. 11,21), уже ис-пош.эуемые ранее при вычислении ст по формуле (2.44). итак, « = 8, m = 5; а„ = = Ьщ- 2. согласно соотношению (2.52) прн i - 1 имеем

-*с*> = (4,-2,-6,0.0,0.0.0,0) - (4,6,2.6, 22,42,0.0.0) = = (-8, -8, -6, -22, -42, о, о, 0) = -2 (4, 4, 3. п. 21, 0. 0. 0).



таким образом, clj ~ с- -8

далее получаем:

/ = 2, с

= С - д = 4 (2, -1. -5. 1, 42. 0. 0). с

(2) л2)

п -1

= 8;

3. с> = йс*-с

5 = -8(4. 6, 2,-31,21,0), с

(3) ЛЗ)

и -3

= -32;

(4)

,* =4, с" =йс*"-с

(3) .(3) о

в = 16(37.1,42)

итак, согласно представлению (2.53) R = кс" = (37. 1.42);

m + 1

= 2"" (-32 +8-22 ~8 -22 + 2-22) =2-22+2-2,

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

как правило, при разыскании особых продолжений ганкелевых матриц достаточно ограничиться нахождением только полинома, пропорционального остатку (2). а вычисления частного Qiz) и множителя \ можно не производить.

полу-нод и подходящие цепные дроби. выше использовался алгоритм гаусса для сфиведения к треугольной или трапецеидальной форме квадратных Ап и расширенных л ганкелевых матриц, все компоненты которых известны. теперь же применим этот алгоритм к еще более расширенным ганкелевым матрицам, а именно к усеченным побочно-диагональным матрицам размера (п +1) X Q/i) имеющим вид

и + 1

71 + 1

и + 1

и + 2

и+2 i °и + 1

2П - 1 "2и t j

о J

(2.54)

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

верхнем углу.

на одном из шагов алгоритма гаусса, прнмеитого к Maipuue (2.54), будет сфор»«1рована строка, совпадающая с точностью до постоянного множителя с вектором-остатком R. при этом ecjm ранг матрицы >4„ „. равен и, то указанный



вектор сформируется на последнем шаге в последней строке. это объясняет, почему к матрице у4„ „ + j добавлена дополнительная (и+ 1)-я строка.

поясним сказанное конкретным примером.

пусть задана матрица, порождаемая вектором v4 = (2, 3, 1, 3, и, 21),

3,4 =

ai ai Дз 4

Ql йъ 4 йз й4 as йб ,

г 2 3 3 1

1 3 11 21

расширим ее до усеченной побочно-диагональной формы, к которой применим алгоритм гаусса:

"2

3 и

3 1

21

11 21

-7 3

21 0

3 21

0 0

13 39

-63.

->

-168

(-2)

-630

(-2)

i

1 13

"156

-168

1 37

-546),

(2.55)

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

в матрице (2,55) слева от штриховой линии сформирована трапецеидальная форма для матрицы А а справа в последней строке образован остаток R = (37, 1, 42), полученный ранее другим методом.

интересно отметить следующее. векторы, образуемые строками матрицы (2.55), являются частными остатками в итеративной процедуре, основанной на алгоритме евютида и применяемой при разыскании наибольшего общего делителя (нод) полиномов z" и v4(z), фигурирующих в формуле (2.36). однако алгоритм евклида применяется фрагментарно, до тех пор, пока не будет получен полином, степень которого менее и, т. е. длина соответствующего вектора не превышает и. подобный полином будем называть полу-нод-

этот термин введен по аналогии с работой [4], в которой полу-нод определяется по-другому (в соответствии с иной целью), как последний остаток степени не менее п. такому полиному соответствует предпоследняя строка в матрице (2.55).

суцщость алгоритма евклида для двух произвольных полиномов f(z) Hg (z) состоит в следующем [33]. предположим для определенности, что степени полиномов связаны неравенством deg/(2) > deg (z). разделив/(2) на(-г), получим частное ?i (z), называемое неполным, н, вообще говоря, не нулевой остаток л i (z). делим затем giz) на Ri(z) и т. д. этот процесс можно представить в виде системы равенств



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