Одноэтапный алгоритм БПФ

Разделим исходную N-точечную последовательность на две -точечные (начальные условия одноэтапного алгоритма БПФ):

· четных отсчетов;

· нечетных отсчетов.

Рис. 13.1. Деление исходной последовательности

Рис. 13.2. Пример деления 8-точечной последовательности

 

После этого запишем ДПФ (12.17) в виде:

где отображает четные, а — нечетные значения .

Вынесем за знак второй суммы:

, (13.2)

представим в виде:

и представим ДПФ (13.2) в виде:

, ,

и далее, с учетом обозначений сумм:

, , (13.3)

где:

—

—

и —

; (13.4)

. (13.5)

Вывод: при вычислении N-точечного ДПФ (13.3) и достаточно вычислить

Определим поворачивающей множитель на второй половине периода :

(13.6)

Вывод:при вычислении N-точечного ДПФ поворачивающий множитель достаточно вычислить

Вывод: N-точечное ДПФ (13.3) можно выразить через -точечные ДПФ и (на рис. 13.4 — это последний,-й этап):

(13.7)

Согласно (13.7), N-точечное ДПФ вычисляется:

и ;

и ;

…………………………….

и .

Размерность вычисляемого ДПФ соответствует нижнему индексу

Сокращение количества операций достигнуто за счет одновременного (параллельного) вычисления по верхней и нижней формулам!

Это оказалось возможным в результате

Одновременное вычисление по верхней и нижней формулам в (13.7) при фиксированном (одном) называют операцией «бабочка» — коротко «бабочкой» — и изображают в виде сигнального графа (рис. 13.3).

Рис. 13.3. Сигнальный граф операции «бабочка»

Для вычисления N-точечного по формуле (13.7) потребуется «бабочек».

 

Рис. 13.4. Поэтапное вычисление N-точечного ДПФ