第4意快速傅里叶夜换(H 则x(m)的DFT为 X()=∑x(m)W+∑x(n)W如 N/2-1 ∑x(2)W+∑x(2r+1 k(2r+1) ∑x(m)+W 2kr 由于 r=0 r=0 2kr r kr- N/2 所以 N/2-1 X(k)=∑x()W2+W∑x2()2=X1(k)+WK2(k) r=0
第4章 快速傅里叶变换(FFT) 则x(n)的DFT为 / 2 1 / 2 1 2 (2 1) 0 0 / 2 1 / 2 1 2 1 2 0 0 ( ) ( ) ( ) (2 ) (2 1) ( ) ( ) kn kn N N n n N N kr k r N N r r N N k kr N N r r X k x n W x n W x r W x r W x r W x r W = = − − + = = − − = = = + = + + = + 由于 2 2 2 2 2 2 / 2 j kr N j kr kr kr N W e e W N N − − = = = 所以 / 2 1 / 2 1 1 / 2 2 / 2 1 2 0 0 ( ) ( ) ( ) ( ) ( ) N N kr k kr k N N N N r r X k x r W W x r W X k W X k − − = = = + = +
第4章快速傅里叶夜换(FEE) 其中X(k)和X2(k)分别为x1(r)和x2r)的N2点DFT, N/2-1 X,(k)=>,(r)W/2=DFT[,(r) (4.2.5) X2(k)=2 x2(r)WT2=DFT[x2(r) (4.2.6) 由于X1(k)和X2(k)均以N2为周期,且 WN2=-W,所以X(k)又可表示为 X(k)=X1(k)+WX2(k)k0,N-1 (4.2.7) X(k、N、x)所X2(k)k=02… (4.2.8)
第4章 快速傅里叶变换(FFT) 其中X1 (k)和X2 (k)分别为x1 (r)和x2 (r)的N/2点DFT， 即 / 2 1 1 1 / 2 1 0 / 2 1 2 2 / 2 2 0 ( ) ( ) [ ( )] ( ) ( ) [ ( )] N kr N r N kr N r X k x r W DFT x r X k x r W DFT x r − = − = = = = = (4.2.5) (4.2.6) 由于X1 (k)和X2 (k)均以N/2为周期，且 2 ，所以X(k)又可表示为 N k k W W N N + = − 1 2 1 2 ( ) ( ) ( ) 0,1, 1 2 ( ) ( ) ( ) 0,1, 1 2 2 k N k N N X k X k W X k k N N X k X k W X k k = + = − + = − = − (4.2.7) (4.2.8)
第4意快速傅里叶夜换(H a+BC B A- BC 图42.1蝶形运算符号
第4章 快速傅里叶变换(FFT) 图4.2.1 蝶形运算符号 C A B A＋ BC A－ BC
第4意快速傅里叶夜换(H X1(0) X(0) N2点X1(1) X(1) x1(2) X(2) DET x1(3) X(3) X(4) N2点X2(1) X(5) x2(2) x(5 X(6) DET x2(3) X(7) 图422N点DFT的一次时域抽取分解图(N=8)
第4章 快速傅里叶变换(FFT) 图4.2.2 N点DFT的一次时域抽取分解图(N=8) N/ 2点 DFT W N 0 N/ 2点 DFT W N 1 W N 2 W N 3 x(0) X1 (0) x(2) x(4) x(6) x(1) x(3) x(5) x(7) 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)
第4意快速傅里叶夜换(H 与第一次分解相同,将xl(r)按奇偶分解成两个N/4 长的子序列x3()和x4(l),即 x1(D)=x(21+、l=01.M x()=x2(2) 4 那么,X1(k)又可表示为 N/4-1 X(k)=∑x(2)W32+∑x1(21+1)2 N/4-1 N/4-1 ∑x(1)WM4+W2∑x1()WM i=0 x3(k)+WMa2X4(k),k=0,1,…N/2 (4.2.9)
第4章 快速傅里叶变换(FFT) 与第一次分解相同，将x1(r)按奇偶分解成两个N/4 长的子序列x3 (l)和x4 (l)，即 3 2 4 1 ( ) (2 ) , 0,1, , 1 ( ) (2 1) 4 x l x l N l x l x l = = − = + 那么，X1 (k)又可表示为 / 4 1 / 4 1 2 (2 1) 1 1 / 2 1 / 2 0 0 / 4 1 / 4 1 3 / 4 / 2 4 / 4 0 0 3 / 2 4 ( ) (2 ) (2 1) ( ) ( ) ( ) ( ), 0,1, / 2 1 N N kl k l N N i i N N kl k kl N N N i i k N X k x l W x l W x l W W x l W x k W X k k N − − + = = − − = = = + + = + = + = − (4.2.9)