Главная Помехоустойчивое кодирование или Тц матрицы, т.е. ганкелевы или теплицевы циркулянты (4.14). Далее рассматриваются свойства векторного и скалярного ГТ-преобра-зований и показывается их использование для вычисления полевой и циклической сверток. Элементы алгебры векторных ганкелевых и теплицезых матриц наД конеч-нымв полями GF(2). Наша задача - научиться быстро умножать элементы поля Галуа, заданные в векторном или полиномиальном виде. Эта задача может быть решена с помоиц>ю специальных векторно-матричных конструкций. Запишем ганкелеву и теплицеву матрицы: (г +1) (2г- 1) (4.28а) Т + 1) {2г - 1) ( + 1) г (4.286). Компонентами этих матриц являются элементы (модифицированные логарифмы) 1, 2, 3, . .. , (г - 1), г. (г + 1), .. (2г - 2), (2г - 1) поля GF(2*). Здесь знаки + " и означают обычные арифметические операции сложения и вычитания целых положительных чисел, а произведение 2г - обычное удвоение числа г. Матрицы Г и Т в форме (4.28) назовем нормальными. Заменим каждый элемент поля в нормальных матрицах Г и Т соответствующими векторами (строкой или столбцом), например, для поля GF(2) С1т(х) = = +Х+ 1: 1 2 3 2 3 4 L3 4 5 (001) (010) (100) (010) (100) (ОН) (100) (011) (IIO)J 3 2 1 4 3 2 5 4 3 (100) (010) (001) (Oil) (100) (010) U(iio) (Oil) (100) \ 0/
где t - символ Транспонирования. Подобные ганкелевы и теплицевы матрицы будем называть векторными. Необходимо подчеркнуть, что в отличие от обычных ганкелевых матриц, явля- ющйхся симметричными (относителыю главной диагонали) - см., например (4.2ff) или (2.3), векторные ганкелевы (и теплицевы) матрицы ие симметричны. т. е. Н\#НдляНб [г, Т}. Обозначим Н = [fljy ]» где компонента fly - вектор, тогда Н = [fl/y]. Другими словами, при транспонировании матриц Г и Т их векторные компоненты aj не тольк переставляются относителыю главной диагонали (как в обычном случае, когда а j-yWflyj-), но и сами транспонируются: fly ~fly/. Конечно, вследствие симметричности обычной ганкелевой матрицы можно считать, что элементы векторной матрицы г только транспонируются. Введем для матриц Г и Т операции изменения порядка строк н столбцов на противоположный. Такие перестановочные операции обозначаются двойными стрелками, записываемыми сверху символа матрицы (при перестановке столбцов) или справа от нее (при перестановке строк), например Г; Т . Ясно, что Г = Т и, наоборот, Т = Г. Введенные операции распространим и на векторы - строки и столбцы - для перестановки их компонент; напомним, что с одной из этих операций над векторами-строками мы уже сталкивались в § 4.3. Перестановочные операции для векторов связаны соотношением (fl) = (fl) например, если fl - (fl2 <о).о = (OQaiOi), (fl) = (flafliflo) I = (fl ) = (flofli fl2) = С другой стороны, заметим, что в общем случае ааФ аос; (аа) ф (fl)o!, т. е. перестановочные операции не коммутируют с операцией умножения вектора на примитивный элемент О. Например, для поля GF (2), (лс) = + +1 имеем fl а = (fl2 fli flo) а = (flQfli a2)0L = (flo fli fl2 0)= [fli (fl2 +fli)ao]; fl a = (fl2fli flo)o: = (fl2 fli flo 0) = [fli (fl2 +0)2] = [2(02 +flo)fli]. где учтено, что умножение вектора на а эквивалентно сдвигу его компонент влево на один разряд Нам понадобится также следующее наблюдение. Из представлешя (4.28) видно, что каждая последующая строка нормальной ганкелевой матрицы Г может быть получена из предыдущей умножением на примитивный элемент а = 2. Действительно, вспомним, что, согласно правилу (3.23), умножение десятичного номера (модифицированного логарифма) а на & = 2 соответствует увеличению на единицу этого десятичного номера; но в данном случаев + & < 2 так как максимальный номер в матрице (4.28а) не превосходит величины 2г ~ 1. Аналогично каждый последующий столбец матрицы Т (4.286) получается из предыдущего при умножении последнего на а~т. е. при делении на а= 2. Следовательно, матрицы Г и Т (4.28) могут быть представлены в виде: - Г1 г, а Г, а (4.29) Ti OL Ту а (4.30) где Vi - первая строка (первый столбец) в матрице Г (4.28а); - первая строка, а - последний столбец в матрице Т (4.286). Векторное ГТ-преобразование Рассмотрим произведения произвольного элемента д = (fl i . . fli flo) или а = (о i • • г -l) векторные ганкелеву и теплицеву матрицы над полем GF(2), т. е. векторные Г- и Т-преобразования. Начнем с примера. Пусть задано поле GF(2) стт{х) - + х+ i иа = (flj Oq). Прямым вычислением найдем
(01) (10) (10) (11). fll LfloJ (Ol)fli + (lO)flo L(io)fli + (11)0- (Ofli) + (floO) (fliO) + (flo flo) (fll + flo) flo (4.31) Здесь умножение матрицы на вектор осуществляется по правилу скалярного произведения строка на столбец", но с суммированием частных произведений по модулю 2. Далее учтено, что вектор на скаляр умножается покомпонентно, например (Ol)fli = (Ofli), и что векторы также складываются покомпонентно, в частности [(fliO) + (floflo)] = [(fli +flo)flo]- Наконец, на последнем этапе под мечено, что вследствие свойств выбранного поля справедливо равенство а а = (fll flo)a = (flo fli )а = (ао ai О ) = l(fl +flo) flo], так как при п{х) - х + х + I = О выполняется тождество х ~ х+ 1у позволяющее избавиться от переноса в разряд переполнения х . Результирующую квадрашую матрицу для произведения Ffl можно представить не только в виде набора строк [см. формулу (4.31) ], но и как совокупность столбцов: (fl+flo) flo = [ia a-)a] = [(a)a] = [(flafl], 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.0128 |