dsp-11-11.ppt

文档介绍：203
FFT的原理和复杂性
按时间抽取FFT的算法
按频率抽取FFT的算法
第十一讲快速 Fourier 变换(FFT)
204
对每个特定 k , X(k)的 DFT的计算:有(N-1) 个复加和N 个复乘;

计算整个DFT 共有N (N-1)个复加和N 2 个复乘;
通过利用W N k n的对称性和周期性,整个DFT 的复乘计算量可减
至为 N log 2 N
 Fast Fourier Transform (FFT).
FFT 算法的原理
205
FFT 算法的原理(续)
复杂性与N的关系:

序列长度复乘复加
N N2 N(N-1)
16 256 240
32 1024 992
64 4096 4032
128 16384 16256
 1个复乘: 4 四个实乘和 2 个实加;
 1 复加: 2实加;
 W N n k的特性:
☆ W N k(N-n)=W N - n k = ( W N n k)* ----复共轭对称性;
☆ W N n k = W N k(N+n) = W N n(N+ k) ----关于 n 和 k的周期性.
206
FFT 算法的原理(续)
对称性的运用:
计算量可减小一半。
207
1)原理: 设序列长度为N=2m,将x[n] 分成偶和奇两个部分:
按时间抽取FFT(DIT)
式中, g[n]= x[2n], h[n]= x[2n+1], 若 N= 2m, 则这种迭代共需进行 m次完成.
复杂性: 每级需要 N 次复加和复乘.
208
按时间抽取FFT(续)
209
按时间抽取FFT(续)
K=0,1,…,N-1
K=0,1,…,N/2-1
K=0,1,…,N/4-1
N=16
N/2-点 DFT
N/4-点 DFT
N/8-点 DFT
329
N/2=4
Points
DFT
G(k)
N/2=4
Points
DFT
H(k)
-1
-1
-1
-1
按时间抽取FFT(续)
2)
计
算
流
图
329
按时间抽取FFT(续)
2-point
DFT
-1
-1
-1
-1
2-point
DFT
2-point
DFT
2-point
DFT
-1
-1
-1
-1
212
按时间抽取FFT(续)
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1