The Fourier Transform from Scratch — Reading a Signal as a Stack of Pure Tones

A signal drawn against time hides the thing you usually want to know: which frequencies are in it, and how much of each. This article builds the Fourier transform from one idea — measure a signal against a pure tone with an inner product — then takes the continuous integral apart symbol by symbol, does the same for the DFT, separates two tones by hand, and ends on the three traps that bite in practice: aliasing, finite resolution, and spectral leakage.

Théorie analytique de la chaleur

The graph you have is not the graph you want

Record a second of a piano chord and plot it. What you get is a wobbling line: pressure against time. Somewhere in that wobble are three struck notes, the hum of the room, and the hiss of the microphone — but you cannot see any of them. The plot answers the question "what was the pressure at each instant?" when the question you actually have is "which tones are in here, and how loud is each one?"

The Fourier transform is the machine that converts the first answer into the second. It takes a function of time and returns a function of frequency, and every serious piece of signal work — audio codecs, JPEG, MRI reconstruction, the spectrogram a speech model eats for breakfast — starts by running it.

This article builds it in the order the idea actually assembles: the two prerequisites (the pure tone, and what it means for two tones to be orthogonal), the one measuring device that does all the work (the inner product), the continuous formula taken apart one symbol at a time, the discrete version you can actually compute, a worked example, and then the three things that go wrong.

Prerequisite 1: the pure tone

The atom of this whole subject is the sinusoid — a single pure tone:

$$x(t) = A \sin(2\pi f t + \phi)$$

Three numbers describe it completely. $A$ is the amplitude, how loud. $f$ is the frequency in cycles per second (hertz), how high the pitch — $2\pi f t$ turns cycles into radians, so that $t$ advancing by $1/f$ seconds advances the angle by exactly one full turn. $\phi$ is the phase, where in its cycle the wave starts at $t = 0$.

In words: a pure tone is fully pinned down by three dials — how loud, how high, and where it starts.

Two conventions make the algebra bearable. First, write the tone as a complex exponential rather than a sine, using Euler's formula:

$$e^{i\theta} = \cos\theta + i\sin\theta$$

Read as a picture: $e^{i\theta}$ is the point on the unit circle at angle $\theta$, with the cosine as its horizontal coordinate and the sine as its vertical one. So $e^{2\pi i f t}$, as $t$ runs forward, is a dot going around the unit circle $f$ times per second. That single object carries both the cosine and the sine at once, which is why it replaces them: one complex tone instead of two real ones.

Second, let amplitude and phase live together in one complex number. A complex number $c = |c| e^{i\phi}$ has a magnitude and an angle — exactly the two things a tone needs. So "the amount of frequency $f$ present" will come out as a single complex number whose magnitude is the amplitude and whose angle is the phase. That is not a trick; it is the reason the transform's output is complex-valued.

Prerequisite 2: orthogonality — why tones do not contaminate each other

Here is the fact that makes the whole method possible: different frequencies do not interfere with the measurement of each other. Stated precisely, over a window of length $T$,

Term by term: the overbar is the complex conjugate (flip the sign of the imaginary part, which for $e^{i\theta}$ means $e^{-i\theta}$); multiplying $e^{2\pi i f_1 t}$ by $e^{-2\pi i f_2 t}$ adds the exponents, leaving a single tone at the difference frequency $f_1 - f_2$; and integrating a tone over a whole number of its own cycles gives zero, because every rise is cancelled by an equal fall. Only when the difference frequency is zero does the integrand become the constant $1$, whose integral is the window length $T$.

In words: multiply a signal by a tone, average, and every frequency except that one averages itself away. The frequencies $f_k = k/T$ — a whole number of cycles inside the window — form an orthogonal family, the continuous analogue of perpendicular axes. The Fourier transform is nothing more than reading off coordinates along those axes, and the "$f_1 - f_2 = k/T$" clause in the formula is the fine print that will come back to bite us later as leakage.

The intuition: a signal is a stack, and we weigh one layer at a time

Now the central claim, which is Fourier's 1822 insight: any reasonable signal can be written as a sum of pure tones. Not approximated by — written as. A square wave, a drum hit, a spoken vowel: each is some particular recipe of sinusoids added together. The signal is a stack of transparent layers, one per frequency, and what you see on the oscilloscope is the stack viewed from above.

If that is true, then "analysing" a signal means one thing: find the recipe. And thanks to orthogonality we can find it one ingredient at a time, without solving for all of them simultaneously. To ask "how much 440 Hz is in this signal?", multiply the signal by a 440 Hz tone and average. The 440 Hz layer, multiplied by itself, is everywhere non-negative and averages to something big. Every other layer, multiplied by the 440 Hz tone, becomes a tone at a nonzero difference frequency and averages to zero. One number falls out, and it is the amount of 440 Hz — regardless of what else was in there.

A geometric way to say the same thing: think of the signal as a vector in a space whose axes are frequencies. Multiplying-and-averaging is the inner product with one axis, i.e. a projection. Just as $v \cdot \hat{e}_x$ pulls the $x$-coordinate out of a 3D vector without needing to know $y$ or $z$, the inner product against $e^{2\pi i f t}$ pulls out the $f$-coordinate of a signal. The Fourier transform is the full list of those coordinates.

The continuous Fourier transform, one symbol at a time

Take the inner-product recipe, let the window stretch to the whole time axis, and write it down:

Read left to right:

• $x(t)$ is the input signal, a function of time.
• $X(f)$ is the output, called the spectrum — a different function, of frequency. Feed it a frequency, get back a complex number.
• $e^{-2\pi i f t}$ is the probe tone at frequency $f$. The minus sign is not decoration: the inner product of complex functions is $\langle x, y \rangle = \int x \overline{y}$, and the conjugate of the tone $e^{2\pi i f t}$ is $e^{-2\pi i f t}$. So the minus sign is exactly what makes this a projection onto that tone and not something else.
• Multiplying $x(t)$ by the probe is the "compare against this frequency" step; $\int \dots dt$ is the "average over all time" step that kills every other frequency.

And the output, unpacked: $|X(f)|$ is how much of frequency $f$ is present (the amplitude), and $\arg X(f)$ is where in its cycle that component sits (the phase). Plotting $|X(f)|$ against $f$ gives the picture we wanted at the start — the chord's notes standing up as separate spikes.

The transform is reversible, which is what "the signal is the stack" really means:

In words: to rebuild the signal, take every frequency's tone $e^{2\pi i f t}$, scale it by that frequency's coefficient $X(f)$, and add them all up. Note the sign has flipped to $+$ — analysis projects onto the conjugate, synthesis adds the tones themselves. Nothing is lost going either way: the time picture and the frequency picture are two descriptions of one object.

One immediate reading: at $f = 0$ the probe is $e^0 = 1$, so $X(0) = \int x(t)\,dt$ — the DC component, the signal's total offset from zero. The lowest "frequency" is the average value.

The discrete version: what a computer actually runs

A computer has neither an infinite time axis nor a continuum of samples. It has $N$ numbers $x_0, x_1, \dots, x_{N-1}$, taken at a sampling rate $f_s$ samples per second, so sample $n$ sits at time $t = n/f_s$ and the whole record lasts $T = N/f_s$ seconds. Replace the integral by a sum and the continuum of frequencies by the orthogonal family $f_k = k/T$, and the formula becomes the Discrete Fourier Transform (DFT):

In words: for each of $N$ test frequencies, multiply the samples by that frequency's tone and add them up; the total is how much of that frequency the record contains.

Every piece maps onto something in the continuous version:

• $x_n$ replaces $x(t)$ — the signal, now a finite list.
• $\sum_{n=0}^{N-1}$ replaces $\int dt$ — averaging over the record instead of over all time.
• $e^{-2\pi i k n/N}$ replaces $e^{-2\pi i f t}$: substituting $f = k/T$ and $t = n/f_s$ gives $f t = (k/T)(n/f_s) = kn/N$, since $T f_s = N$. The exponent is the same exponent; only the bookkeeping changed.
• $X_k$ is called bin $k$, and it means the amount of frequency $f_k = k \cdot f_s / N$ present.

That last line is the single most useful fact in applied Fourier work: bin index $k$ converts to hertz as $f_k = k f_s / N$, and consecutive bins are spaced by

$$\Delta f = \frac{f_s}{N} = \frac{1}{T}$$

In words: the finest frequency detail you can see is one over the length of the recording.

The spacing depends only on how long you recorded, not how fast you sampled. Want to tell 440 Hz from 441 Hz? You need $\Delta f \le 1$ Hz, so you need at least one full second of audio. No amount of oversampling substitutes for it.

The inverse is the same sum with the sign flipped and a $1/N$ out front:

$$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k\, e^{+2\pi i k n / N}$$

In words: add every bin's tone back together, each scaled by its coefficient, and you get the original samples exactly.

The $1/N$ is there because the discrete orthogonality relation is $\sum_{n=0}^{N-1} e^{2\pi i (k - k')n/N} = N$ when $k = k'$ (and $0$ otherwise — it is a geometric series whose ratio is an $N$-th root of unity). Projecting onto a basis vector of squared length $N$ overcounts by $N$, and the inverse divides it back out. Where that constant sits is pure convention, which is why different libraries normalise differently — a real source of factor-of-$N$ bugs.

Computed as written, the DFT costs $N$ multiplications for each of $N$ bins: $O(N^2)$. The FFT is the divide-and-conquer reorganisation that gets the same numbers in $O(N \log N)$; it is a faster route to this formula, not a different transform. That algorithm is the subject of The FFT from Scratch.

Worked example: pulling two tones back apart

Mix two sinusoids, one loud and low, one quiet and higher:

$$x(t) = \sin(2\pi \cdot 5t) + 0.5 \sin(2\pi \cdot 12t)$$

Sample it at $f_s = 128$ Hz for exactly one second, so $N = 128$ and $\Delta f = 128/128 = 1$ Hz. Each bin is one hertz wide, and both tones sit on exact bin centres — 5 Hz lands in bin 5, 12 Hz in bin 12.

import numpy as np

fs, N = 128, 128
t = np.arange(N) / fs
x = np.sin(2*np.pi*5*t) + 0.5*np.sin(2*np.pi*12*t)

X = np.fft.fft(x)
mag = np.abs(X)

for k in np.argsort(mag)[::-1][:4]:
    print(f"bin {k:3d}  =  {k*fs/N:5.1f} Hz   |X| = {mag[k]:.1f}")

Out come exactly four peaks, and every one of them is predictable:

bin   5  =    5.0 Hz   |X| = 64.0
bin 123  =  123.0 Hz   |X| = 64.0
bin  12  =   12.0 Hz   |X| = 32.0
bin 116  =  116.0 Hz   |X| = 32.0

Three things to read off. First, the magnitudes. A real sinusoid of amplitude $A$ produces a peak of height $NA/2$, because $\sin\theta = (e^{i\theta} - e^{-i\theta})/2i$ splits the tone into two complex exponentials of size $A/2$, and the sum over $N$ samples multiplies each by $N$. So $A = 1$ gives $128 \times 1/2 = 64$ and $A = 0.5$ gives $32$. The ratio of the peaks is the ratio of the amplitudes — the transform recovered the recipe.

Second, the mirror. Bins 123 and 116 are the $e^{-i\theta}$ halves: $123 = 128 - 5$ and $116 = 128 - 12$. For any real-valued input, $X_{N-k} = \overline{X_k}$, so the top half of the spectrum is a reflection of the bottom half and carries no new information. This is why plots stop at $f_s/2$ and why np.fft.rfft exists.

Third, the phase. Printing the raw values gives $X_5 = -64i$ and $X_{12} = -32i$: purely imaginary, no real part. That is the signature of a sine rather than a cosine — a cosine would have come out purely real. Discarding the phase and keeping only $|X|$ throws that away, which is exactly why you cannot reconstruct audio from a magnitude spectrogram alone without some phase-recovery trick.

Three pitfalls, in the order they will bite you

Aliasing: sampling too slowly forges a frequency

The Nyquist–Shannon sampling theorem says a signal containing no frequency above $f_{\max}$ is fully determined by samples taken at $f_s > 2 f_{\max}$. Half the sampling rate, $f_s/2$, is the Nyquist frequency — the highest frequency the samples can represent at all.

Break that and the energy does not vanish; it comes back in disguise. A tone at $f$ above Nyquist is indistinguishable, at the sample instants, from one at $|f - m f_s|$ for the integer $m$ that brings it into range. Add np.sin(2*np.pi*100*t) to the example above, still at $f_s = 128$: 100 Hz is past Nyquist (64 Hz), and the peak appears at bin 28 — because $128 - 100 = 28$. A perfectly clean 100 Hz tone is reported as a perfectly clean 28 Hz tone, and nothing in the data marks it as fake. The only fix is prevention: a low-pass anti-aliasing filter before the sampler, which is why every audio interface has one in hardware.

Resolution: a short window cannot tell close frequencies apart

$\Delta f = 1/T$ is a hard floor. Two tones closer together than one bin land in the same bin and merge into a single peak; no post-processing separates them. The standard mistake is to zero-pad the record and celebrate the smoother-looking spectrum: zero-padding interpolates the same underlying information onto a finer grid, making peaks easier to locate, but it does not resolve tones that were already merged. And since $T$ is also the interval over which the spectrum is an average, wanting both fine frequency detail and fine timing detail puts you in direct conflict — the time–frequency trade-off that forces a spectrogram to pick a window length and live with it.

Leakage: a tone that is not an exact bin smears across the whole spectrum

Go back to the orthogonality condition: it held only for frequency differences that are whole numbers of cycles per window. A tone that completes a fractional number of cycles inside the window is orthogonal to nothing, and its energy spills into every bin. Take $\sin(2\pi \cdot 5.5 t)$ with the same $N = 128$ — 5.5 cycles in the window, dead between bins:

bin:     3      4      5      6      7      8
|X|:  10.5   15.7   42.6   39.0   12.0    6.7

Instead of one spike of 64 there are two shoulders of ~41 and a long tail of skirts. Physically, the DFT assumes the record repeats forever, so cutting a wave mid-cycle creates a discontinuity at the seam, and that artificial jump has broadband content.

The standard treatment is a window function: multiply the samples by a curve that tapers smoothly to zero at both ends, removing the seam. Applying a Hann window to the same signal gives

bin:     3      4      5      6      7      8
|X|:  0.81   5.60  27.01  27.03   5.58   0.79

The distant skirts drop by more than an order of magnitude. Note what it cost: the main lobe is still spread over two bins (slightly wider than before), and the peak heights shrank because the window removed signal energy. That is the permanent bargain of windowing — lower sidelobes in exchange for a wider main lobe and an amplitude correction you have to apply yourself.

How this shows up on the job

You will essentially never write the DFT sum by hand; you will call np.fft.rfft, torch.stft, or librosa.melspectrogram. What you will spend real time on is the four parameters those functions expose, and each one is a pitfall above wearing a keyword argument.

n_fft is your frequency resolution. It fixes $\Delta f = f_s / n_{\mathrm{fft}}$. At 16 kHz speech with n_fft=512, bins are 31 Hz apart — fine for formants, too coarse to separate the harmonics of a low male voice. Raising it buys frequency detail and pays in time detail.

hop_length and window are leakage management. A spectrogram chops audio into overlapping frames; each frame is a finite window, so each frame leaks. Hann is the default for a reason, and the conventional 50–75 % overlap exists so that the tapered-away edges of one frame are covered by the middle of the next.

Normalisation conventions differ, and the symptom is a clean factor of $N$. NumPy puts the $1/N$ on the inverse; some libraries use $1/\sqrt{N}$ on both sides; rfft returns $N/2 + 1$ bins, so summing its magnitudes double-counts nothing but summing power without a factor of 2 for the folded half undercounts. When a measured level is off by a suspiciously round factor, check the convention before the physics.

Anything reported below Nyquist can still be an alias. If a spectrum shows a tone you cannot account for, verify the anti-aliasing path before hunting for it in the source. Resampling in software has the same requirement: downsampling without low-passing first folds the discarded top octave back down into the audible band.

Summary

• A time plot answers "what was the value at each instant"; the Fourier transform answers "which frequencies are present, and how much of each"
• The whole method is one measuring device — the inner product $\int x(t) e^{-2\pi i f t} dt$ — and it works one frequency at a time because distinct frequencies are orthogonal over the window
• Output is complex on purpose: magnitude is amplitude, argument is phase
• The DFT $X_k = \sum_n x_n e^{-2\pi i kn/N}$ is the same formula on a finite record; bin $k$ means $f_k = k f_s / N$, and bin spacing $\Delta f = 1/T$ is set by record length alone
• Three hard limits: sample above $2f_{\max}$ or frequencies come back disguised (aliasing); tones closer than $1/T$ cannot be separated (resolution); tones off bin centre smear across the spectrum unless you window (leakage)

For the $O(N \log N)$ algorithm and the convolution theorem that follows from it, continue to The FFT from Scratch. For the linear-algebra reading of "project onto an orthogonal basis", see Linear Algebra for AI.

Exercises

1. You record 0.25 seconds of audio at $f_s = 8000$ Hz. What is the bin spacing $\Delta f$, how many bins does the DFT produce, and which bin index corresponds to 1000 Hz?
2. A signal is sampled at $f_s = 1000$ Hz and contains a pure tone at 700 Hz with no anti-aliasing filter. At what frequency will the peak appear, and why can you not detect from the samples alone that it is spurious?
3. A colleague needs to distinguish two engine harmonics 3 Hz apart. He records 0.2 s at a very high sampling rate and zero-pads to 65536 points, then reports that the peaks still merge. What is wrong with his approach, and what must he change?
4. Taking the DFT of $\cos(2\pi \cdot 10 t)$ with $f_s = 64$, $N = 64$ gives $X_{10} = 32$ — purely real — while the same experiment with $\sin$ gives $X_{10} = -32i$. Explain both the magnitude 32 and the difference in phase.