7.7. Алгоритмы редуцированного БПФ

В данном разделе рассматриваются способы построения быстрых алгоритмов для вычисления СДПФ . Такое преобразование, как будет показано в гл. 10, находит применение при построении многомерных алгоритмов БПФ. Согласно определению редуцированное ДПФ определяется как

где

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

В [5, 27] Нуссбаумер для вычисления СДПФ применил метод Рейдера-Бреннера. При этом преобразование

заменяется на

Такой алгоритм вычисления СДПФ характеризуется следующими оценками арифметических операций (численные данные приведены в [5], табл. 4.4):

Рис. 7.15. Алгоритм БПФ с расщепленным основанием для СДПФ

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

Для вычисления СДПФ можно применить метод факторизации с расщепленным основанием (см. разд. 7.4). Представим матрицу В виде

Тогда после первого этапа факторизации получаем

Далее в (4.47) матрицы могут быть факторизованы по методу БПФ с расщепленным основанием (7.24).

При таком подходе к вычислению получаем минимальные из известных оценки числа нетривиальных арифметических операций

На рис. 7.15 приведен пример построения СДПФ методом расщепленного основания для случая