Двухэтапный алгоритм БПФ

Продолжим процесс разделения исходной последовательности (на рис. 13.1—13.2 — это второй этап): каждую из -точечных последовательностей разделим на две -точечные последовательности (начальные условия двухэтапного алгоритма БПФ):

· четных отсчетов (в порядке следования, считая от нуля);

· нечетных отсчетов (в порядке следования, считая от нуля).

В этом случае формула (13.7) может быть использована для вычисления двух -точечных ДПФ и , каждая через -точечные ДПФ (на рис. 13.4 — это предпоследний, -й этап):

(13.8)

(13.9)

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

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

Для вычисления ДПФ и потребуется «бабочек».

Значения -точечных ДПФ и далее используются для вычисления N- точечного ДПФ по формуле (13.) (на рис. 13.4 — это последний, -й этап).