The Fourier Transform, one tiny step at a time
No prior math needed. Each step adds one small idea. Press play, drag the sliders, and watch. Part 1 builds the idea. Parts 2–4 cover the formula, the DFT, and the FFT.
Here's where we're going. Any wiggly line, like a sound, can be built by adding up simple spinning circles. The Fourier transform is a way to look at a wiggly line and find out which circles built it. We'll start with one circle.
1A dot on a circle draws a wave
A yellow dot goes around a circle at a steady speed. Look only at its height, meaning how far up or down it is.
On the right, we write down that height as time moves forward. The line we get is a smooth up-and-down curve. It's called a sine wave.
2Three knobs: speed, size, starting point
Every circle has only three settings. Try each slider. The faint grey wave stays put so you can compare.
- Speed is how many turns the dot makes each second. Scientists call it frequency. It's measured in hertz (Hz), and 1 Hz means 1 turn per second. Faster spinning gives a more squashed-together wave.
- Size of the circle is the amplitude, meaning how strong the wave is. A bigger circle gives taller peaks.
- Starting angle is the phase, meaning where the dot starts. Changing it slides the wave left or right.
3Stack circles to draw any shape
Now put a small circle on the rim of a big one, then a smaller one on that, and so on. Each one spins at its own speed. Watch the height of the last dot only.
With one circle we get a plain wave. Add more circles, each faster and smaller, and the result looks more and more like a square wave (a flat-topped on/off shape, shown as the dashed line). Circles stacked like this are sometimes called epicycles.
4The reverse question
Now flip it around. Someone hands you the messy wave at the top. You don't know how it was made.
The question is: which circles, with which speeds and sizes, add up to this? Press the button to see the answer here. In real life nobody gives you the answer, so you need a method to find it.
5The winding trick
Here's the clever part. This wave has one hidden speed. We'll pretend we don't know it's 3 Hz.
What's happening. Picture the wave as a string. We wrap it around a center point, like winding thread on a spool. A high part of the wave sits far from the center. A low part sits close. We pick the winding speed, meaning how many turns we wrap each second. Press "Watch it wrap" to see it happen slowly.
Then we find the center of mass, the shape's balance point, shown as the yellow dot. Usually the wrapped shape is spread evenly all around, so the balance point stays near the middle.
But when the winding speed matches the hidden speed (3 turns per second), every high part lands on the same side. The shape gets lopsided and the balance point jumps out. The right-hand plot records that jump as a spike at 3.
(There's also a bump at 0. This wave never goes below zero, and with no winding at all the whole string piles up on one side. That bump just measures the wave's average height. You can ignore it.)
6That plot is the spectrum
Do the winding trick for every speed at once, and the plot you get has a name: the spectrum. This wave mixes a 2 Hz part and a 5 Hz part (and an optional 7 Hz part). Move the sliders and watch the spikes follow.
This wave is centered on zero, so there's no bump at 0 this time. Only the real ingredients show up. (We doubled the balance-point distance so each spike's height matches its slider exactly.)
7Going back: rebuild the wave from the spikes
The spectrum works in reverse too. Turn each spike back into a circle: the spike's position gives the circle's speed, and its height gives the circle's size. Stack the circles like in step 3 and the original wave comes back. This uses the spikes from step 6. Shown in slow motion.
Switch circles off and the rebuilt green wave stops matching the dashed original. All of them together match it exactly. Going from spikes back to the wave is called the inverse Fourier transform. (The balance point also has a direction, which gives each circle's starting angle. Here they all start at the same angle, so you can't see that part.)
8Why people care: two quick examples
A. A musical chord. Three piano notes played together (C, E, G) make one messy wave. The spectrum splits it back into three clean spikes, one per note. Tuner apps and music software do exactly this.
B. Removing noise. A smooth 3 Hz wave gets covered in random fuzz, which we call noise. In the spectrum, the real signal is one tall spike and the noise is a low scatter spread across every speed. Delete everything except the spike, go back to a wave, and the fuzz is gone. Noise-cancelling headphones, photo cleanup, and audio compression (making files smaller, as in MP3) all work this way.
The formula, piece by piece
In Part 1 you watched the Fourier transform happen. Now let's read its formula. It looks scary, but every symbol is something you've already seen. The formula stays pinned at the top while you scroll through this part, and the piece we're talking about lights up.
9eiθ is just a point on a circle
First, a new kind of number. A complex number is a point on a flat map. It has a left-right part and an up-down part. The left-right part is called the real part. The up-down part is called the imaginary part, and the letter i marks it. Don't let the name worry you. Here, "imaginary" just means "the up-down direction".
Now the strange-looking eiθ. The Greek letter θ ("theta") stands for an angle. eiθ means: start at the right-hand edge of a circle of size 1 and walk counterclockwise by the angle θ. You end up at a point, and that point is eiθ. (The letter e is a special number, about 2.718. A famous fact called Euler's formula says it works this way. You never need e's actual value here.)
10The minus sign: wind clockwise
Put a minus sign in front of the angle and the dot goes around the other way. e+iθ goes counterclockwise. e−iθ goes clockwise. That's the only difference.
Why clockwise? Mostly habit. Winding the other way would find exactly the same spikes. Only the angles in the answer would come out flipped.
112πft: f turns every second
Now the angle itself. 2π (about 6.28) is one full turn. Mathematicians measure angles in radians, and a full circle is 2π radians, the same as 360°. f is turns per second. t is time in seconds. So:
- f × t is how many turns you've made so far.
- 2π × f × t is that same amount written as an angle.
12Times x(t): wrapping the wave
x(t) is the wave's height at time t. Multiplying by it changes how far the spinning dot is from the center. When the wave is high, the dot sits far out. When it's low, the dot sits close in. (Multiplying a point by a number just stretches its distance from the center.)
13∫ … dt: add up all the points
The tall S, ∫, is called an integral. Here it just means "add up". dt means "a tiny slice of time". Together they say: add up every point along the wrapped path, each one counted for how long it lasted.
Here we drop points along the path one at a time. The yellow dot is the average of all the points so far. Once every point is in, that average is the balance point (center of mass) from step 5. The formula keeps the total instead of dividing to get the average. That only changes the size of the answer, not its direction.
14X(f): one arrow, two answers
The answer X(f) is a single point. Think of it as an arrow from the center. That one arrow tells you two things:
- Its length, written |X(f)| (the bars mean "size of"), tells you how much of speed f is in the wave.
- Its angle gives the starting angle (phase) of that part of the wave.
The DFT: how a computer does it
A computer can't store a smooth wave. It can only store a list of numbers. The version of the Fourier transform that works on a list is called the discrete Fourier transform, or DFT. "Discrete" just means "made of separate pieces" instead of smooth.
15A computer only has samples
A computer measures the wave at evenly spaced moments. Each measurement is called a sample. N is how many samples we take. The list is written x[0], x[1], … x[N−1]. The square brackets mean "item number n in the list". The stretch of time we measured is the window. How many samples we take each second is the sample rate.
The faint line is the real wave. The computer only ever sees the yellow dots. Our window here is 1 second.
16The integral becomes a sum
With a list instead of a smooth wave, "add up every point" becomes "add up N arrows". The Greek letter Σ ("sigma") means "add these up". Here's the DFT formula:
| ∫ … dt → Σ | Instead of a smooth path, add up N separate arrows, one per sample. |
| x(t) → x[n] | The wave's height becomes sample number n. |
| f → k | k is the number of turns we wind during the whole window. |
| t → n/N | Sample n happens n/N of the way through the window. |
Each sample turns into an arrow. Its length is x[n]. Its angle is k × n/N of a turn, clockwise. A sample below zero points the opposite way. Then we lay the arrows tip to tail, each one starting where the last one ended. Where the chain ends is X[k]. Do that for every k from 0 to N−1 and you've built the whole bar chart, one bar at a time.
The wave here is a size-1 part with 1 cycle per window plus a size-½ part with 3 cycles. Bars show up at k = 1 and k = 3. Their heights are N/2 times the parts' sizes, because we add the arrows instead of averaging them. (The matching bars near the right end are explained next.)
17Bins, and the mirror image
Each k is called a bin, like a bucket that catches one speed. Bin k means "k cycles per window". To turn that into hertz: frequency = k × sample rate ÷ N. For example, with 8 samples per second for one second, bin 3 is 3 Hz.
Now the mirror. In step 16 the bars above N/2 copy the ones below. Here's why. We only look at N dots. Watch both wheels jump one sample at a time:
The right wheel takes huge clockwise jumps, almost a full turn each time. But it lands exactly where a small counterclockwise step would. It's the left wheel seen in a mirror. A real-world wave (no imaginary part) catches the same amount in a mirror-image winding, so bin N−k always matches bin k. That's why people usually only look at the first half of the bars.
18Aliasing: too fast to see
The same thing happens to the wave itself. If a wave wiggles too fast, the samples can't keep up, and the dots look like they came from a slower wave. This is called aliasing: the fast wave hides under an "alias", a fake identity. The fastest speed you can trust is half the sample rate. That's called the Nyquist limit.
Here we take 8 samples per window, so the limit is 4 cycles. Below 4, the green "slowest wave through the dots" matches the real pink wave. Above 4, the dots tell a lie. For example, 7 cycles looks exactly like 1. That's why music is recorded at 44,100 samples per second: it can capture sounds up to about 22,000 Hz, just above the top of human hearing.
19The DFT as a grid: N × N work
Here's all of the DFT's work at once. Each row is one bin k. Each column is one sample n. Each cell holds a small arrow for that k and n, the turn e−i2πkn/N. To get bar k, multiply every sample by its cell's arrow and add along the row.
That's N rows times N columns: N × N = N² multiplications. Doubling N makes it four times the work. For a one-second song clip (44,100 samples), that's almost 2 billion multiplications.
The FFT: the same answer, far faster
The fast Fourier transform, or FFT, computes exactly the same numbers as the DFT. It isn't an approximation. It just avoids repeating work. The trick has three moves: split the samples in half, solve each half, and combine.
20Split: evens and odds
Take the 8 samples. Put the even positions (0, 2, 4, 6) in one group and the odd positions (1, 3, 5, 7) in another. Then split each group the same way, and again, until every group is a single sample.
A DFT of one sample is easy: it's just that sample. Getting down to single samples takes log₂N rounds of splitting. log₂N means "how many times you can halve N before you reach 1". For 8 it's 3, and for a million it's only 20.
21Why the halves can share work
Splitting only helps if we can put the pieces back together cheaply. We can, because the winding waves repeat. Compare bin k with bin k + N/2:
At the even positions their arrows point exactly the same way. At the odd positions they point exactly opposite. So we add up the even samples once and use the result for both bins. We add up the odd samples once too. For one bin we add that sum, and for the other we subtract it.
One more detail: the odd samples sit one step later in time, so their sum gets an extra rotation of k/N of a turn before it's added. That small rotation is called the twiddle factor, written Wk.
E = the DFT of the even samples, O = the DFT of the odd samples (each only N/2 long), Wk = rotate by k/N of a turn, clockwise.
22Butterflies: combining stage by stage
Now build back up, from single samples to the full answer. At each stage, pairs of small answers combine into one answer twice the size, using the rule from step 21. Each crossing X-shape is called a butterfly: two numbers in, two out (top = sum, bottom = difference). Each little circle shows its number as an arrow. Orange marks show a twiddle rotation.
The inputs on the left look shuffled: 0, 4, 2, 6, 1, 5, 3, 7. That's simply the order the even/odd splitting from step 20 left them in. The outputs on the right come out in normal order, X[0] to X[7], and they match the slow N² DFT exactly. (This step uses 8 made-up sample values so the arrows point in more interesting directions.)
23How much faster?
The FFT takes about N × log₂N steps. The plain DFT takes N². Drag the slider and race them at the same speed, assuming a computer that does a billion steps per second.
(Real FFT programs count steps a little differently, but the shape is the same: N log N instead of N².) This speedup is why the FFT is everywhere: phones, Wi-Fi, music apps, MRI scanners, and image compression all run it constantly.
✓Recap
A dot spinning on a circle traces a wave, and its speed, size, and starting angle are all you need to describe it. Stack spinning circles and you can draw almost any wave. The Fourier transform answers the reverse question. It wraps the wave around a center at every possible winding speed and checks where the balance point jumps away from the middle. Those jumps form the spectrum, a list of which speeds are inside and how strong each one is. Turning the spikes back into circles rebuilds the original wave exactly. That's why it's used everywhere for sound, images, radio, and medical scans.
The formula (Part 2) says exactly that. Wind the wave clockwise at f turns per second, stretch each point by the wave's height, and add up all the points. The arrow you get has a length (how much of speed f) and an angle (its starting angle).
The DFT (Part 3) is the same recipe for a list of N samples. The smooth adding-up becomes a sum of N arrows laid tip to tail, one sum for each bin k (k cycles per window). The bars above N/2 mirror the ones below, and speeds above half the sample rate get disguised (aliasing). Done directly, it costs N × N steps.
The FFT (Part 4) gets the identical answer with far less work. Split the samples into evens and odds, again and again, down to single samples. Then combine pairs with butterflies: sum and difference, plus a small twiddle rotation. It works because the winding waves repeat, so each half's work is used twice. That's about N·log₂N steps instead of N², so a million samples takes milliseconds instead of minutes.
The whole thing in one line:
- x(t): the wave's height at time t. This is the string being wrapped.
- e−i2πft: "wind around the circle at speed f". It's a compact way to write the point on a circle at angle 2π·f·t (one full turn is 2π). The minus sign just means clockwise.
- ∫ … dt: add up every point along the whole wrapped string. That's the balance point (center of mass), before dividing by the length.
- X(f): the result for winding speed f. How far it is from the middle tells you how much of speed f is in the wave. Its direction gives the starting angle.