6.3. Некоторые свойства алгоритма БПФ с основанием 2 и прореживанием по времени

Анализ графа на фиг. 6.3 и процедуры последовательного сокращения вдвое размеров преобразований показывает, что на каждом этапе БПФ (т. е. при каждом сокращении размеров ДПФ) необходимо выполнить  комплексных умножений. Поскольку общее количество этапов равно , то число комплексных умножений, необходимое для нахождения -точечного ДПФ, приблизительно равно . Слово приблизительно использовано по той причине, что умножения на  и  в действительности сводятся просто к сложениям и вычитаниям комплексных чисел. Так, например, на фиг. 6.3 первый этап БПФ содержит только сложения и вычитания комплексных чисел. Даже на втором этапе используются только сложения и вычитания комплексных чисел. Фактически, как следует из направленного графа на фиг. 6.3, вместо ожидаемых 12 (т. е.) достаточно выполнить всего два нетривиальных умножения. Однако для больших значений  фактическое число нетривиальных умножений хорошо аппроксимируется выражением .

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

Базовая операция алгоритма с прореживанием по времени (так называемая «бабочка») состоит в том, что два входных числа  и  объединяются для получения двух выходных чисел  и  следующим образом:

                       (6.14)

На фиг. 6.4 изображен направленный граф базовой операции (6.14). Внимательное рассмотрение направленного графа на фиг. 6.3 показывает, что каждый из этапов содержит  базовых операций.

Фиг. 6.4. Базовая операция алгоритма БПФ.

В случае когда множитель  - нетривиальный, для каждой базовой операции необходимо выполнить только одно умножение, поскольку величину  можно вычислить и запомнить. Таким образом, структура базовых операций такова, что для выполнения БПФ -точечной последовательности, размещенной в памяти, достаточно иметь лишь одну дополнительную ячейку памяти. Результаты всех промежуточных этапов БПФ можно размещать в те же ячейки памяти, где находились исходные данные. Поэтому для хранения и входной, и выходной последовательностей можно использовать один и тот же массив ячеек памяти. Алгоритм, в котором для размещения входной и выходной последовательностей используются одни и те же ячейки памяти, называется алгоритмом БПФ с замещением.

На фиг. 6.5 алгоритм БПФ с основанием 2 иллюстрируется несколько иначе. Все ДПФ являются двухточечными и не требуют операций умножения.

Фиг. 6.5 Типичное разложение для алгоритмов БПФ с основанием 2.

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