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



2,-1, ~з. О, а о, а о, о: 2,3,1,3,11,21 = 1,-2,1,-2

2, 3, 1, 3, И, 21

4, -4, -3,-11,-21, О 4, -6, -2, -6,-22,-42

2, -1, -5, 1, 42, О 2, 3, 1, 3, 11, 21

-4, -6, -2, 31,-21, О -4, -6, -2, -6,-22.-42

37, 1, 42 = Л.

Убедимся теперь, что особые продолжения А (z) можно вычислять без привлечения рекуррентных процедур.

Рассмотрим формулу (2.29) при/ = 2« + 1:

Выражение в скобках формулы (2.45) равно коэффициенту из соотношения (2.41). Таким образом, anw %п~ откуда находится первая компонента особого продолжения Д2« + 1 = ~~п%-

При/ = 2и + 2 нз формулы (2.29) получаем

Выражение в последней скобке согласно соотношению (2.41) равно коэффициентуJ, т. е.

В общем случае

2«+/<0 + 2«+/-1<«+--+2« + 1</-1+"« + 1-/ =0 >*-

Следовательно, особое продолжение вниз А для полинома А (z) можно найти из соотношения

А\ а = ~Я: (Р : А).

(2-46)

Аналогично особое продолжение вверх А f для полинома А (г) может быть найдено нз соотношения

А f =-Р: "а =Р: (: Л )- (2.47)

Заметим

следующие

соотношения:

А I = i-RA) :Р = (-R:P)A] А f = (-А) : = {-Р:Ж)А.



в то время как по формулам (2,46) н (2.47) можно вычислить любое число продолжений.

Вычислим для предыдущего примера несколько компонент особых продолжений вниз и вверх по формулам (2-46) и (2.47):

~r : а = а \

37, 1, 42 : 1,-2.1,-2 = 37.75,155,...

37,-74, 37, -74

75, 5, 74

75.-150. 75,-150

155, - . .

: а = у4 f

3 5 15

3, 1. -2 : -2, 1,-2, 1 = - - ,- -

2 2

5 5 5 5

2" 4 2"4

2 4 8 "

Таким образом, начальные компоненты особых продолжений равны: Д7= 37, as = 15, = 155; «/о =-3/2, д , =-5/4, <7 2 = 15/8,

что было получено ранее другим способом.

Естественно, деление в выражениях (2.42). (2.43) и (2.46), (2.47) практически выполняется по процедурам, не требующим нахождения мультипликативных обратных элементов. Покажем, как это можно сделать.

Пусть заданы два полинома

a(z) az +*7 z" + .., + a2z +aiz +ао- 2 az; (2.48)

i = 0

b{z) = bz +bjn yZ~ + .,. + b2z +biz +bo= Б bjz\ (2.49)

i = 0

причем для определенности принимаем и > m, а также без потерн общности считаем, что д„ "0»ьу Ф 0.

Задача состоит в нахождении частного q{z) и остатка r (z) от деления а (z) на b{z), т.е. таких полиномов q{z) н Л (г), которые удовлетворнют равенству

aiz) = q(z)biz) +r{z)

(2.50)



deg R{z) < deg В (г) = m, deg Q{z) = n - m,

где deg R (2), deg В (z) и deg Q (z) - степени полиномов остатка R (z) , делителя

j5 (z) н частного Q{z).

Перейдем от полиномов (2.48) н (2.49) квекторам>4 = (аа j . . .агаупо)

н В = (6;ит-1 **• bjbtbo). Выровняем степени полиномов (2.48). (2.49) и длины векторов Л, В; для чего умножим полином В (z) на z""а к вектору В допишем п - т нулей:

(2) =2"- (2) =

- bjjjZ + Djjj J г + . . . + bQZ , В ~ {bffibjn-1 1 bo • • • )•

n -tn нулей

Применим теперь к векторам А н в\ нмеюшим одинаковую длину, одни шаг алгоритма Гаусса (2,19):

.. До

П- I

ще i:)= Af . - миноры второго порядка, образуемые столбцами п н i, / = О, 1, .. . , п (нумерация столбцов справа налево), а верхний индекс (1) указьюает, что совершен только один шаг алгоритма Гаусса.

Следовательно, компоненты сМ)вектора С* находятся по формулам

4-1 m„ i-----=nbi -bfaf, i >nm-

<n-m-i =-V«-m-i--*/ =-m«/. / = 0, 1,m-1.

h среди них могут быть нулевые. Если же все компоненты с окажутся равными

нулю, то A{z) = kz ~ Biz), где к - о/Ь - коэффициент пропорциональ

ностн. В общем случае С ФО.

Возвращаясь к полиномам, можем записать соотношение

С iz) = bAiz) -az-Biz). (2.51)

Степень полученного полинома С (z) по крайней мере на единицу меньше степени полинома - делимого A{z), так как длина вектора С на единицу

(npHCj = 0) меньше длины вектора >4.

Итак, в результате первого шага алгоритма Гаусса может быть вычислена первая компонента частного й/Ь, н найден первый частный остаток С (г),



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