7.7. Алгоритмы редуцированного БПФ
В данном разделе рассматриваются способы построения быстрых алгоритмов для вычисления СДПФ 
. Такое преобразование, как будет показано в гл. 10, находит применение при построении многомерных алгоритмов БПФ. Согласно определению 
редуцированное ДПФ определяется как
где
Очевидно, что 
в (7.46) может быть факторизована любым из рассмотренных в главе способом. Например, в случае использования для 
стандартного БПФ по основанию 2, получаем следующие оценки числа арифметических операций для 
В [5, 27] Нуссбаумер для вычисления СДПФ 
применил метод Рейдера-Бреннера. При этом преобразование
заменяется на
Такой алгоритм вычисления СДПФ 
характеризуется следующими оценками арифметических операций (численные данные приведены в [5], табл. 4.4):
Рис. 7.15. Алгоритм БПФ с расщепленным основанием для СДПФ 
Аналогичные результаты дает способ факторизации, определяемый выражением (7.11).
Для вычисления СДПФ 
можно применить метод факторизации с расщепленным основанием (см. разд. 7.4). Представим матрицу В виде
Тогда после первого этапа факторизации получаем
Далее в (4.47) матрицы 
могут быть факторизованы по методу БПФ с расщепленным основанием (7.24).
При таком подходе к вычислению 
получаем минимальные из известных оценки числа нетривиальных арифметических операций
На рис. 7.15 приведен пример построения СДПФ 
методом расщепленного основания для случая 
