The Fourier transform

The Fourier transform takes a signal and tells you how much of each frequency it contains. It’s behind almost everything else on this site: frequency responses, filter design, MP3’s psychoacoustic model, and spectrograms. Its formula looks forbidding:

By the end of this page every symbol in it should make sense, as should why it works and how the FFT computes it so quickly. We’ll start from scratch with a picture of complex numbers as arrows.

A complex number such as $3 + 2j$ is just a point on a flat plane: 3 along the horizontal (real) axis, 2 up the vertical (imaginary) axis. Think of it as an arrow from the centre to that point. (Engineers write $j$ for $\sqrt{-1}$; mathematicians write $i$, but in electronics $i$ already means current.)

Arrows give complex arithmetic a picture. Pick each one in the figure below:

• Adding two complex numbers adds their “along” parts and their “up” parts. As arrows: put the second arrow’s tail on the first one’s tip.
• Every arrow has a size (its length, written $|z|$) and an angle (measured anticlockwise from the positive real axis, written $\angle z$). The next subsection shows how to work them out.
• Multiplying two complex numbers multiplies their sizes and adds their angles. That’s the key fact. You can check it by multiplying out the brackets the ordinary way, using $j \times j = -1$; the figure shows the working.
• $j$ itself is the arrow of size 1 pointing straight up (90°), so multiplying by $j$ turns any arrow a quarter-turn anticlockwise. Do it twice and you’ve turned 180°, which is why $j \times j = -1$.
• More generally, multiplying by an arrow of size 1 just rotates whatever it multiplies.

Here’s the one piece of school trigonometry everything else on this page rests on. In a right-angled triangle, pick one of the other two angles and call it $\theta$. The longest side is the hypotenuse, the side touching $\theta$ is the adjacent side, and the side across from it is the opposite side. The three trig functions are just ratios of these sides, remembered as SOH CAH TOA:

Now draw an arrow of length 1 at angle $\theta$, and drop a line straight down from its tip to the horizontal axis. That makes a right-angled triangle whose hypotenuse is the arrow (length 1), whose adjacent side is how far across the tip is, and whose opposite side is how far up it is. So:

• CAH: across $= \cos\theta \times \text{hypotenuse} = \cos\theta$
• SOH: up $= \sin\theta \times \text{hypotenuse} = \sin\theta$

The arrow of length 1 at angle $\theta$ ends at the point $(\cos\theta, \sin\theta)$: it’s the complex number $\cos\theta + j\sin\theta$. (An arrow of length $r$ is just $r$ times that.)

Going the other way, from a point $a + bj$ to its size and angle, uses the same triangle. The size is the hypotenuse, by Pythagoras: $\sqrt{a^2 + b^2}$. The angle comes from TOA: $\tan\theta = b/a$. (Calculators and code use a function called atan2(b, a), which also works out which way round the arrow points.)

So the arrow of size 1 at angle $\theta$ is $\cos\theta + j\sin\theta$, and multiplying two of these adds their angles. Exponents behave the same way: $e^a \times e^b = e^{a+b}$. Because angles add when you multiply, the angle behaves like an exponent, and that’s why this arrow is written

That’s Euler’s formula. It isn’t just a convenient label: it really is the number $e$ raised to the power $j\theta$. Here’s why.

The number $e$ comes from compound interest. Suppose a bank pays 100 % interest a year. Paid all at once at the end of the year, 1 pound becomes 2. Paid in two halves of 50 %, the second payment also earns interest on the first: 1 × 1.5 × 1.5 = 2.25 pounds. Paid monthly, it’s $(1 + \tfrac{1}{12})^{12}$. The more often interest is paid, the more you end up with, but the total doesn’t grow without limit:

It homes in on 2.718281…, and that limit is the number $e$. At a different rate $x$ it works the same way, and gives $e^x$:

So what is $e^{j\theta}$? Use the same recipe with $x = j\theta$: grow by $j\theta/N$, $N$ times. Multiplying by $(1 + j\theta/N)$ means “keep what you have, and add a small piece $\theta/N$ times as long, turned 90°” (multiplying by $j$ is a quarter-turn). A small push at right angles is a small rotation. So each step turns the arrow by about $\theta/N$ without changing its length much, and $N$ steps turn it by $\theta$ in total.

Now let the angle grow steadily, by $\omega$ radians every sample: $e^{j\omega n}$ for $n = 0, 1, 2, \dots$ The arrow spins. Its horizontal shadow is $\cos(\omega n)$ and its vertical shadow is $\sin(\omega n)$: a sinusoid is the shadow of a spinning arrow.

This also explains a phrase used on the filter pages: “delaying by one sample multiplies by $e^{-j\omega}$”. A spinning arrow one sample ago pointed $\omega$ radians further back. Turning it back by $\omega$ means multiplying by the arrow at angle $-\omega$, which is $e^{-j\omega}$.

Why break signals into sinusoids, rather than square waves or anything else? Three reasons.

Filters can’t change them. Feed a spinning arrow $e^{j\omega n}$ into any filter that only delays, scales and adds (an FIR or IIR filter, an echo, a room). Each delayed copy is the same arrow, rotated. Each scaled copy is the same arrow, stretched. Adding rotated, stretched copies of one arrow gives one arrow, rotated and stretched. So out comes the same spinning arrow, multiplied by a single complex number:

That number $H(\omega)$ is the frequency response. No other shape survives a filter intact. Put a square wave through a low-pass filter and it comes out rounded. So if a signal is written as a sum of sinusoids, filtering it is simple: multiply each sinusoid by its own $H(\omega)$.

Nature uses them. Strings, air columns and circuits vibrate in sinusoids, and the inner ear separates sound into frequencies before your brain hears it.

Anything can be built from them. Fourier’s bold claim (1807) was that any repeating signal is a sum of sinusoids at whole multiples of its repetition frequency.

That bottom panel is the idea of a spectrum. Building a signal from a recipe is synthesis. The Fourier transform does the reverse, analysis: given the signal, find the recipe.

How do you find how much of one particular frequency is hiding in a signal? Multiply the signal by a test wave at that frequency, sample by sample, and add up the results.

If the signal contains the test frequency, the two rise and fall together. Their products are mostly positive, and the sum grows big. If it doesn’t, the products swing between positive and negative and cancel out. Dividing the sum by $N/2$ turns it into the amplitude of that component. (This multiply-and-add is called a correlation, or a dot product.)

The fix is to test with two waves, a cosine and a sine. Any sinusoid at that frequency, whatever its phase, is a mixture of the two. The two results say how much of each, so together they give the amplitude (the length of the arrow, $\sqrt{\text{cos}^2 + \text{sin}^2}$) and the phase (its angle). Switch the figure to a cosine and a sine: now the amplitude stays at 1 however you shift the signal, and only the arrow’s angle turns.

A pair of numbers that belong together is a complex number, so do both tests at once: multiply by $\cos(\omega n) - j\sin(\omega n)$, which is $e^{-j\omega n}$:

There’s a lovely way to picture this. The component of the signal at frequency $\omega$ is a spinning arrow. Multiplying by $e^{-j\omega n}$ spins it backwards at the same speed, so it stops spinning, and adding up all $N$ samples piles $N$ copies of it end to end. Components at any other frequency are still spinning after the multiplication, so they go round in circles and add up to (nearly) nothing.

That cancellation is exact when the frequencies are whole numbers of cycles across the window. Multiply two different whole-cycle sinusoids and the products always sum to precisely zero. Mathematicians call such signals orthogonal.

The word comes from geometry. Think of 16 samples as a single arrow in 16-dimensional space: one coordinate per sample. The multiply-and-add is the dot product, which measures how much two arrows point the same way, and it’s zero for arrows at right angles. With 16 samples there happen to be exactly 16 whole-cycle sinusoids: cosines with 0 to 8 cycles and sines with 1 to 7. All 16 are at right angles to each other, like 16 perpendicular axes.

Perpendicular axes are what make coordinates easy. Because the axes are perpendicular, the “how far along x” measurement isn’t disturbed by how far along y something is. In the same way, any 16-sample signal is exactly one combination of those 16 sinusoids, and each test measures its own ingredient without interference from the others.

Now do the test for every frequency that fits a whole number of cycles into the $N$ samples: $k$ cycles, for $k = 0, 1, \dots, N-1$. Testing for $k$ cycles means turning by $\omega = 2\pi k/N$ per sample. That’s the discrete Fourier transform (DFT), and the formula at the top of the page:

In words: for each bin $k$, spin the signal backwards at $k$ turns per window, and add it up. Each $X[k]$ is a complex number. Its size says how much of that frequency there is, and its angle the phase.

A few things to notice about the bins:

• Bin $k$ is the frequency $k/N$ cycles per sample, or $k \cdot f_s/N$ Hz. The spacing between bins, the frequency resolution, is $f_s / N$. A longer window gives finer resolution.
• Bins above $N/2$ are negative frequencies. $k$ turns per window forwards looks exactly the same, sample by sample, as $N - k$ turns backwards, since the samples can’t tell a full extra turn. (This is aliasing, explored properly on the sampling page.) For a real signal, each cosine is a pair of opposite spinning arrows (section 1), so it shows up twice: at $k$ and at $N - k$, with half its strength in each. That’s the mirror image in the middle panel.
• Bin 0 is the average (the “DC” part), and bin $N/2$ is the Nyquist frequency.

The DFT turns $N$ samples into $N$ arrows. Can we turn them back into the signal? Yes, and the way back is almost the same calculation:

Compare it with the forward transform. Only two things differ: the sign in the exponent, and the $1/N$ in front.

The sign. The forward transform multiplied by $e^{-j2\pi kn/N}$ to un-spin the component at frequency $k$, so it stood still and piled up. Going back, each arrow $X[k]$ has to be set spinning again, in the original direction. That’s multiplying by $e^{+j2\pi kn/N}$. Then add up all the spinning arrows.

The 1/N. When the forward transform un-spun a component, adding up $N$ samples piled $N$ copies of its arrow end to end. So $X[k]$ is $N$ times bigger than the arrow actually in the signal, and the inverse divides by $N$ to undo that. You’ve seen this already. The DFT explorer’s cosine of amplitude 1 read 32 in its bin. A cosine is two arrows of length ½ (section 1), and with $N = 64$, $64 \times \tfrac{1}{2} = 32$. (Some books split the factor evenly instead, putting $1/\sqrt{N}$ on both transforms. That’s a convention; it changes nothing important.)

Why so symmetric? It’s the perpendicular axes from section 4 again. To find a point’s coordinates in 3-D, you measure how far it goes along each axis: a dot product with each axis. To rebuild the point from its coordinates, you go that far along each axis and add up. Both directions use the same axes; one measures along them, the other builds along them. The only wrinkle is that our “axes”, the test waves, aren’t of length 1. Each one’s dot product with itself is $N$, not 1, and that’s the same factor of $N$ again.

So each bin $k$ contributes an arrow of length $|X[k]|/N$, starting at angle $\angle X[k]$, and spinning $k$ turns every $N$ samples. Bins above $N/2$ count as negative frequencies, spinning the other way. Chain the arrows tip to tail, set them all spinning, and the tip of the last one traces out the signal. Ancient astronomers used chains of circles like this, called epicycles, to model the planets.

For a real signal, the arrows come in mirror-image pairs. Bin $k$ and bin $N-k$ (that is, $-k$) have the same length and opposite angles, and spin in opposite directions. So their vertical parts always cancel, which is exactly the “a cosine is two opposite arrows” picture from section 1. Whatever the arrows do, the tip stays on the horizontal axis, sliding back and forth, and its position over time is the signal.

Now drop the requirement that the signal is real. Let each “sample” be a complex number, a point anywhere on the plane. There’s nothing to stop the DFT working on complex samples. The only difference is that the arrows no longer need to come in mirror pairs. Without the pairs, the tip is free to leave the horizontal axis and roam the whole plane.

So take any closed outline, a heart or a star or your own scribble, and walk round it at a steady pace, noting where you are every step: across $+ j \times$ up. That’s a list of complex numbers, and because the outline is closed it repeats, trip after trip, like a periodic signal. Take its DFT, and the arrows will redraw it. Fourier’s claim from section 2 applies, so any closed shape can be drawn this way. With $N$ sample points, $N$ arrows reproduce all $N$ points exactly.

It helps to think about what each frequency contributes, adding them in order:

• Frequency 0 doesn’t turn at all. It’s the centre of the shape (the average position).
• Frequency +1 goes round exactly once per trip, anticlockwise: a circle, the roughest possible one-loop sketch. Adding −1, which goes round once clockwise, squashes that circle into the best-fitting ellipse.
• ±2, ±3, … go round 2, 3… times per trip. Riding on top of the bigger arrows, they add 2, 3… wiggles per trip: finer and finer detail, just as higher harmonics add sharpness to a sound.
• Sharp corners need a lot of high frequencies, like the square wave’s edges. Leave them out and corners come out rounded, with small ripples nearby. That’s the Gibbs phenomenon once more, in two dimensions.

The DFT only tests whole-cycle frequencies. What happens to a frequency in between? Its sinusoid isn’t orthogonal to any of the test waves (section 4), so every bin responds a little: the energy leaks across the whole spectrum.

There’s a neat way to see why. Taking $N$ samples is the same as multiplying an endless signal by a rectangular window. So the DFT doesn’t see a pure sinusoid. It sees the window’s spectrum, centred on the sinusoid’s frequency, exactly the picture from the windows section of the FIR page. When the frequency is a whole number of cycles, the bins happen to land exactly on that spectrum’s zeros, and everything looks clean. Otherwise they land on its sidelobes.

One more property explains why the Fourier transform is so central. Filtering in time is multiplication in frequency: the spectrum of a filter’s output is the input’s spectrum times the filter’s frequency response. That’s why the FIR page could get a filter’s frequency response from the FFT of its taps. It’s also why long filters are often run by transforming the signal, multiplying, and transforming back. With the FFT, that’s faster than computing the convolution sum directly. (With the DFT there’s a catch: the convolution wraps around the end of the window, so in practice the signals are zero-padded first.)

The DFT as written does $N$ multiply-adds for each of $N$ bins: $N^2$ in total. For $N = 1024$ that’s over a million. The fast Fourier transform (FFT) gets the identical answer with about $\frac{N}{2}\log_2 N$ “butterflies”, about 5000 for $N = 1024$. It isn’t an approximation: it just stops repeating work. Here’s how, built up from the smallest case.

One sample. The DFT of a single sample is that sample: $X[0] = x[0]$.

Two samples. With $N = 2$ the test waves are $e^{-j2\pi kn/2}$, and only two values ever come up: 1 (for $k$ or $n$ equal to 0) and $e^{-j\pi} = -1$ (for $k = n = 1$, Euler’s identity again!). So

A sum and a difference. Drawn as a diagram, the two crossing lines look like a butterfly’s wings, so this is called a butterfly.

Bigger sizes: split into even and odd samples. Split the DFT’s sum into the even-numbered samples and the odd-numbered ones. For the even samples, $n = 2m$, the test wave is $e^{-j2\pi k(2m)/N} = e^{-j2\pi km/(N/2)}$. That’s exactly an $\frac{N}{2}$-point DFT of the even samples; call its result $E[k]$. The odd samples, $n = 2m+1$, are the same thing shifted by one sample, and a one-sample shift multiplies by $e^{-j2\pi k/N}$ (section 1, once more). So with $O[k]$ the $\frac{N}{2}$-point DFT of the odd samples:

$W^k$ is called the twiddle factor. Now the saving. $E$ and $O$ are $\frac{N}{2}$-point transforms, so their values repeat after $\frac{N}{2}$ bins. And jumping $k$ by $\frac{N}{2}$ turns $W^k$ by half a circle, which flips its sign. So the second half of the outputs comes free:

That’s a butterfly again: one multiplication by $W^k$, then a sum and a difference, giving two outputs. Now split $E$ and $O$ the same way, and keep going until everything is 1-point DFTs. Each split level is one stage of $\frac{N}{2}$ butterflies, and there are $\log_2 N$ levels.

The inverse FFT is the same algorithm with the twiddle factors spinning the other way ($e^{+j2\pi/N}$), and a division by $N$ at the end.

The DFT treats its $N$ samples as the whole story. Real signals change over time, so in practice you take the DFT of short, overlapping, windowed chunks. That’s the short-time Fourier transform, and plotting its results gives a spectrogram. MP3’s psychoacoustic model does exactly that with 1024-point FFTs. The same “one bin per frequency” idea, run backwards, is how modern radio (Wi-Fi, 4G, 5G) packs data into hundreds of narrow sub-carriers (OFDM), a topic for the communications pages to come.

• 3Blue1Brown, But what is the Fourier Transform? A visual introduction: the “winding around a circle” picture, beautifully animated.
• Julius O. Smith III, Mathematics of the Discrete Fourier Transform: a free online book that takes the DFT from complex numbers up.
• Steven W. Smith, The Scientist and Engineer’s Guide to Digital Signal Processing: free, practical, and light on maths.
• J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series” (1965): the paper that made the FFT famous (Gauss had found it in 1805).