The Fourier Transform and the FFT

Any signal can be looked at in two completely equivalent ways. The time domain asks "what is the value at each instant?" The frequency domain asks "which oscillations, and how strong, add up to make this signal?" The Fourier transform is the exact dictionary that translates between the two, and the Fast Fourier Transform (FFT) is the algorithm that does the translation quickly enough to run on real data millions of times a second.

The one idea. Every signal is a sum of pure sine waves. The Fourier transform finds the recipe — the amplitude and phase of each sine wave needed to rebuild the signal. Reading that recipe is the frequency domain; the original wiggle is the time domain.

This note states the transform mathematically, then walks through the five textbook signals — impulse, step, ramp, cosine, sine — plotting each one in both domains so the pairing becomes visual, not just symbolic.

  1. Two domains, one signal
  2. The mathematics
  3. Examples in both domains
  4. Putting it together: superposition
  5. Summary of transform pairs

Two domains, one signal

Feeding a block of samples into the FFT returns, for each frequency bin, a complex number carrying two facts: a magnitude (how much of that frequency is present) and a phase (where in its cycle that wave sits). The pipeline is short:

The FFT is lossless and invertible: the inverse FFT turns the bins back into the exact original samples. Nothing is thrown away — the two domains are the same information wearing different clothes.

The mathematics

Continuous Fourier transform

For a continuous signal $x(t)$, the Fourier transform and its inverse are

$$ X(f) = \int_{-\infty}^{\infty} x(t)\, e^{-i 2\pi f t}\, dt, \qquad x(t) = \int_{-\infty}^{\infty} X(f)\, e^{\,i 2\pi f t}\, df . \tag{2.1} $$
Equation 2.1: Continuous Fourier transform (analysis and synthesis)

The kernel $e^{-i2\pi f t} = \cos(2\pi f t) - i\sin(2\pi f t)$ is a pure oscillation at frequency $f$. The integral correlates the signal against that oscillation: if $x$ contains a component at $f$, the product stays in step and the integral is large; if it does not, the product averages to zero. Doing this for every $f$ sweeps out the whole spectrum.

The Discrete Fourier Transform (DFT)

Real data is a finite list of $N$ samples $x[0], x[1], \ldots, x[N-1]$, so the integral becomes a sum — the DFT:

$$ X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-i 2\pi k n / N}, \qquad x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\, e^{\,i 2\pi k n / N}, \qquad k = 0,\ldots,N-1 . \tag{2.2} $$
Equation 2.2: Discrete Fourier Transform (analysis and synthesis)

Each output $X[k]$ measures how strongly the signal oscillates at bin $k$, which corresponds to a physical frequency

$$ f_k = \frac{k}{N}\, f_s , \tag{2.3} $$
Equation 2.3: Bin index → frequency

where $f_s$ is the sampling rate. Bin $k$ is simply "$k$ complete cycles across the window." Because our signals are real, the spectrum is conjugate-symmetric, $X[N-k] = \overline{X[k]}$, so the magnitude is mirror-symmetric and we only need to plot the lower half $k = 0, \ldots, N/2$ (the top being the Nyquist frequency).

What makes the FFT fast

Computed directly, Equation 2.2 costs $N$ multiply-adds for each of $N$ outputs — $O(N^2)$ work. The FFT (Cooley–Tukey) computes the identical numbers in $O(N\log N)$ by splitting the sum into even- and odd-indexed samples and reusing the shared pieces:

$$ X[k] = \underbrace{E[k]}_{\text{even samples}} + e^{-i 2\pi k/N}\,\underbrace{O[k]}_{\text{odd samples}}, \tag{2.4} $$
Equation 2.4: Radix-2 split — the heart of the FFT

where $E$ and $O$ are half-length DFTs, each again split the same way. The factor $e^{-i2\pi k/N}$ is the twiddle factor, and the add/subtract pairing is the butterfly. For $N = 1024$ this is roughly a 100× speed-up; the FFT is what made frequency analysis practical. It changes the cost, not the result — every spectrum below is exactly what the DFT of Equation 2.2 produces.

Reading a magnitude spectrum

In the plots that follow, the left panel is the signal $x[n]$ in time, and the right panel is the magnitude spectrum $|X[k]|$. Writing $X[k] = |X[k]|\,e^{i\angle X[k]}$ splits each bin into magnitude (how much of that frequency) and phase (where in its cycle). Magnitude is what the eye reads first — a spike means a strong pure tone, a flat line means all frequencies are present equally, and a decaying curve means the energy is concentrated at low frequencies with a tail.

Examples in both domains

All examples use $N = 64$ samples. Watch a recurring theme: the more localized a signal is in one domain, the more spread out it is in the other.

Impulse

The unit impulse $\delta[n]$ is $1$ at a single instant and $0$ everywhere else — the most localized signal possible.

$$ \delta[n] = \begin{cases}1 & n = 0\\ 0 & n \neq 0\end{cases} \qquad\Longrightarrow\qquad X[k] = \sum_{n} \delta[n]\, e^{-i2\pi kn/N} = e^{0} = 1 \ \ \text{for every } k . \tag{3.1} $$
Equation 3.1: Impulse and its transform

Time domain — $\delta[n]$

Frequency domain — $|X[k]|$ (flat)

Figure 3.1: Impulse. A single spike in time contains every frequency in equal measure — its spectrum is perfectly flat. (Continuous analogue: $\delta(t)\leftrightarrow 1$.)

A perfectly sharp event in time is maximally spread in frequency: to build an infinitely thin spike you need all frequencies, added in phase. This is the Fourier face of the uncertainty principle — you cannot be sharp in both domains at once.

Step

The step switches from $0$ to $1$ and stays there. Its single sharp edge is what matters.

$$ u[n] = \begin{cases}0 & n < n_0\\ 1 & n \ge n_0\end{cases} \qquad\Longrightarrow\qquad U(f) \ \sim\ \tfrac{1}{2}\delta(f) \;+\; \frac{1}{i\,2\pi f}. \tag{3.2} $$
Equation 3.2: Step and its transform

Time domain — $u[n]$

Frequency domain — $|X[k]|$ ($1/f$ tail)

Figure 3.2: Step. A huge DC component (its non-zero average) plus a long high-frequency tail that decays like $1/f$ — the signature of a sharp edge. Band-limiting this tail is exactly what causes Gibbs ringing.

The tall bar at $k=0$ is the DC term — the signal's average. The slowly decaying tail says a step still needs plenty of high frequencies to render its edge sharply; cut them off and the edge overshoots and rings.

Ramp

A ramp rises linearly across the window — like one tooth of a sawtooth.

$$ r[n] = \frac{n}{N-1} \qquad\Longrightarrow\qquad R(f)\ \sim\ \frac{1}{(i\,2\pi f)^2}\ \text{(plus a DC term)} . \tag{3.3} $$
Equation 3.3: Ramp and its transform

Time domain — $r[n]$

Frequency domain — $|X[k]|$

Figure 3.3: Ramp. Like the step it is dominated by DC and low frequencies, but its harmonics fall off faster (a smoother shape needs less high-frequency content than a hard edge).

Compared with the step, the ramp has no instantaneous jump, so its high-frequency tail is weaker: smoother in time ⇒ less high-frequency content. Sharpness costs high frequencies.

Cosine

Now a pure tone — a cosine at exactly $f_0 = 6$ cycles per window.

$$ \cos(2\pi f_0 t) \;\longleftrightarrow\; \tfrac{1}{2}\big[\delta(f-f_0) + \delta(f+f_0)\big] . \tag{3.4} $$
Equation 3.4: Cosine and its transform

Time domain — $\cos(2\pi\cdot 6\,n/N)$

Frequency domain — spike at $k=6$

Figure 3.4: Cosine. A single pure frequency shows up as a single spike at its bin $k=6$ (plus its mirror image above Nyquist, not shown). One tone in, one line out.

A never-ending pure oscillation is the exact opposite of the impulse: perfectly spread in time, perfectly localized in frequency. All of its energy lives in one bin.

Sine

The same frequency as the cosine, but a sine — shifted by a quarter cycle.

$$ \sin(2\pi f_0 t) \;\longleftrightarrow\; \tfrac{1}{2i}\big[\delta(f-f_0) - \delta(f+f_0)\big] . \tag{3.5} $$
Equation 3.5: Sine and its transform

Time domain — $\sin(2\pi\cdot 6\,n/N)$

Frequency domain — spike at $k=6$

Figure 3.5: Sine. Its magnitude spectrum is identical to the cosine's — a single spike at $k=6$. Sine and cosine differ only in phase (a 90° shift), which the magnitude plot deliberately discards.

This is the crucial subtlety of the magnitude spectrum: sine and cosine look different in time yet have the same magnitude spectrum. Their entire difference — the $90^\circ$ shift — lives in the phase, $\angle X[k]$, which the magnitude plot throws away. Magnitude tells you which frequencies; phase tells you how they line up.

Putting it together: superposition

The Fourier transform is linear: the transform of a sum is the sum of the transforms. So a signal built from several tones shows one spike per tone — and the FFT pulls them apart cleanly. Below, $x[n] = \sin(2\pi\cdot 6\, n/N) + \tfrac{1}{2}\sin(2\pi\cdot 15\, n/N)$.

$$ a\,x_1[n] + b\,x_2[n] \;\longleftrightarrow\; a\,X_1[k] + b\,X_2[k] . \tag{4.1} $$
Equation 4.1: Linearity of the transform

Time domain — sum of two sines

Frequency domain — two spikes

Figure 4.1: Two tones added in time become two separate spikes in frequency: a tall one at $k=6$ and a half-height one at $k=15$ (its amplitude is half). This separation is exactly why the FFT is the workhorse of audio, radio, imaging and signal processing.

The tangled time-domain wiggle looks complicated, but the spectrum is obvious: two lines, at the two frequencies present, with heights in the ratio $2:1$ matching their amplitudes. Turning a hard time-domain problem into an easy frequency-domain one is the whole point of the FFT.

Summary of transform pairs

Signal (time)Spectrum (frequency)Fingerprint
Impulse $\delta[n]$$X[k] = 1$Flat — all frequencies equally
Constant / step edgeDC spike $+\ 1/f$ tailLow frequencies dominate; slow tail
Ramp $n$DC $+\ 1/f^2$-ish decayLow frequencies; faster roll-off
Cosine $\cos(2\pi f_0 t)$$\tfrac12[\delta(f{-}f_0)+\delta(f{+}f_0)]$Single spike at $f_0$
Sine $\sin(2\pi f_0 t)$$\tfrac{1}{2i}[\delta(f{-}f_0)-\delta(f{+}f_0)]$Single spike at $f_0$ (differs in phase)
Sum of tones$\sum$ of spikesOne line per tone (linearity)
Table 5.1: The signals above and their frequency-domain fingerprints. 'Localized' and 'spread' are always opposite across the two domains.

Two threads run through every example. First, duality: sharp in time ⇔ broad in frequency, and vice versa (impulse vs. cosine are the extremes). Second, linearity: complicated signals are just sums of simple tones, and the FFT reads off that recipe in $O(N\log N)$ time — which is why it is one of the most widely used algorithms ever written.