Chapter 9 Computation of the DiscreteFourier Transform9.1 decimation-in-time FFTAlgorithms9.2 decimation-in-frequency FFT Algorithms9.3 IFFTAlgorithm9.4 FFT Algorithm of real sequence9.5 practical considerations (software realization)
9.1 decimation-in-time FFT Algorithms 9.2 decimation-in-frequency FFT Algorithms 9.3 IFFT Algorithm 9.4 FFT Algorithm of real sequence 9.5 practical considerations（software realization) Chapter 9 Computation of the Discrete Fourier Transform
Direct computation:N-1knx[n]wX[k] =0<≤k<≤N-1Nn=02-knIX[k]W0≤n<N-1x[n]NNk=0Complex multiplication:N(N-1)Complex addition4N2Real multiplication4N2Real addition:
[ ] 0 1 1 [ ] [ ] [ ] 0 1 1 0 1 0 − − = = − − = − = n N N k n X k W N x n k N N k n X k x n W N k N n Direct computation: Complex multiplication: 2 N Complex addition: N(N −1) Real multiplication: Real addition: 2 4N 2 4N
9.1 decimation-in-time FFT AlgorithmsG[0]X[0]x[0]N/2POINTG[1]x[2] →X[1]DFTG[2]X[2]x[4] —G[3]X[3]x[6] Figure9.3WNH[0]X[4]x[1] →N/2POINTH[1]Wx[3] →X[5]H[2]X[6]x[5]DFTWH[3]x[7]X[7]
9.1 decimation-in-time FFT Algorithms -1 -1 -1 -1 WN 0 WN 1 WN 2 WN 3 x[7] x[5] x[3] x[1] x[6] x[4] x[2] x[0] H[2] H[3] H[1] H[0] G[3] G[2] G[1] G[0] X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] N/2 POINT DFT N/2 POINT DFT Figure 9.3
mth(m-1)ststagestageWN1Figure 9.9complex multiplications岁*(N>>1)
Figure 9.9 ,( 1) 2 2 2 2 : 2 2 + N N N N complex multiplications
Gi[0]G[O]x[0]N/4point-X[O]DFTG;[1]G[1x[4]-X[1]WNOG[2]G2[0]N/4pointX[2]x[2]DFTWNG2[1]GI3x[6]-X[3]H,[0]WNH[O]X[4]N/4pointx[1]DFTH,[0]WNH[1]x[5] -X[5]WNoH,[0]H[2]WN/4pointx[3]X[6]DFTWNWNH2[0]H[3]x[7]X[7]Figure 9.5
G1 [0] G[0] WN 2 WN 0 WN 2 WN 0 H1 [0] H1 [0] H2 [0] H2 [0] G1 [1] G2 [1] G2 [0] WN 0 H[0] -1 WN 1 WN 2 WN 3 x[7] x[3] x[5] x[1] x[6] x[2] x[4] x[0] H[2] H[3] H[1] G[3] G[2] G[1] N/4point DFT DFT X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] N/4point DFT DFT N/4point DFT DFT N/4point DFT DFT -1 -1 -1 -1 -1 -1 -1 Figure 9.5