6.2. Алгоритмы БПФ по основнию r
Для данного класса алгоритмов размерность преобразования 
отсюда из (6.1) получаем 
или в транспонированной форме
Оба алгоритма БПФ имеют структуру вычислений с замещением, что экономит оперативную память процессора, однако требует переменной индексации промежуточных данных от этапа к этапу.
Можно получить другую модификацию алгоритма (6.5) или (6.6), имеющую постоянную структуру вычислений на всех этапах [3]. Алгоритм БПФ с постоянной структурой выводится из (6.5) или (6.6) на основе свойства 4.1 матриц перестановг 
(разд. 1.4). Применяя после давательно данное свойство к 
эритму (6.5), получаем
Аналогично для транспонированного алгоритма БПФ
Достоинством алгоргтмов (6.7) и (6.8) является наличие постоянной структуры вычисх ений на каждом этапе, что значительно упрощает устройство управления адресацией промежуточных данных, однако для таких алгоритмов БПФ требуется удвоение ОЗУ. В [4] рассмотрена аналогичная процедура построения алгоритмов с постоянной структурой для различных ортогональных базисов (обобщенное преобразование Уолша, преобразование Уолша - Качмарша и др.).
На рис. 6.1—6.4 приведены 
этапы вычислений соответственно алгоритмов БПФ (6.5) - (6.8).
Вычислительная эффективность алгоритмов (6.5) — (6.8) сдинакова. Точные оцпнки числа арифметических операций возможны при конкретизации способа вычислений 
Например, как и ранее, блоки 
могут быть представлены в канонической форме (4.13) [5]. Тогда мы поручаем следующие оценки числа нетривиальных вещественных операций
В табл. 6.1 приведены сценки числа нетривиальных арифметических операций для некоторых наиболее часто встречающихся на практике значений 
Из приведенных оценок следует, что наиболее привлекательными конструкциями являются алгоритмы 
для которых вычисление 
не требует умножений.
(кликните для просмотра скана)
(кликните для просмотра скана)
