第4意快速傅里叶夜换(H 式中 x,(k)=2 X3 (DWN14-=DFT[x,(0 N/4-1 x4(k)=>x4(IW/4=DFT[x() 同理,由X3(k)和X4(k)的周期性和WmN2的对称 性Wk+N/4N2=WN2最后得到: X(k)=X,(k)+Wwnx(k) k=0,1,…,N/4-1(4210) X1(k+N/4)=X3(k)-WN2X4(k)
第4章 快速傅里叶变换(FFT) 式中 / 4 1 3 3 / 4 3 0 / 4 1 4 4 / 4 4 0 ( ) ( ) [ ( )] ( ) ( ) [ ( )] N kl N i N kl N i x k x l W DFT x l x k x l W DFT x l − = − = = = = = 同理，由X3 (k)和X4 (k)的周期性和Wm N/2的对称 性 Wk+N/4 N/2 =-Wk N/2 最后得到： 1 3 / 2 4 1 3 / 2 4 ( ) ( ) ( ) , 0,1, , / 4 1 ( / 4) ( ) ( ) k N k N X k X k W X k k N X k N X k W X k = + = − + = − (4.2.10)
第4意快速傅里叶夜换(H 用同样的方法可计算出 X2(k)=X5(k)+WN2X6(k) k=0,1,…N/4-1(42.1) X2(k+N/4)=X(k 其中 N/4-1 Xs()=2x(OWN/4=DFTLxs(D N/4-1 X6(k) 0 xpk=DFT[() N/4 x5()=x2(2) 1=0.1.…N/4-1 x6()=x2(2/+1)
第4章 快速傅里叶变换(FFT) 用同样的方法可计算出 2 5 / 2 6 2 5 / 2 6 ( ) ( ) ( ) , 0,1, / 4 1 ( / 4) ( ) k N k N X k X k W X k k N X k N X k W X k = + = − + = − (4.2.11) 其中 / 4 1 5 5 / 4 5 0 / 4 1 6 6 / 4 6 0 5 2 6 2 ( ) ( ) [ ( )] ( ) ( ) [ ( )] ( ) (2 ) , 0,1, / 4 1 ( ) (2 1) N kl N i N kl N i X k x l W DFT x l X k x l W DFT x l x l x l l N x l x l − = − = = = = = = = − = +
第4意快速傅里叶夜换(H M4点七0 X1(O) Y(0) x1(1) x(4) DFT X, (1) X(1) X,(2) (2) M4的(0) X(2) DFT X4(1) x(6) X1(3) X(3) x2(O) N4点 X(4) DFT X X(1)不 X2(2) N4点 X(6) DET X2(3) x(7) 图42.3N点DFT的第二次时域抽取分解图(N=8)
第4章 快速傅里叶变换(FFT) 图4.2.3 N点DFT的第二次时域抽取分解图(N=8) N/ 4点 DFT W N 1 2 W N 1 2 W N 0 W N 1 W N 2 W N 3 X1 (0) X1 (1) X1 (2) X1 (3) X2 (0) X2 (1) X2 (2) X2 (3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x(0) X3 (0) X3 (1) X4 (0) X4 (1) x(4) x(2) x(6) x(1) x(5) x(3) x(7) N/ 4点 DFT N/ 4点 DFT N/ 4点 DFT W N 0 2 W N 0 2
第4意快速傅里叶夜换(HI A(0) A(0) A(0) A(0) A(1) A(1) A(1) x(4) A(2) A(2) A(2) x(2) X(2) x(6) A(3) A(3) A(3) X(3) A(4) A(4) X(4) A(5) A(5) A(5) x(5) wN A6)Wo X(5) A(6) A(6) x(3) X(6) A(7) A(7) x(7) WN AO WN A)X(7 图424N点D—FFT运算流图(N=8)
第4章 快速傅里叶变换(FFT) 图4.2.4 N点DIT―FFT运算流图(N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7)
第4意快速傅里叶夜换(H 42.3DIT—FFT算法与直接计算DFT运算量的比较 每一级运算都需要N2次复数乘和N次复数加(每个 蝶形需要两次复数加法)。所以,M级运算总共需要的 复数乘次数为 N CM(2 M log w 2 复数加次数为 CA(2)=N·M=Nlog2N 例如,N=210=1024时 N 1048576 =204.8 (N/2)log2N5120
第4章 快速傅里叶变换(FFT) 4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个 蝶形需要两次复数加法)。所以，M级运算总共需要的 复数乘次数为 2 2 (2) log 2 2 (2) log M A N N C M N C N M N N = = = = 复数加次数为 例如，N=2 10=1024时 2 2 1048576 204.8 ( / 2)log 5120 N N N = =