TABLE OF CONTENTS In Chap. 6 we saw that the discrete Fourier Transform (DFT) could be used to perform convolutions. In this chapter we look at the computational requirements of the DFT and derive some fast algorithms for computing the DFT. These algorithms are known, generically, as fast Fourier transforms (FFTs). We begin with the radix-2 decimation-in-time FFT, an algorithm published in 1965 by Cooley and Tukey. We then look at mixed-radix FFT algorithms and the prime factor FFT.
The N-point DFT of an N-point sequence x( n) is
Because x( n) may be either real or complex, evaluating X( k) requires on the order of N complex multiplications and N complex additions for each value of k. Therefore, because there are N values of X( k), computing an N-point DFT requires N 2 complex multiplications and additions.
The basic strategy that is used in the FFT algorithm is one of "divide and conquer," which involves decomposing an N-point DFT into successively smaller DFTs. To see how this works, suppose that the length of x( n) is even (i.e., N is divisible by 2). If x( n) is decimated into two sequences of length N/2, computing the N/2-point DFT of each of these sequences requires approximately ( N/2) 2 multiplications and the same number of additions. Thus, the...
