Продолжим процесс разделения исходной последовательности (на рис. 13.1—13.2 — это второй этап): каждую из -точечных последовательностей разделим на две -точечные последовательности (начальные условия двухэтапного алгоритма БПФ):
· четных отсчетов (в порядке следования, считая от нуля);
· нечетных отсчетов (в порядке следования, считая от нуля).
В этом случае формула (13.7) может быть использована для вычисления двух -точечных ДПФ и , каждая через -точечные ДПФ (на рис. 13.4 — это предпоследний,-й этап):
(13.8)
(13.9)
Т. о., количество формул, подобных (13.7), , а размерность вычисляемого ДПФ в каждой из них
Размерность вычисляемого ДПФ соответствует нижнему индексу
Для вычисления ДПФ и потребуется «бабочек».
Значения -точечных ДПФ и далее используются для вычисления N-точечного ДПФ по формуле (13.) (на рис. 13.4 — это последний,-й этап).