2.3.6 Fast Fourier transform FFT Consequently (N/2)1 (N/2)1 X(k)=∑x2Wm2+W∑x2r+1)WM (2238) G(k+Wkhk) k=0.1.N-1 where C(k)=∑x(2)w2k=01.y-1(239) H()=∑(2r+)2k=01,…y2-1(240) After the two dFts corresponding to the two sums in Eq (2.238) are computed, they are then combined to yield the N-point dFt, X(h)
Consequently, where After the two DFTs corresponding to the two sums in Eq. (2.238) are computed, they are then combined to yield the N-point DFT, X(k). 2.3.6 Fast Fourier transform (FFT) ( ) ( ) ( ) ( ) ( ) G(k) W H(k) X k x r W W x r W k N N r r k N k N N r r k N = + = + + − = − = 2 1 0 2 2 1 0 2 2 2 1 k = 0,1,N −1 (2.238) ( ) ( ) − = = 2 1 0 2 2 ( ) N r rk WN G k x r ( ) ( ) − = = + 2 1 0 2 1 2 ( ) N r rk WN H k x r 1 2 k = 0,1,N − (2.239) 1 2 k = 0,1,N − (2.240)
2.3.6 Fast Fourier transform FFT This figure used the signal G(O) flow graph conventions for x(2 ×(1) representing difference x(4 equations. That is. branches x(6 X(3) entering a node are summed au X4) to produce the node variable. x( point When no coefficient is DF T -ox(6) indicated. the branch →bx(7) transmittance is assumed to Fig. 2. 74 Flow graph of the be one For other braches decimation-in-time decomposition of an N-point dft computation into two the transmittance of a branch N/2-point DFT computations(N=8) is an integer power of w
This figure used the signal flow graph conventions for representing difference equations. That is, branches entering a node are summed to produce the node variable. When no coefficient is indicated, the branch transmittance is assumed to be one. For other braches, the transmittance of a branch is an integer power of WN. 2.3.6 Fast Fourier transform (FFT) Fig. 2.74 Flow graph of the decimation-in-time decomposition of an N-point DFT computation into two N/2-point DFT computations(N=8)
2.3.6 Fast Fourier transform FFT Equation(2.238 )corresponds to breaking the original N-point computation into two-N/2-point computations. Breaking further each of the sums in Eq (2.238 ) into two N/4-point DFTs, which would then be combined to yield the n/2-point DFTS N/2)-1 (N/4)1 (N/4)1 G(k)=∑g()W2=∑g(2)+28(1+12 1=0 l=0 (N/4)1 G(k)=∑g(2)W4+W2∑8(21+14(24 S imari (N/4)1 (N/4)-1 H()=∑62)%4+WA∑621+1) (2.242
Equation (2.238) corresponds to breaking the original N-point computation into two-N/2-point computations. Breaking further each of the sums in Eq. (2.238) into two N/4-point DFTs, which would then be combined to yield the N/2-point DFTs. Similarly, 2.3.6 Fast Fourier transform (FFT) ( ) ( ) ( ) ( ) ( ) − = − = = + + 4 1 0 2 4 4 1 0 2 4 2 1 N l l k N k N N l l k G k g l WN W g l W ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) − = + − = − = = = + + 4 1 0 2 1 2 4 1 0 2 2 2 1 0 2 2 2 1 N l l k N N l l k N N r r k G k g r WN g l W g l W (2.241) ( ) ( ) ( ) ( ) ( ) − = − = = + + 4 1 0 2 4 4 1 0 2 4 2 1 N l l k N k N N l l k H k h l WN W h l W (2.242)