 length N/2 by splitting the input samples into even and The inverse discrete Fourier transform odd samples, in Equations 2.71 and 2.72, where k = 0, 1, N-1. Given the discrete Fourier transform X(k) of the input sequence (2.71) x(n), the inverse discrete Fourier transform (IDFT) of X(k) is the original time sequence, and is given by Equation 2.70. (2.70) (2.72) The proof is easily obtained by substitution and interchanging the order of summation. The form of the IDFT is the same as the DFT apart from the factor 1/and the sign change in exponent of the basis Consider X and X2 to represent the normalised even and odd functions, and consequently the DFT algorithm can be used to sample components respectively as in Equations 2.73 and 2.74, for compute these transforms in either direction. It should be noted that m=0,1,2,......(N/2-1). the DFT is equal to the Z-transform of a sequence, x(n), evaluated at equally spaced inputs on the unit circle in the z-plane (see later). x,(m) - (l(2m) (2.73) The fast Fourier transform (2.74) Special analysis and many other applications often require DFT's to be performed on data sequences in real time and on contiguous sets of input samples. If the input sequence has N samples, the compu- Therefore Equation 2.72 may be written as in Equation 2.75, tation of the DFT requires N2 complex multiplies and N2-N com- where Equation 2.76 holds and each of the summation terms is plex additions. reduced to an N/2 point DFT. 2/10 Fourier analysis Stage 4 N 2 point (8 odd input x(10) samples) x(12) x(14) point X(10) (8 odd input samples) X(11) X(12) x(11) X(13) x(13) X(14) x(15) X(15) Figure 2.6 First step in developing a 16 point decimation in time FFT signal flow graph N/2-1 (2.75) (2.82) The decomposition process is repeated until two-point DFT's are (2.76) generated. Each decomposition is called a stage, and the total number of stages is given by Equation 2.83. The general form of the algorithm may be written as in Equation 2.77 and 2.78, where Equations 2.79 and 2.80 hold. M(N) = log2N = (