In one convenient description, an N‑dimensional vector describes a point in N‑space as a weighted summation of equally spaced samples. We call that description the time‑domain representation. The Discrete Fourier Transform (DFT) is a transform that describes that same point in N‑space as a weighted summation of cosines and sines. We call that description the frequency‑domain representation. The point is the same in both coordinate systems, but the basis sequence that describes the point is different.

Think of a point in three‑dimensional space described in Cartesian coordinates (x, y, z). The same point can also be described in polar coordinates (R, θ, φ). Both 3‑tuples describe the same point, but in different coordinates. We select the coordinate system to describe that point in either form and can change forms for convenience of a different perspective. The inverse DFT (IDFT) reverses the mapping, converting the frequency‑domain description to the time‑domain description. The DFT is a transform with well defined and useful properties.

The DFT is implemented as a set of length-N inner products of the input vector on a set of N orthogonal basis vectors. Each inner product requires N complex multiplies and adds, which means the set of N inner products requires N² complex multiplies and adds. If N is small, say 10², then 10² complex products is manageable. If N is large, say 10³, then 10⁶ complex products may give us cause for second thoughts.

The Fast Fourier Transform (FFT) is an algorithm that performs the DFT operations with, on the order of, mN complex multiplies and adds. In one form of the algorithm the scale factor m is log₂(N)/2 and in another form m is 2. The most common constraint we learn when we first study the FFT algorithm is that N must be highly composite, the product of many factors. Misconception number 1. The most well‑known version of the FFT is the Cooley–Tukey radix‑2 algorithm. This algorithm is so pervasive that we are often misguided to believe that N must be a power of 2, i.e., 2³. Misconception number 2. FFTs come in all sizes, including prime lengths.

We will review the FFT in three primary forms — the Cooley–Tukey, the Good–Thomas, and the Winograd — with a few essential equations and with many figures and images to show why and how they differ.