Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 ยท DFT and FFT

The FFT Algorithm

See why the fast Fourier transform is so fast: the divide-and-conquer idea behind radix-2 Cooley-Tukey, a from-scratch Python FFT, operation counts and practical FFT tips.

The direct DFT needs about N^2 multiplications. For a one-second CD recording that is 44100^2, about two billion operations for a single spectrum. The fast Fourier transform (FFT) computes exactly the same numbers with about N * log2(N) operations: roughly 700,000 for the same recording, thousands of times less. The FFT is not an approximation. It is a clever reorganization, and it is the reason spectrum analyzers, MP3 coders, Wi-Fi and radar are practical.

The divide-and-conquer idea

Split the sum for X[k] into the even-numbered samples and the odd-numbered samples:

X[k] = E[k] + W^k * O[k], with W = e^(-j 2 pi / N)

where E is the DFT of the N/2 even samples and O the DFT of the N/2 odd samples. Both half-size transforms are periodic in k with period N/2, so they only have to be computed once, and the second half of the output follows with a sign flip:

X[k] = E[k] + W^k O[k] X[k + N/2] = E[k] - W^k O[k] for k = 0 ... N/2 - 1

The factors W^k are called twiddle factors. The pair of equations is a butterfly: two inputs, one multiplication, two outputs.

flowchart TB
    A["DFT of N samples"] --> B["DFT of N/2 even samples"]
    A --> C["DFT of N/2 odd samples"]
    B --> D["combine with N/2 butterflies"]
    C --> D
    D --> E["N outputs"]
    B -.->|"same trick again"| F["N/4 + N/4"]

Each level halves the problem. A power-of-two length can be split log2(N) times, and every level costs about N operations.

A recursive implementation

The code is short: if the length is 1, return it; otherwise transform the even and odd halves and combine them with butterflies.

Python Radix-2 FFT in 12 lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recursion confirms that the fast version returns exactly the same numbers as the library.

Counting the work

Each of the log2(N) levels needs about N/2 butterflies, each with one complex multiplication. The total is about (N/2) * log2(N) complex multiplications. Compare:

Python N squared versus N log N

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a million samples the FFT does about ten million multiplications where the direct DFT needs a million million.

An iterative view: bit reversal

Production FFTs avoid recursion. They first reorder the input so that the sample at index n goes to the position whose binary digits are n reversed (bit-reversal permutation), then run the butterfly levels in place with loops. This needs no extra memory and suits hardware and DSP chips.

Python Bit reversal and an in-place FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The inverse FFT

The inverse transform uses the same algorithm: conjugate the input, run the forward FFT, conjugate the result and divide by N. Equivalently, ifft(X) = conj(fft(conj(X))) / N. In NumPy it is np.fft.ifft.

Python Inverse FFT from the forward FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Practical points

  • Any length works. Radix-2 needs N = 2^m, but libraries also use radix-3, radix-5 and the Bluestein method, so even a prime N costs O(N log N). Lengths that factor into small primes are the fastest. scipy.fft.next_fast_len(n) returns the next efficient size (zero-pad to it).
  • Real input: rfft roughly halves the work and memory because the other half of the spectrum is redundant.
  • Precision: the FFT is more accurate than the direct sum, because there are fewer rounding steps.
  • Libraries differ in normalization. NumPy puts the 1/N in the inverse. Other tools (and norm="ortho") use 1/sqrt(N) both ways. Check before comparing numbers.
  • Not just for audio. Image filtering (2D FFT), fast polynomial and big-number multiplication, solving PDEs, and the fast convolution of later lessons all use it.
Python Any length, normalization options

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Roughly how many complex multiplications does a radix-2 FFT of N = 1024 need?

    (N/2) log2 N = 512 * 10 = 5,120, versus about a million for the direct DFT.
  2. 2. What is the central trick of the Cooley-Tukey FFT?

    Even and odd half-transforms are computed once and combined with butterflies for both halves of the output.
  3. 3. How can the inverse FFT be computed with a forward FFT routine?

    ifft(X) = conj(fft(conj(X))) / N.
  4. 4. Why prefer rfft for real signals?

    A real signal has X[N-k] = conj(X[k]), so half the spectrum carries no new information.

Summary

  • The FFT computes the DFT exactly, in O(N log N) instead of O(N^2).
  • Radix-2: split into even and odd samples, transform each half, combine with twiddle-factor butterflies.
  • Iterative FFTs reorder input by bit reversal and work in place.
  • The inverse FFT reuses the forward algorithm with conjugation and a 1/N scale.
  • Use rfft for real data, pad to scipy.fft.next_fast_len, and check the normalization convention.

Next: DFT Properties, Leakage and Zero Padding