Главная > Разное > Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.6. Факторизация ДПХ для взаимно-простых множителей

Пусть . Матрица ДПХ может быть представлена в виде

где — матрица перестановки, определяемая правилом (3.5). Из (3.39)

матрица имеет вид

Матрица может быть представлена через послойно-кронекеровское произведение матриц как

По аналогии с предыдущими рассуждениями применим к и теорему 1.3 и представим номер строки к в виде (3.7). Тогда первое слагаемое преобразуется так:

Как было показано в разд. 3.2 при выполнении условия перестановки следует выбирать по правилам (3.13). Тогда

Отсюда для получаем

Множитель окончательно преобразуется к выражению

В сомножителе переставим местами знаки послойной и прямой сумм. В этом случае для матрицы перестановки сохраняется отображение (3.13) для в котором теперь сначала изменяется переменная затем к у. Отсюда

Таким образом, Аналогично получаем выражение для

Можно показать (по аналогии с предыдущим разделом), что

Тогда, подставляя приведенные соотношения в (3.40) и затем в (3.39), окончательно получаем

Приведем два частных случая общей формы факторизации (3.32), полезные для практики:

1) тогда и матрица перестановки, определяемая правилом "руританского" соответствия;

Как следует из (3.43), данная форма факторизации с точностью до перестановок изоморфна векторно-матричному представлению двумерного несепарабельного т.е. если в одномерном ДПХ

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

Данное выражение также можно определить как аналог факторизации Гуда [2] для дискретного преобразования Хартли.

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

Так как перестановочна с матрицами то согласно определению (см. (2.59) и матрица перестановочна с . Отсюда окончательно

Аналогичными преобразованиями можно рекуррентно построить факторизацию при где

матрицы перестановок руританского (1.10) и китайского (1.11) соответствий.

Если сравнить выражения (3.45) и (2.64), то очевидно, что они с точностью до перестановок совпадают, поэтому (3.45) можно переписать в виде

где матрица многомерного несепарабельного

<< Предыдущий параграф Следующий параграф >>
Оглавление