Главная Помехоустойчивое кодирование с векторами А и А длины п или п- \ следующим образом свяжем юлиномы 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) имеет следующее представление:
(2.7) т. е. a2 0 +аза„ 1 + . -. + ai = 62; (2-8) Как уже отмечалось, от ганкелевой матрицы можно перейти к теплицевой. Действительно, изменив в каждой строке системы (2.8) порядок слагаемых на обратный, получим в екторно-матричное уравнение (2.6а), аналогичное (2.7), но с теплицевой матрицей и с прямым вектором а. Далее ограничимся рассмотрением системы (2.7) с ганкелевой матрицей. Теплицева или ганкелева матрица с дополнительным свойством а. =а, i =1, 2, называется циклической {циркулярной или просто циркулянтом). Например, для л = 4 имеем следующие циркулянты:
- теплицев (правый); (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 |