Page 110 - DSP Integrated Circuits

3.16 FFT—The Fast Fourier Transform Algorithm 95

Figure 3.26 Sande-Tukey's FFT for N = 8.

memory cells that store the input values. The values in a dual node pair are used
to compute the corresponding dual node pair in the next column. At this point, the
first node pair is no longer needed so the results can be stored back into the origi-
nal memory cells. This technique is called in-place computation. The program in
Box 3.6 uses in-place computation. Note also that all of the dual node pairs in each
column can be computed simultaneously. Hence, there is a relatively high degree
of computational parallelism in the FFT.
We will later show that the technique
of using a memory with only N complex
memory cells for computing an JV-point
FFT results in a significant reduction in
chip area. A drawback of the in-place
computation is that the original input
sequence is lost.
The butterfly for the Sande-Tukey
FFT is shown in Figure 3.27. The Sande- Figure 3.27 The Sande-Tukey butterfly
Tukey butterfly can be derived from the
Cooley-Tukey butterfly by using the
transposition theorem.