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



с векторами А и А длины п или п- \ следующим образом свяжем юлиномы A{z) и А (z) степеней л - 1 или п от переменной z :

I - п .

I = 1

Б a,-z I = 1

.aiz-ai

I = 0

+i(z) = 2 a,z =a„z" + fl„ i

/ ~ 0

z" W . . . +aiz +ao.

Следовательно, свободный члену "обратного" полинома Л (z) имеет минимальный индекс, а у "прямого" полинома A{z) - максимальный.

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

В теории помехоустойчивого кодирования задача оперирования с ганкелевыми (или теплицевыми) матрицами возникает при составлении системы линейных уравнений, называемых синдромными, и в век-торно-матричной форме записываемых в ввде

Аг о = Ь;

Ату = Ь,

(2.6а) (2.66)

где Aj и Л р - теплицева и ганкелева квадратные матрицы порядка п; о = [oi 02 . • Оп] - вектор-столбец высоты п неизвестных переменных; b = [bjbi • • • bfj] - вектор-столбец высоты л известных величин

(параметров); а - обращенный вектор о.

В развернутом виде векторно-матричное уравнение (2.66) имеет следующее представление:

"1

" »л

* • л + 1

й ь ш ш Л

Ш » »

Ш ш ш

Л+ 1

WW WW

2rt- 1

W W

(2.7)

т. е.



a2 0 +аза„ 1 + . -. + ai = 62;

(2-8)

Как уже отмечалось, от ганкелевой матрицы можно перейти к теплицевой. Действительно, изменив в каждой строке системы (2.8) порядок слагаемых на обратный, получим в екторно-матричное уравнение (2.6а), аналогичное (2.7), но с теплицевой матрицей и с прямым вектором а. Далее ограничимся рассмотрением системы (2.7) с ганкелевой матрицей.

Теплицева или ганкелева матрица с дополнительным свойством а. =а, i =1, 2, называется циклической {циркулярной или

просто циркулянтом). Например, для л = 4 имеем следующие циркулянты:

«1

- теплицев (правый);

(2.9а)

ганкелев (левый),

(2.96)

где каждая последующая строка получена из предыдущей строки путем циклического сдвига вправо - (2.9а) или влево - (2.96). Оба циркулянта связаны между собой соотношениями, аналогичными соотношениям (2.5):

Ст J - С]

С г J = Ст : / С

где/ - побочно-диагональная матрица (2.4),

С помощью циркулянтов задаются важные бинарные операции (см. § 3.2), используемые, в частности, в процедурах кодирования - декодирования помехоустойчивых кодов.

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

Определитель и ранг ганкелевой матрицы. Понятия определителя матрицы являются общими и применимы для любого типа матрицы;

и ранга однако



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

Сопоставим с квадратной матрицей >1„ „ вида (2.1) при т = п некоторое число (вообще элемент множества к), называемое определителем, или детерминантом, обозначаемое A* ln п I п равное сумме п \ всевозможных произведений типа

где п\ ~ 1-2-...П (и - факториал); к - номер столбца матрицы =

= 1, 2, . . . , и; т - число попарных перестановок (транспозиций) упорядоченного

множества 11, 2, . . ., « в множество (aj, кг, • • • , А}» т. е. определитель равен сумме п\ произведений (с соответствующим знаком), составленных из п элементов, взятых по одному из каждой строки и по одному из каждого столбца.

Практически/вычисление определителей осуществляется путем их разложения по элементам какой-либо строки или столбца согласно формуле

(2.10)

где / = 1, 2, .. ., и; м i i п~ \ i i --ммноры элементов йг-у и д./, т. е. определители (и - 1)-го порядка, получаемые из определителя п-го порядка при вычеркивании из него / (/ )-й строки и / (/ )-го столбца.

Формула (2.10) применима для вычисления детерминантов л ю б ы х матриц.

Определитель ганкелевой матрицы (2.3) вследствие ее симметричного строения может быть вычислен по рекуррентной формуле

/ 1

+ 2 2 (-1) ~\а,м,

к,1 q

где /=1,2,..., и; и Ау i - главные определители, т. е. определители левых верхних угловых матриц порядка / и / - 1, получаемых из матрицы (2.3); mj • . ~ диагональный минор элемента главной диагонали а, т.е. определитель порядка / - 2, получаюищйся из определителя вычеркиванием /-й строки и /-го столбца; mj а, /3 ~ минор порядка / - 2, получающийся из определителя Ау J вычеркиванием строки а и столбца/3; © - множество пар, образованных из индексов элементов последнего столбца (строки) без индекса 2п - 1; 0 = 0 для и < 2. При этом принимается, что

/ = о

До= 1; М, , , = 1; 2 (...) =0.



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