第4章快速傅里叶夜换(ED 则x(m)的DFT为 X()=∑x(m)W+∑x(n)W如 N/2-1 2 kr (2r)WN"+ x(2r+1)W2r+1) ∑x(m)+W∑x(r) 2 由于 r=0 r=0 2kr 2 N/2 所以 N/2 N/2-1 r)r2 +W2 x2(r)WNr 2=X,(k)+WX2 (k)
第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章快速傅里叶夜换(FH) 其中X(k)和X2(k)分别为x1(r)和x2r)的N/2点DFT, N/2-1 X,(k)=>,(r)W/2=DFT[,(r) (4.2.5) X2(k)=2 x2(r)WNT2=DFT[x2(r) (4.2.6) 由于X1(k)和X2(k)均以N2为周期,且 WN2=-W,所以X(k)又可表示为 X(k)=X1(k)+WNX2(k)k=0,12 (4.2.7) (,N\=X(k)-WH2(k)k=0,12 (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章快速傅里叶夜换(ED a+BC B A- BC 图42.1蝶形运算符号
第4章 快速傅里叶变换(FFT) 图4.2.1 蝶形运算符号 C A B A＋ BC A－ BC
第4章快速傅里叶夜换(ED X1(0) X(0 N2点x1(1) x(2) X(1) x(4) x1(2) X(2) X1(3) X(3) x2(O) X(4 x(3) N2点X,(1)wy X(5) X2(2) x(5) X(6) T 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章快速傅里叶夜换(ED 与第一次分解相同,将xl(r)按奇偶分解成两个N/4 长的子序列x3()和x4(l),即 x()=x2(2) l=0 x4()=x(2+1) 那么,X1(k)又可表示为 N/4-1 N/4-1 X()=∑x1(21)W+∑ x(2/+1)82) N/4-1 N/4-1 ∑x(D)WM4+W2∑ ,(owk N/4 i=0 x3(k)+W2X4(k,k=0,1…N/2-1 (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)