10.2. Методы построения гнездовых алгоритмов «квадратного» ДПФ-m

"Квадратное" класс ДПФ -мерных массивов одинаковой координатной размерности Гнездовые алгоритмы вычисления "квадратного" ДПФ основаны на векторно-матричном определении ДПФ (2.16):

где (аналогично

Пусть Тогда согласно одномерное может быть факторизовано в виде быстрого алгоритма

где матрица цифроинверсной перестановки по основанию -точечное

Путем несложных преобразований можно показать, что на основании свойства 5 кронекеровского произведения матриц (разд. 1.2) возможна факторизация ДПФ-m вида

Из (10.13) непосредственно следует, что число этапов вычислений остается прежним, равным что в общем случае дает в оценке (10.3) вычислительной сложности коэффициент

Матрицы в (10-13) могут быть вычислены методом однако эффективнее выполнять вычисления, используя базовые модули В этом случае умножение на вектор промежуточных данных вычисляется через блоки

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

где

При формировании матриц в (10.15) при вычислении элементов последовательно варьируются переменные затем

Подставляя (10.14) в (10.13), получаем следующую запись алгоритма БПФ-w

Очевидно, что каждое в (10.16) также может быть вычислено с помощью гнездового метода. Если представимо в канонической форме (4.13) (или (4.14), (4.15)), то для получаем следующую запись гнездового алгоритма [15]

Недостатком такого подхода к построению базовых модулей является расширение пространства коэффициентов, число которых становится равным что для некоторых нежелательно. С другой стороны, для небольших эффективным является метод полиномиальных преобразований, причем, если простое, наиболее перспективным является алгоритм, основанный на методе смещенного ПП [16].

Например, для двумерного блока ДПФ выполняются вычисления

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

Присущий методу ПП недостаток — сложность перестановочных операций, здесь не существен, так как перестановки вида к выполняются на малом адресном поле памяти.

Общее число нетривиальных вещественных операций для алгоритма БПФ-2 типа (10.16) равно

В оценке (10.19) считается, что одно комплексное умножение выполняется за три вещественных умножения и три вещественных сложения.

Из (10.19) для некоторых частных случаев следует:

Из (10.16) следует, что каждый этап гнездового алгоритма БПФ-m выполняется за два подэтапа.

1. Из матрицы промежуточных данных считывают подматрицы по координатам согласно (10.15), по которой определяется спектр

2. Матрица поточечно умножается на матрицу весовых коэффициентов

где

и координаты приведеныв (10.15). Каждый элемент полной матрицы весовых коэффициентов равен

где

Полученный результат записывается во внешнее ОЗУ по координатам

Таким образом, для алгоритма характерны вычисления с замещением, отсюда общая емкость внешнего ОЗУ составляет вещественных слов.

На рис. 10.3 приведена блок-схема этапа вычислений алгоритма по основанию

Если объем внутреннего ОЗУ достаточен, чтобы записать строк по комплексных элементов комплексных слов), то при файловой записи данных на диске (ленте), где в каждом файле записана одна строка, не требуется выполнения операции транспонирования, так как считывается сразу полных строк, над ними раз выполняется

Рис. 10.3. Структура двумерной базовой операции размерностью

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

В (10-22) слагаемое появляется за счет необходимости перестановки данных после окончания основных вычислений.

Отметим, что для общее число циклов считывания/записи в пересчете для каждого отсчета составляет [14]

что для больше, чем оценка (10.22).

Приведем наиболее простые примеры построения гнездовых алгоритмов БПФ-2 для случая :

1. Алгоритм БПФ-2 с замещением

Граф алгоритма (10.24) изображен на рис. 10.4,

2. Алгоритм БПФ-2 с постоянной структурой

где Граф алгоритма (10.25) приведен на рис. 10.5.

В теории одномерных алгоритмов БПФ в случае минимальными оценками вычислительной сложности (для арифметики в поле комплексных чисел) обладает алгоритм БПФ с расщепленным основанием (Split - Radix, см. гл. 7). Рассмотрим методику синтеза гнездового алгоритма БПФ-2 с расщепленным основанием. После первого этапа факторизации ДПФ-2 получаем

где

Рис. 10.4. Граф алгоритма двумерного БПФ (4x4) с замещением

Рис. 10.5. Граф двумерного БПФ (4X4) с постоянной структурой

Факторизуем соответственно в виде

где

где

Отсюда

Таким образом, согласно методике расщепленного основания разбивается на одно нетривиальных вещественных умножений, следовательно, вычислительная сложность данного алгоритма БПФ-2 по числу умножений определяется рекуррентным выражением

решение которого дает оцежу

Число сложений для алгоритма БПФ-2 с расщепленным основанием равно