3. БАЗОВЫЕ ФОРМЫ ФАКТОРИЗАЦИИ

Для создания универсальной теории быстрых алгоритмов типа ДПФ или ДПХ (а в общем случае — для любых N - периодических преобразований) необходимг определить базовые формы факторизации матриц при раэлс жении длины преобразования на два множителя На основе таких базовых форм факторизации возможна помощи рекррентн процедур общая факторизация при разложении длины преобразования да и множителей, которая и определяет структ; быстрых алгоритмов.

При разложении длины преобразования на два множителя возможны два варианта:

1) случай произвольных множителей, когда

2) случай взаимно-простых множителей, когда

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

В данной главе будут рассмотрены факторизации матриц ДПФ и ДПХ для обоих вариантов.

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

Пусть тогда матрицу ДПФ можно представить в следу ющей послойно-кронекеровской форме:

Введем следующее обозначение. вектор-строка из элементов, тотда

Согласно теоре не 1.3 из (3.1) получаем

Ппедставим номер в позиционной сиоеме по смешанному основанию тогда отсюда

Так как то второй член в можно переписать в виде

где матрица ДПФ размерности т.е.

Матрицу можно переписать в виде В тогца

Выражение (3.2) можно дале упростить, если в поменять и знаки послойной и прямой сумм. этого достаточно ввести матрицу цифрои тереной перестановки тогда

где матрица диагональная матрица весовых коэффициентов, равная

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

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

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

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

где

Очевидно, что такое представление возможно когда номер столбца матрицы можно представкть в виде

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

где предсавимо в виде

Аналогично можно представить номер строки k

В этом случае вводится матрица перестановки определяемая правилом (3.7)

Выполняя над (3.6) преобразования, а логичные проведенным выше, и учитывая при этом разложение окончательно получаем

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

итак, при произвольном представлении пик матрица может быть факторизована на произведение трех матриц. Очевидно, что представление (3.8) не эффективно для практических вычислений, так как размерности пере множенных матриц больше исходной Для упрощения (3.8) необходим» ввести ограничения на выбор а именно из (3.8) следует, что целесообразно определить в виде где сохраняющие однозначность отображений. Отсюда

Подставляя (3 9) в (3.8), после аналогичных (3.1) — (3.3) преобразований окончательно получаем

где матрицы перестановок, определяемые правилами (3.9), и согласио (1.5) и имею смысл перехода в обобщенную систему счисления, и матрицы ДПФ со смещенными ядрами, т.е.

На рис 3 1. приведена полученная базовая форма факторизации. Из (3.10) можно выделить следунгцие частные случаи , тогда

Рис. 3.2. Базовая факторизация ДПФ для двух -простых множителей