资料介绍
合工大信号处理课件 3.3 快速傅里叶变换
*FFT 并 不 是 一 种 新 的 变 换 形 式,
它 只 是 DFT 的 一 种 快 速 算 法 。并
且根据对序列分解与选取方法的
不 同 而 产 生 了 FFT 的 多 种 算 法 。
计算DFT复数运算量
)计算一个X (k)值,运算量为
N 1
例k=1则 X (1) = ∑ x(n)W
n
N
n =0
要进行N次复数乘法,(N-1)次复数加法
所以,要完成整个DFT运算,其计算量为:
N*N次复数相乘,N*(N-1)次复数加法
kn
利用 N 的固有对称性和周期性
W
改善DFT的运算效率
nk
W kn
N 的对称性: N (W ) = W
kn *
N
kn ( n+ N ) k n( N +k )
W N 的周期性: N
kn
W =W N =W N
2π
j kN