42基2FF算法 有限长序列x(n)的N点DFT为 X(k)=∑x(m)Wk=0,1,…,N-1 可得,计算X(k的所有N个值,共需NN次复数乘法和 NN-1)次复数加法运算。 结论:大的运算量将导致实时信号处理发生困难
42基2FF算法 ◆减少运算量的途径 口把N点DFT分解为几个较短的DFT,可使乘法次数大大减少 口充分利用旋转因子的周期性和对称性,即 W 周期性:N=N(m-)-2mm 2丌 对称性:W=WAm,[WN]=W,W+2=-W
42基2FF算法 ●时域抽取法基2FFT基本原理 基于2FFT算法分为 ◆时域抽取法FT( Decimation-In- Time fft, DIT-FFT) ◆频域抽取法FFT( Decimation-In- Frequency FFT,DIT- FD
42基2FF算法 ◆DIT-FFT算法 设序列X(n)的长度为N,且满足 N=2M,M为自然数 按n的奇偶把x(n)分解为两个N2点的子序列 N X, (r)=r(2i =0,1, N x2(r)=x(2r+1),r=0,1,…-1
42基2FF算法 Ⅹ(n)的DFT为 X(k)=∑x(n)W+∑x(n)W nEcr+ N/2-1 x(2)W x(2r+1)W(2+ ∑x(rW r,(r)w kr 由于 W2kr se'N e 2-wkr N/2 所以 X(k)=∑x(W2+W∑x2(T)W2=X()+WX2(k)