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



матрицы ФМС-преобразования над полем GF(2) длин соответственно 3 и 5, изображенные на рис. 4.9, а и 4.10, а; ® - символ кронекеров-ского произведения - см. рис. 4.14, на котором также изображены матрицы £"3 ® ф5 и Фз ® £"5; dis = dP - диагональная матрица, рассчитанная на рис. 4.12,

Ядра матриц Фз и ф5 могут быть сформированы на базе элементов ез е ( 6, П} е GF(2) и 65 6 (4, 7, 10, 13) s GF(2*), имеющих порядки соответственно 3 и 5. На рис. 4.14 принято = 6, 65 = 4, а нулевые элементы не показаны.

Если в формуле (4.26) опустить матрицу P/s, то произведение в правой части упомянутой формулы сформирует матрицу ф15, приведенную на рис. 4.15 и отличающуюся от матрицы ф15 лишь перестановкой строк; нумерация строк, восстанавливающая матрицу ф15, указана на этом рисунке справа от матрицы 5.

Если бы мы пользовались методом взаимно простых множителей (см. § 4.1), то можно было бы опустить диагональные матрицы/) (поворачивающие множители), но пришлось бы согласно (4.9) трансформировать компоненты не только выходного у = (уо> Ji> • • • ? ун)* но и входного X = (лго, Хуу ..., л: 14) сигналов. Пусть, например, необходимо вычислить компоненту у. Воспользовавшись матрицей Ф/з на рис. 4.15, получим

у& = Хо -9x1 + 2x2 + Юлгз + 3x4 + 11л:5 +4Хб + 12x7 +

+ 5x8 + 13x9 + бхю + 14хи + 7xi2 + 15xi3 + 8x14, (4.27)

Вычислим теперь у с учетом факторизации ф (£3 ® ф5) X X (Фз ® £5), где кронекеровские произведения матриц вычислены на рис. 4.14. Умножая х на (ф3 ® es), найдем промежуточный вектор Z = (Zo, Zi,.. • , м)- В свою очередь, умножая z на (£3 ® ф5), можно вычислить вектор у. Однако по условию нас интересует только компонента у, т.е. в матрице (£3® ф5) используется лишь вторая снизу строка, первые 10 компонент которой равны нулю. Следовательно, достаточно вычислить только пять промежуточных величин Zio> . •., z 14, для нахождения которых можно использовать пять правых столбцов в матрице (Фз ® я5).

Итак, с учетом перестановок (4.9) имеем: Zio = Xq + IIX5 + бХю;

Zii = Хз + llXg + 6X13; Z12 = Хб + ИХп +6X1; Zi3 = Х9 + llXi4 +6x4;

Zi4 = Х12 + 11X2 + 6X7.

Умножая теперь эти компоненты на вторую снизу строку в матрице 3 ® Фз > получим

38 =10 + 10Z11 +4zi2 + 13zi3 +7zi4, GF(2),



Размеры:

X kl

11111 1 4 7 10 13

1 7 13 4 10

1 10 4 13 7

1 13 10 7 4

1 "

1 i 1 1 1

1 4 7 10 13

1 7 13 4 10

1 10 4 13 7

1 13 10 7 4

12 3 9

10 1 7

13 4 5

8 14

В = Фз0 £s =

1 1 1 1 6 11 1 11 6

О 3 6 9 12 I 5 8 И 14 2

10 13 14 7

ftic. 4.14. Кронекеровское произведение матриц (нулевые компоненты матрицы исключены)




Рис. 4.15. Факторизация матрицы Фд

что после преобразований дает выражение (4.27).

Более подробные сведения о преобразованиях ФМС, ДПФ и БПФ можно найти в литературе [2, 10, И, 16, 20, 24, 26, 37, 39,45, 58].

4.4. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ

ГАНКЕЛЯ - ТЕПЛИЦА

Назначение ГТ-преобразования.

на матрицах (4.13), позволяет при вычислениях над полями Галуа обходиться без традиционных таблиц логарифмов. Более того, с помощью ГТ-преобразования можно не только вычислять полевые свертки, т. е. находить произведения элементов поля Галуа, но и синтезировать как простые, так и быстрые схемы для таких вычислений. Однако и этим не исчерпываются замечательные свойства этого преобразования ... Наблюдательный читатель, конечно, заметил, что полевая свертка вычисляется по более сложному правилу, чем циклическая: при переполнениях разрядной сетки действию обратной связи подвержен не только младший разряд (как у циклической свертки), но и некоторые более старшие разряды. Возникает резонный вопрос: нельзя ли так приспособить ГТ-преобразование, пусть в модифицированном виде, чтобы оказалось возможным вычисление циклической свертки? Ока-

можно

для этого достаточно использовать циклические Гц



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