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



или Тц матрицы, т.е. ганкелевы или теплицевы циркулянты (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/



\o ,

где 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). Прямым вычислением найдем

1 2

2 3

(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