Fourier analysis · Algorithms

FFT butterfly diagram

An 8-point FFT is three stages of four butterflies, each one twiddle multiplication yielding both X[k] and X[k+N/2], for 12 multiplications instead of the direct DFT’s 64.

Taught in Sines & Spectra.

Reveal the N = 8 signal-flow diagram one stage at a time: even/odd-ordered inputs on the left, size-2, size-4 and size-8 DFTs built stage by stage, and outputs in natural order, with the multiplication count updating.

The claim above is what this widget demonstrates. Disagree with it?

Where next