Page 108 - DSP Integrated Circuits
P. 108

3.16 FFT—The Fast Fourier Transform Algorithm                         93





                 Substituting this into the preceding expression, we get






             or








                 Figure 3.25 shows the signal-flow graph for the Cooley-Tukey FFT. The last
             stage in Figure 3.25, called unscrambling, is needed to sort the outfput values. We
             get






























                      Figure 3.25 Signal-flow graph for the Cooley-Tukey FFT for N = 4





             3.16.2 ST-FFT (The Sande-Tukey FFT)

             The ST-FFT The Sande-Tukey FFT) can be derived in a similar way to the
             Cooley-Tukey FFT by instead performing the summations over the frequency
             index, k, i.e., using the divide-and-conquer approach in the frequency domain.
             Hence, the Sande-Tukey FFT is referred to as a decimation-in-frequency FFT. A
             Pascal program for the Sande-Tukey FFT is shown in Box 3.6.
   103   104   105   106   107   108   109   110   111   112   113