Department of Computer ScienceUniversity of Illinois at Urbana-Champaign
201 North Goodwin Avenue, Urbana, IL 61801
This module illustrates a recursive fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform of a complex vector. Although an iterative implementation of the FFT algorithm is usually more efficient than a recursive implementation, the latter more clearly illustrates the divide-and-conquer nature of the algorithm.
The user chooses the size of the input vector from the menu of small powers of 2. For each size, a default input vector is provided, but the user can type in different initial values by clicking Edit Input Vector. Input values may be scaled to guarantee that intermediate steps and results of the algorithm will fit in the display boxes. Clicking OK in the input editor returns to the main display. With the initial vector selected, the user then steps through the recursive FFT algorithm by repeatedly clicking either Next or the currently highlighted step. Each step of the algorithm is graphically depicted in the main display, with corresponding values of the indices and twiddle factors displayed at the lower right. Red lines indicate copying of entries from one vector to another. Blue lines indicate a multiplication/addition step, where the second of two numbers is multiplied by the appropriate twiddle factor and the numbers are added together. At any point during or after the execution of the algorithm, the user may click Reset to start over from the first step of the FFT.
The arguments passed to the FFT procedure are x, y, n, and ω, where x is the initial sequence as shown in the main display, y stores the output vector containing the DFT of x, n is the size of x, and the initial ω is ωn as defined in the twiddle factors module. For clarity, separate arrays are used here for the subvectors, whereas in a practical implementation the FFT is computed in place without using additional storage.
Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 12.2, especially Algorithm 12.1.
Developers: Evan VanderZee and Michael Heath