The FFT: how the butterflies save multiplies

One product, used twice: the trick behind the FFT. Watch the dashed arrow give one output added and a second one flipped.

One product, two outputs

x = 1, 2, 0, −1, 0, 1, 2, 1. Even and odd samples, then two 4-point DFTs.

Eight samples. A direct DFT would take 8 × 8 = 64 multiplies.

not started

multiplies

Describe this picture

Two panels for $x=1,2,0,-1,0,1,2,1$ : its even and odd samples, then two 4-point DFTs. The samples panel shows $x[n]$ from −2 to 3 against the sample $n$ from 0 to 7. Even samples, $x[0]$ , $x[2]$ , $x[4]$ , $x[6]$ , are stems ending in dots, and odd samples, $x[1]$ , $x[3]$ , $x[5]$ , $x[7]$ , are stems ending in squares. The plane panel shows the real part from −4 to 7 against the imaginary part from −4 to 4, on the same scale. A solid arrow from the origin is $X_\text{ev}[k]$ . A dashed accent arrow from its tip is $W_8^kX_\text{od}[k]$ , and its end is marked with a ring labelled $X[k]$ . The dashed arrow flipped, drawn dotted, ends at a square labelled $X[k+4]$ . Finished outputs stay as faint rings and squares labelled $X[0]$ to $X[7]$ . The readouts are $k$ , which shows “not started” until the arrows begin, and the multiplies.

The clip has no control and lasts 16.5 seconds. It opens on eight samples, which then part into two rows of four; the multiplies readout shows 32 from the moment the split is complete. Then for $k=0$ , 1, 2 and 3 the two arrows draw, and the readout counts 33, 34, 35, 36, one for each product that has landed. The caption for each $k$ appears when the square lands and stays for only 0.7 seconds, and is blank while the arrows draw. The last caption reads “Four products gave eight outputs: 32 + 4 = 36 multiplies instead of 64. Split each half again and the saving repeats.” At the end the arrows for $k=3$ are still drawn. Reduced-motion steps stop at 0, 4, 6.8, 9.5, 11.8 and 16.5 seconds.

The cost of the DFT

The DFT (13.2) defines each of $N$ bins as a correlation with a probe, and each bin takes $N$ products:

X[k]=\sum_{n=0}^{N-1}x[n]\,W_N^{kn},\qquad W_N=e^{-j2\pi/N}.

The count is $N$ bins times $N$ products, which is $N^2$ multiplies. For 8 samples that is $8\times 8=64$ . For 1024 samples it is $1024^2=1\,048\,576$ , over a million, for one spectrum.

The fast Fourier transform (FFT) is not a different transform. It gives the same $X[k]$ as the DFT, by a way of ordering the work so that most products are never computed. This page shows the one trick behind it, and then counts what it saves.

One product, two outputs

Split the sum into even samples $n=2m$ and odd samples $n=2m+1$ , with $m=0,\dots,N/2-1$ . Since $W_N^{2km}=W_{N/2}^{km}$ , the two sums are themselves DFTs of length $N/2$ . Two steps of an $N$ -step circle are one step of an $N/2$ -step circle, as in Complex numbers for signals (3.3, section 7). I write them $X_\text{ev}[k]$ and $X_\text{od}[k]$ :

X[k]=\underbrace{\sum_{m=0}^{N/2-1}x[2m]\,W_{N/2}^{km}}_{X_\text{ev}[k]}+W_N^{k}\underbrace{\sum_{m=0}^{N/2-1}x[2m+1]\,W_{N/2}^{km}}_{X_\text{od}[k]}.

The factor $W_N^k$ that multiplies $X_\text{od}[k]$ is a power of $W_N$ . It is called a twiddle factor. Both half-size DFTs repeat every $N/2$ in $k$ , and $W_N^{k+N/2}=-W_N^k$ , because half a turn of the circle is $-1$ . So the same two numbers also give the second half of the outputs:

\begin{aligned} X[k]&=X_\text{ev}[k]+W_N^{k}X_\text{od}[k],\\ X[k+N/2]&=X_\text{ev}[k]-W_N^{k}X_\text{od}[k], \end{aligned} \qquad k=0,\dots,\tfrac N2-1.

The product $W_N^kX_\text{od}[k]$ is computed once, added once and subtracted once. Think of weighing two parcels together and apart: two weighings give both answers.

The picture at the top of the page uses the signal of this lesson, $x=1,2,0,-1,0,1,2,1$ for $n=0,\dots,7$ . The solid arrow is $X_\text{ev}[k]$ , and the dashed arrow, $W_8^kX_\text{od}[k]$ , is added to it nose to tail, as in 3.3 (section 3). The dashed arrow flipped gives $X[k+4]$ . Split into even and odd samples, $x$ needs two 4-point DFTs of 16 multiplies each, 32 in all.

For $k=0$ , $X_\text{ev}[0]+X_\text{od}[0]=3+3=6$ is $X[0]$ , and the same product subtracted gives $X[4]=0$ . For $k=1$ there is one product, $W_8^1X_\text{od}[1]=2.12+0.71j$ . Added, it gives $X[1]=3.12+2.71j$ ; subtracted, $X[5]=-1.12+1.29j$ . For $k=2$ the product is $-3j$ , so $X[2]=-1-3j$ and $X[6]=-1+3j$ . Four products gave eight outputs: $32+4=36$ multiplies instead of 64.

Notice that the dashed arrow flips: the ring and the square sit at opposite ends of it, mirrored about the tip of the solid arrow.

The count of 36 includes the 32 multiplies of the two 4-point DFTs, and the four products by a twiddle factor. It counts every multiply the same, including the one by $W_8^0=1$ and the one by $-j$ . More FFT algorithms (14.2) shows how real codes skip those.

A small check by hand

Take the 4-point case $x=1,2,3,4$ . The even samples are 1 and 3, and the odd samples are 2 and 4. Their 2-point DFTs are $X_\text{ev}=4,-2$ and $X_\text{od}=6,-2$ . The twiddle factors are $W_4^0=1$ and $W_4^1=-j$ . Then

\begin{aligned} X[0]&=4+6=10, & X[1]&=-2+(-j)(-2)=-2+2j,\\ X[2]&=4-6=-2, & X[3]&=-2-(-j)(-2)=-2-2j. \end{aligned}

This agrees with a direct 4-point DFT of 1, 2, 3, 4.

Three stages of butterflies

The saving does not stop at one split. The two half-size DFTs have the same shape as the original, so I split each of them again, into two 2-point DFTs, and each of those into single samples. A DFT of one sample is the sample. For $N=8$ there are three splits in all.

One split step, “two in, a sum and a difference out, one multiply on the lower wire”, is called a butterfly, because its wires cross like wings. It computes $(a,b)\mapsto(a+Wb,\ a-Wb)$ . A column of $N/2$ butterflies is a stage. The number of stages is $\log_2N$ , which is how many times $N$ halves before it reaches 1. For $N=8$ that is 3.

Splitting by even and odd three times reorders the inputs. The sample that goes in row $r$ is $x$ at the index you get by reading the three bits of $r$ backwards. That is called bit-reversed order. Row 1 is 001, which read backwards is 100, which is 4, so row 1 holds $x[4]$ . The rows hold $x[0],x[4],x[2],x[6],x[1],x[5],x[3],x[7]$ , and the outputs come out in order.

Before you start the instrument, think of a knockout tournament: 8 players, 3 rounds. Each round halves the field, and every player is connected to the final through exactly three matches.

Three stages of butterflies

The 8-point FFT of x = 1, 2, 0, −1, 0, 1, 2, 1.

The inputs go in bit-reversed order: x[4] (binary 100) sits in row 1 (001).

stage

inputs

multiplies

Describe this picture

One graph of the 8-point FFT of $x=1,2,0,-1,0,1,2,1$ : four columns of eight nodes, the inputs in bit-reversed order, then stages 1, 2 and 3. The inputs are labelled $x[0]$ , $x[4]$ , $x[2]$ , $x[6]$ , $x[1]$ , $x[5]$ , $x[3]$ , $x[7]$ from the first row to the last, and the outputs $X[0]$ to $X[7]$ . Each node has its value beside it, to one decimal, such as “3.1+2.7j”. Each butterfly has two straight wires and two crossing wires. A twiddle factor is written on a lower input wire where it is not 1: $-j$ in stage 2, and $W_8^1$ , $W_8^2$ , $W_8^3$ in stage 3. The butterflies being drawn are thick and the finished ones thin. The readouts are the stage, from “inputs” to “3 of 3”, and the multiplies.

The clip lasts 15.5 seconds, with a caption after each stage and none while a stage is drawn. First the eight samples fly from natural order into their bit-reversed rows, with the multiplies at 0. Then the stages fill in one at a time, and the readouts go to “1 of 3” and 4, “2 of 3” and 8, and “3 of 3” and 12. Reduced-motion steps stop at 0, 2.5, 4.5, 7.5, 10.5 and 15.5 seconds. Once the clip has finished, tapping an output node, or the Up and Down arrow keys, chooses $k$ through a control named “Output to trace”, whose value reads like “X[3]”. The wires that feed that output turn thick in the accent colour, the rest fade, and the caption reads, for example, “X[3] uses all eight inputs, through one butterfly in each of the three stages.”

The inputs go in bit-reversed order: $x[4]$ (binary 100) sits in row 1 (001). Stage 1 is four 2-point DFTs, and each butterfly makes a sum and a difference. After stage 2, rows 0 to 3 hold $X_\text{ev}[k]=3,\ 1+2j,\ -1,\ 1-2j$ , and rows 4 to 7 hold $X_\text{od}[k]=3,\ 1+2j,\ 3,\ 1-2j$ .

Stage 3 is the step from the previous instrument: its rows 0 to 3 are $X_\text{ev}$ , its rows 4 to 7 are $X_\text{od}$ , and its twiddle factors are $W_8^0,\dots,W_8^3$ . Three stages of four butterflies make 12 multiplies, against 64 for the direct sum, and the outputs come out in order, $X[0]$ to $X[7]$ .

When the clip ends, tap an output node, or use the arrow keys, to trace which wires feed it. Notice that every output is reached from every input, through exactly three butterflies: 2 wires feed it in stage 3, 4 in stage 2, and 8 in stage 1.

How the saving grows

Each stage has $N/2$ butterflies and each butterfly has one multiply. With $\log_2N$ stages, the whole FFT costs

\frac N2\log_2N

multiplies, against $N^2$ for the direct sum. Doubling $N$ quadruples the direct cost. It only a little more than doubles the FFT’s cost, so the gap keeps widening. For $N=1024$ there are 10 stages with 512 butterflies each, which is 5120 multiplies against $1\,048\,576$ . The ratio is $N^2\big/\big(\tfrac N2\log_2N\big)=2N/\log_2N$ , which is $204.8$ times fewer.

The idea is old. Gauss used it in 1805 and did not publish it. Cooley and Tukey’s 1965 paper made spectra of long records practical overnight.

The last picture doubles $N$ from 8 to 65 536 and counts both ways. Watch the gap between the two curves.

How the saving grows

Complex multiplies for one N-point DFT, direct and by FFT.

N = 8: 64 direct multiplies, 12 by FFT, 5.3 times fewer.

times fewer

5.3×

direct

FFT

Describe this picture

One log–log plot of complex multiplies for one $N$ -point DFT, direct and by FFT: the DFT length $N$ from 8 to 65 536, against the multiplies from 10 to $10^{10}$ , with a tick at each power of 10. Two traces are built up point by point: the direct count $N^2$ as joined squares on a dashed line, and the FFT count $(N/2)\log_2N$ as joined dots on a solid line. A ring marks the current $N$ on each. The readouts are $N$ , how many times fewer, and the two counts.

The clip lasts 12.5 seconds. It starts at $N=8$ , reading 5.3×, 64 and 12, and doubles $N$ every 0.8 seconds, up to 65 536 at 10.4 seconds. Between holds the caption follows the form “N = 256: 64.0 times fewer multiplies.” At $N=1024$ the readouts are 204.8×, “1.05 million” and 5 120, and at the end 8192.0×, “4.29 billion” and 524 288. Reduced-motion steps stop at $N=8$ , 64, 1024 and 65 536. Once the clip has finished, dragging along the plot, the Left and Right arrow keys (one doubling), or Home and End choose $N$ , through a control named “DFT length N”.

At $N=8$ the FFT takes 12 multiplies against 64, 5.3 times fewer. At $N=1024$ it is about a million directly against 5120, 204.8 times fewer. At $N=65\,536$ it is 4.29 billion against 524 288, 8192 times fewer: each doubling of $N$ roughly doubles the saving.

When the clip ends, drag along the plot, or use the arrow keys, to choose $N$ . Notice that “times fewer” grows from 5.3 at $N=8$ to 8192 at $N=65\,536$ , and that the two traces drift further apart on the log scale at every doubling.

The count includes multiplies by 1 and by $-j$ , which need no real multiplication. Real codes skip them, and 14.2 gives the exact table. The count is also not a timing. On a laptop a 4096-point FFT takes tens of microseconds, and you can time the library in the browser console. Its count is $\tfrac{4096}{2}\cdot12=24\,576$ multiplies, against $16\,777\,216$ directly, which is $682.7$ times fewer.

The maths behind it · sparse matrix factorisation

The DFT matrix of The DFT as a matrix (13.5) is dense, with $N^2$ entries. The FFT writes it as a product of $\log_2N$ sparse matrices, each with two non-zero entries per row, after a permutation (bit reversal). Factoring a matrix into sparse pieces is how many fast algorithms work.

The maths behind it · divide and conquer

A merge sort splits a list in halves until single items remain, and merges back in $\log_2N$ rounds. It has the same $N\log_2N$ shape.

Where you’ll meet this

Every spectrum analyser, audio plug-in and radio receiver computes its DFTs this way. Lengths that are not a power of two come next, in More FFT algorithms (14.2). Filtering by multiplying spectra is in Fast convolution (14.3). Computing only a few bins is in Goertzel and the chirp z-transform (14.4). Padding a record with zeros to reach a power of two is in Zero-padding and resolution (15.3).

Reference card

Quantity	Formula	Notes
Even/odd split	$X[k]=X_\text{ev}[k]+W_N^kX_\text{od}[k]$	$k=0,\dots,N/2-1$
Second half	$X[k+N/2]=X_\text{ev}[k]-W_N^kX_\text{od}[k]$	because $W_N^{N/2}=-1$
Butterfly	$(a,b)\mapsto(a+Wb,\ a-Wb)$	one multiply
Stages	$\log_2N$	$N/2$ butterflies each
Cost	direct $N^2$ ; FFT $\tfrac N2\log_2N$	speed-up $2N/\log_2N$
Input order	bit-reversed	outputs in order

The FFT

First, the picture

The cost of the DFT

One product, two outputs

A small check by hand

Three stages of butterflies

How the saving grows

Where you’ll meet this

Reference card