DIT-FFT Digital Signal Processing--DFT/FFT Algorithms Depended on odd-even,x1(r)is divided into two N/4-point sub-sequence x3(I)and x4(I) w1-n文1 X (k) N/4-1 W/4-1 X()=∑x(2W+∑x(21+1)W2+ i=0 i=0 N/4- N/4-1 ∑s☑)W4+W2∑x()W4 i i=0 =X3(k)+W2X4(k),k=0,1,…N/2-1 上游充通大￥
Digital Signal Processing—— DFT/FFT Algorithms DIT-FFT Depended on odd-even, x1(r) is divided into two N/4-point sub-sequence x3(l) and x4(l) 3 1 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
DIT-FFT Digital Signal Processing--DFT/FFT Algorithms W/4-1 X3(k)=>x;(1WN=DFT[x;(I)] i=0 W/4-1 Xa(k)=>xa(WN4 DFT[xa(I] i=0 Because of periodicity of X3(k)and Xa(k)and symmetry of Wm(Wk+N/4 N2--Wk N),that is: X(k)=X3(k)+WN/2Xa(k) X(k+N/4)=X,(k)-W2X4(k) k=0,1,N14-1 上浒充通大￥
Digital Signal Processing—— DFT/FFT Algorithms DIT-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 Because of periodicity of X3 (k) and X4 (k) and symmetry of Wm N/2 ( Wk+N/4 N/2 =-Wk N/2 ) ,that is： 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
DIT-FFT Digital Signal Processing--DFT/FFT Algorithms In the same way X2(k)=X3(k)+WN/2X6(k) ,k=0,1,…N/4-1 X2(k+N/4)=Xk-WN2X (k) N/4-1 Xs(k)=>xs(tW DFTIxs(I)] i=0 N/4-1 X(k)=>x(1)WNa=DFT[x(I)] i=0 x,()=x2(21) 1=0.l,w14-1 x(I)=x2(21+1)' 上游充通大
Digital Signal Processing—— DFT/FFT Algorithms DIT-FFT In the same way 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 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
DIT-FFT Digital Signal Processing--DFT/FFT Algorithms X3(0) X1(0) x(0)● N/4 ·X(0) x(4)● DFT X31) X1(1) ·X1) X4(0) X(2) x(2)· N/4 ·X2) DFT X4(1) X(3) x(6)● W'NR ·X3) X2(0) x(1)◆ N/4 ·X4) DFT X(1) x(5)◆ ·X5) X2(2) x(3)◆ N/4 Wx ·X6) DFT X2(3) x(7)● 究 ·X7) Fig N Points DFT(N=8) 上游充通大￥
Digital Signal Processing—— DFT/FFT Algorithms DIT-FFT Fig N Points 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
DIT-FFT Digital Signal Processing--DFT/FFT Algorithms A(0) A(0) 4(0) 4(0) x(0) X0) A(1) A(1) A(1I) x(4) w& X1) A(2) A(2) A2) x(2) X2) A(3) A(3) A3) x(6) A(4) W& X3) A(4) A4) x(1) W X4) A(5) A(5) A(5) x(5) W& W X5) A(6) A(6) A(6) x(3) W% X6) A(7) A(7) A(7) x(7) w& p昵 W A(7) X7) Fig N Points DIT-FFT Flow graph (N=8) 上游充通大￥
Digital Signal Processing—— DFT/FFT Algorithms DIT-FFT Fig N Points DIT―FFT Flow graph (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)