The Fourier Transform, Explained in One Sentence

Most equations are written for people who already understand them. This one was rewritten for everybody else. In 2011 Stuart Riffle, a programmer writing for other game developers, took the formula for the discrete Fourier transform, painted each piece of it a different color, and put a single sentence underneath in the same colors. Read the sentence, match the colors, and the formula stops being a wall of symbols. It becomes an instruction.

The card has been passed around ever since, usually without the blog post it came from. That is a shame, because the sentence is only the first step. Every phrase in it hides a small idea, and each of those ideas is easy on its own. So that is how we will read it: one color at a time, then all six together, then with a machine you can turn by hand.

Play a chord on a piano and a microphone records one wiggly line: air pressure going up and down over time. The three notes you pressed are not visible in that line. They have been added together into a single wave. Your ear has no trouble pulling them apart again. The Fourier transform is how a computer does the same thing.

Feed it a list of numbers measured over time and it hands back a list of ingredients: how much of each frequency went into the mix. A prism does this to white light, splitting it into colors. The transform does it to anything that varies, whether a sound, a heartbeat, the brightness along a row of pixels or the tide tables of a harbor.

The idea is older than electricity. Joseph Fourier, working on how heat spreads through a metal bar, claimed in 1807 that any temperature profile, however jagged, could be built by stacking up smooth sine waves. The claim was so bold that the committee reading it, which included Lagrange and Laplace, held back their approval for years. Fourier published the full theory in 1822, in his book on the analytic theory of heat. Two centuries later his sums run inside almost every device that records, compresses or transmits anything.

The formula on the card is the discrete version, the one computers use. It does not take a smooth curve. It takes N samples, the individual readings a sensor actually wrote down, and returns one number for each frequency you ask about. Here it is again, without the colors:

Twelve symbols, and almost nobody can read them cold. Now let's take them one color at a time.

X is the answer, the number you are trying to compute. There is one X for every frequency, which is why it carries a little k. If your signal holds a lot of a certain frequency, X at that frequency will be large. If it holds none, X will be close to zero.

Riffle calls it “energy”, which is a friendly word rather than a precise one. Strictly, X is a complex number, a point on a flat plane rather than on a line. Its distance from the center tells you the amplitude of that frequency, how loud it is. Its angle tells you the phase, where in its cycle the wave started. Square the distance and you get the power, which is the thing physicists would call energy. For a first reading, “how much of this frequency is there” is exactly right.

k is the frequency you are asking about. On the card it is measured in a slightly unusual unit: full cycles per window. If you recorded one second of sound, k = 440 asks about a wave that completes 440 cycles in that second, the A above middle C. If you recorded a row of 1,000 pixels, k = 10 asks about a pattern that repeats ten times across the row.

Notice that k appears twice: once on the left, naming the answer, and once up in the exponent, where it does the work. The sentence repeats it too, “at a particular frequency” and later “at that frequency”. You choose a frequency, and then you use it to set the speed of the spin.

This is the step that makes people give up, and it turns out to be the friendliest one. In school, e raised to a power means growth: money compounding, bacteria doubling. But raise e to an imaginary power and nothing grows at all. You get a point that moves around a circle of radius one. That is Euler's formula:

The cosine is the point's horizontal position and the sine is its vertical position. As the angle θ increases, the point travels counterclockwise around the circle. If that picture is fuzzy, our tour of the unit circle builds it from scratch. For this article, one rule is enough: e^i·angle means “face this direction”. Multiply any number by it and you rotate that number without changing its size.

x_n is the data: the n-th sample of whatever you measured. Sample 0, sample 1, sample 2, all the way to sample N − 1. A CD stores 44,100 of these per second per channel. A phone camera stores millions in each frame. They are ordinary numbers, positive and negative, and they are the only part of the formula that comes from the outside world. Everything else on the card is machinery for looking at them.

i2π turns the exponent into an angle. The i is what switches e from growing to turning, as above. The 2π is one full lap, measured in radians: 360 degrees. Put those two together with the green k and the angle for sample n becomes

Read it as a fraction of the way through the recording, n/N, times the number of laps you want, k, times one lap, 2π. At the first sample the angle is zero. At the last one you have gone almost exactly k times around.

The big Σ means “add up”: do the thing to the right for every n from 0 to N − 1, then sum the results. The 1/N in front divides by how many things you added. Add, then divide by the count: that is an average.

And what are we averaging? For each sample we take its value x_n and point it in the direction e^angle. That gives us a point on the plane: as far from the center as the signal is strong, in the direction the circle has turned to. Do that for every sample and you get a curve, the signal wrapped around the origin like thread on a spool. The average of all those points is their center of mass. That single point is X.

The whole formula is one instruction: wrap the signal around a circle, then find where its weight sits.

Here is the part the sentence leaves you to discover. Suppose your signal is a pure tone that rises and falls three times in the window. Now wind it around a circle at some other speed, say once per window. The high points of the signal land in every direction, spread evenly around. They balance each other out, and the center of mass sits at the middle. The average is zero.

Now wind at exactly three turns per window. Each time the signal peaks, the circle is facing the same way. Each time it dips, the circle is facing the opposite way, and since a dip is a negative number, it gets flipped to the same side as the peaks. All the weight piles up on one side of the circle. The center of mass jumps away from the origin. You have found the frequency.

That is all the transform is: a resonance test. Every frequency that is not in the signal washes out to nothing, and every frequency that is in it leaves a lopsided pile. Try it below. Drag the green slider slowly and watch the teal dot. It sits near the center almost everywhere, then swings out the moment the winding speed matches a note in the signal.

A few things worth noticing while you play. With “One note”, the dot only leaves the center around k = 3, and it reaches 0.5, half the height of the wave. The other half of the wave's energy is hiding at a negative frequency, a mirror image the card does not show. With “Two notes”, the spectrum grows two peaks, and the smaller note makes the smaller peak. And with “Note + steady hum”, the dot is far from the center at k = 0. Winding at zero speed does not wind at all, so the average is simply the average of the signal, its steady offset.

The rosette shapes the red curve draws are close cousins of Lissajous curves: two rhythms traced against each other. When the rhythms lock, the curve becomes lopsided. When they do not, it spreads into an even flower and balances out.

Riffle's card is honest, but it is a card, and a few details were sanded off to make it fit. None of them change the picture. They are worth knowing before you meet the formula in a textbook and think you have the wrong one.

The sign. Most textbooks write the exponent with a minus sign, e^−i2πkn/N, and keep the plus sign for the inverse transform, which rebuilds the signal from its frequencies. The card spins counterclockwise; the textbook spins clockwise. For a real signal, the size of each X comes out the same either way. Only the angle is mirrored.

The 1/N. Where the division by N goes is a matter of convention. Some fields put it on the forward transform, as the card does, so that X really is an average. Most software libraries put it on the inverse instead, and physicists often split it as 1/√N on both sides. The shape of the spectrum is identical; only the scale changes.

How high you can go. With N samples you can only tell apart frequencies up to N/2 turns per window. Above that, the circle turns so fast between two samples that it looks like it is turning slowly backwards, the same effect that makes wagon wheels spin the wrong way in old films. This limit is the Nyquist frequency, and it is why CDs sample at 44,100 per second: just over twice the highest pitch most people can hear.

Taken literally, the card is slow. For each of N frequencies you visit all N samples, so a million samples would take a trillion steps. In 1965 James Cooley and John Tukey published a way to reuse the work, splitting the sum into halves, then quarters, then eighths, until the cost fell to about N log N. It later turned out that Gauss had found the same shortcut around 1805, in notes on asteroid orbits that were only printed after his death. The method is now called the fast Fourier transform, or FFT, and it gives exactly the same answer as the card. It just gets there sooner.

With that speed it went everywhere. MP3 and AAC audio throw away the frequencies your ear will not miss, using a close relative of the transform. JPEG does the same with the fine patterns in 8 × 8 blocks of a photo. An MRI scanner never takes a picture at all: it measures frequencies, and a Fourier transform turns them into an image of your knee. Wi-Fi and 4G pack data onto hundreds of separate frequencies at once and pull them apart again with an FFT. Song-recognition apps fingerprint a few seconds of audio by its spectrum.

Run the transform over and over on short slices of a recording and line the results up, and you get a spectrogram: time running left to right, frequency running up. That is how the researchers behind Pattern Radio turned years of underwater recordings into a picture of humpback whale song you can scroll through. It is also the hidden subject of Nigel Stanford's Cymatics, where each frequency gets its own shape in sand, water and fire.

It is no surprise that Ian Stewart gave the Fourier transform a chapter of its own in 17 Equations That Changed the World, or that Steven Strogatz returns to waves and their ingredients in Infinite Powers. Few formulas have so many jobs.

The reason Riffle's card spreads every time it is posted is not that it simplifies the math. It does not leave anything out that matters. It simply refuses to let a symbol appear without saying what it is for. Navy is the answer, green is the question, blue is the data, and red, orange and teal are the three moves that connect them: spin, go around, average.

Once you have read it that way, the plain black formula reads differently too. You see the circle in the exponent and the average out in front, and the strange symbols turn back into the sentence. To find the energy at a particular frequency, spin your signal around a circle at that frequency, and average a bunch of points along that path.