文档介绍：Fast Fourier Transform
YANG Boyang
1
2
1 Demonstration of FFT
2 The DFT and FFT
3 Polynominal Multiplication〔多项式乘法〕
Outline
3
This demonstration uses the FFT function to analyze the variations in sunspot activity over the last 300 years.
Sunspot activity is cyclical, reaching a maximum about every 11 years.
Astronomers have tabulated this number for almost 300 years.
1 Demostration of FFT
4
1 Demostration of FFT
5
Result of FFT
1 Demostration of FFT
6
Power(norm of complex) vesus frequency
1 Demostration of FFT
7
Select the first 40 period (0-40years)
The strongest period is
1 Demostration of FFT
8
complex roots of unity and their properties
〔单位复数根及其性质〕
DFT (Discrete Fourier Transform, 离散傅里叶变换)
how the FFT (Fast Fourier Transform, 快速傅里叶变换) computes the DFT and its inverse in just Θ(n lgn) time
2 The DFT and FFT
9
ωn = 1 , complex number ω is a complex nth root of unity
〔ω称为 1 的 n 次复根，或单位 n 次复根〕
ωn=e2πi/n : principal nth root of unity 〔单位 n 次复根的基元〕
exactly n complex nth roots of unity
〔单位 1 有 n 个 n 次复根〕
eiu=cos(u)+i sin(u) :
the exponential of a complex number
Complex roots of unity
10
some properties
Complex roots of unity