Разделим исходную 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-точечного ДПФ