1988 Reports

Fast Fourier Transforms: A Review

Wolberg, George

The purpose of this paper is to provide a detailed review of the Fast Fourier Transform. Some familiarity with the basic concepts of the Fourier Transform is assumed. The review begins with a definition of the discrete Fourier Transform (DFT) in section 1. Directly evaluating the DFT is demonstrated there to be an 0 (N2) process. The efficient approach for evaluating the OFT is through the use of FFT algorithms. Their existence became generally known in the mid-1960s, stemming from the work of J. W. Cooley and J. W. Tukey. Although they pioneered new FFT algorithms, the original work was actually discovered over 20 years earlier by Danielson and Lanczos. Their formulation, known as the Danielson-Lanczos Lemma, is derived in section 2. Their recursive solution is shown to reduce the computational complexity to 0 (N log2 N). A modification of that method, the Cooley-Tukey algorithm, is given in section 3. Yet another variation, the Cooley-Sande algorithm, is described in section 4. These last two techniques are also known in the literature as the decimation-in-time and decimation-in-frequency algorithms. respectively. Finally, source code, written in C, is provided in the appendix.