Лекция 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) обе части равенства умножаются на и выполняется операция их комплексного сопряжения (символ *):