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



«2 = 0 «2 = 1

«2=0 «2=1

1 1 1 -1

е2 = У1~=ехр(/2я/2) =-1

«3 = 0 «3 = 1 «3=2

«3 =

1 1

«3 =

.1 el

6з = -УГ -ехр(/2я/3);

t = e.

«4=1

«4

= 1

«4 =

i -

64 = -1"= ехр(/2

я/4) =

= el

1=6$;

/; et-

Wa =

еб -

/=4. 9 -.15

Рис 4.2. примеры ядер дискретного преобразования Фурье на циклических группах

порядков 2 (a)yn= 3 {6)yn~ 4 (в) иЛ= 6 (г)

ПО рядка

их ядра в зависимости от порядка и типа абелевой группы g. Вид характера Ха(л:) группы g определяется множителями числа n - этой группы.

Заметим, что матрицы преобразований Уолша (ПУ), Крестенсона (ПК), Виленкина-Крестенсона (ПВК) могут быть упорядочены различными способами [45], однако здесь на вариантах упорядочения останавливаться не будем.



Из табл. 4.2 следует, что перечисленные преобразования задаются на абелевой группе, разложимой в однотипные группы одного и того же порядка. Такая абелева группа циклической не является и не может быть использована для организации ДПФ. Только преобразование Пон-тигина - Виленкина - Крестенсона (ППВК) изоморфно ДПФ, но при

дополнительном условии, что все - взаимно простые числа. Остальные преобразования (ПУ, ПК, ПВК) упоминаются потому, что с их помощью легче всего иллюстрировать идею быстрых алгоритмов преобразований, основанных на факторизации матриц.

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

таблица 4.2

Классификация основных дискретных преобразований иа конечном множестве

точек Ли над полем комплексных чисел с

Группа g

Порядок

n= р

Цикличе-

ская g

Срф ... Ф Gp

Дискретное преобразование

ФурЬе

Уолша

Крестенсона, р > 2 ~ простое число

Ядро преобразования (характеры х)

Х(х)= ехр(/

Х(х) = е=(-1), пг

1 = 1

= ехр /

р 1-1

@... Ф (ji

Виленкина- Крестенсона, г ~ целое положительное число

Понтрягина- Виленкина - Крестенсона, - целое положительное (произвольное)

число

х(х) = ехр 1/~ S a-Xj- W i = 1

1=1 i

Oii Xi

. 2я

г

примечание, т - количество групп; сг, gp,gf. и gf. - абелевы группы

порядков 2, р, г и Kj; j = ~ мнимая единица; Ф ~ символ прямой суммы групп.



Пусть задана матрица W. как ядро ДПФ. Тогда тензорная степень

W формирует следующие ядра преобразований: Уолша при г = 2;

Крестенсона при г =/7 (р-простое число); Виленкина-Крестенсона при целом положительном г. Так, для преобразования Уолша порядка Л= 4 получим

[2]

1 1 1 -1

®

1 1 1 -1

1 1

1 -1

(4.3)

Идея факторизации матрицы, равной тензорному произведению, состоит в следующем. Пусть дано произведение ® W, Используя единичные матрицы Еа, Efy порядков соответственно а и б, а также свойство тензорного произведения (1.41), получим

Wa®W= (Еа W) ® (WE) = (Еа ® W) (W ® Е).

Например, имеем W2® W2= {Ег Щ) ® {Щ Ег) = (2 ® Нз) (Нз ® Е2) =

1 1

1 -1

1 -1

(4.4)

где пустым позициям соответствуют нули.

Скалярно перемножив слабозаполненные матрицы в (4-4), можно убедиться, что будет получена матрица (4.3). Вычисления по формуле (4.4) выполняются за две итерации, причем вычислительный процесс может быть распараллелен. С увеличением числа итераций т (длины преобразованияЛ= 2"), число операций уменьшается [37, 39].

В общем случае факторизация матриц порядков 2", р", основана на соотношении [26]

(4.5)

где S

р - простое число (система Крестен-натуральное число (система Виленкина-Крестенсона). Как уже отмечалось, преобразования ПУ, ПК, ПВК не изоморфны

= 2 (система Уолша), s сона), S = г -

ДПФ. Однако используя приведенный процесс факторизации матрицы



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