Этапныйй алгоритм БПФ

Продолжим процесс разделения исходной последовательности (сохраняя принцип чет и нечет) до тех пор, пока не будет получено групп, каждая из которых содержит , один из которых , а второй —

Это начальные условия -этапного алгоритма БПФ (на рис. 13.1—13.2 — это последний -й этап).

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

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

Запишем одну из этих формул, используя условные обозначения и — четный и нечетный отсчеты, а и — отсчеты 2-точечного ДПФ:

(13.10)

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

Дальнейшие этапы представлены на рис. 13.1—13.2 (снизу вверх).

На последнем -м этапе будет вычислено N-точечное ДПФ .

На каждом их этапов выполняется «бабочек».