Лекция 13. Быстрое преобразование сигнала БПФ 2. Одноэтапный алгоритм БПФ
Лекция 13. Быстрое преобразование сигнала (БПФ)
1. БПФ Кули-Тьюки.
2. Одноэтапный алгоритм БПФ.
3. Двухэтапный алгоритм БПФ.
4. ν-этапныйй алгоритм БПФ.
5. Эффективность алгоритма БПФ.
6. Формирование начальных условий в алгоритме БПФ.
7. Вычисление ОДПФ с помощью БПФ.
, (12.17)
где
, (12.19)
· четных отсчетов;
· нечетных отсчетов.
· четных отсчетов (в порядке следования, считая от нуля);
· нечетных отсчетов (в порядке следования, считая от нуля).
В этом случае формула (13.7) может быть использована для вычисления двух -точечных ДПФ и , каждая через -точечные ДПФ…
Это начальные условия -этапного алгоритма БПФ (на рис. 13.1—13.2 — это последний -й этап).
В этом случае формула (13.7) может быть использована для вычисления -точечных… Т. о., количество формул, подобных (13.7), будет равно , а размерность ДПФ каждой из них — равна
ü количество этапов —
ü количество бабочек на одном этапе —
ü количество арифметических операций с комплексными числами для одной бабочки:
Рассмотрим на примере 8-точечного БПФ (рис. 13.2) и результаты обобщим.
Исходная последовательность
Прореженная …
Вывод: Для алгоритма БПФ отсчеты исходной последовательности должны быть расставлены
. (12.18)
Вычисляется следующим образом:
1) обе части равенства умножаются на и выполняется операция их комплексного сопряжения (символ *):