Быстрое преобразование Фурье (БПФ)

1. Быстрое преобразование Фурье (БПФ)

Володин Георгий Викторович

2. БПФ = быстрое ДПФ

БПФ – не является новым видом ПФ, это
набор алгоритмов эффективного
вычисления дискретного преобразования
Фурье
ДПФ =>
Кол-во операций:
N – перемножения комплексных чисел
(N-1) – сложения комплексных чисел
Для k точки спектра!

3. Эффективность БПФ по сравнению с ДПФ

• O(N^2) – скорость вычисления для ДПФ,
где мы опускаем сложение
VS
• O(N*Log2(N)) – скорость вычисления для
БПФ, и скоро мы увидим почему
N
100
10^6
10^9
N^2
10000
10^12
10^18
2*10^7
3*10^10
N*log2(N) 665
Если процессор имеет скорость 1 выч/нс, то
для ДПФ 10^9 будет найдено за 32 года, а с
использованием ПБФ всего за 30 секунд
N^2
N*log2(N)

4. Проблема поворачивающего множителя в ДПФ