Page plan · 15 pages

Written for: Second-year undergraduates in engineering, physics or mathematics

1. 1

   The Fourier transform, from a vibrating string to the FFT

   • This talk follows one idea from a vibrating string to the fast algorithm used everywhere today.
   • Any reasonable signal can be written as a sum of simple oscillations.
   • We move from series to integral to discrete transform to FFT.
   • Goal: understand what the transform means and why the FFT makes it practical.
2. 2

   A plucked string and its overtones

   • A plucked string vibrates at a fundamental frequency plus overtones at integer multiples.
   • Each overtone is a standing wave, a sine shape fitting the string with fixed ends.
   • The mix of overtone strengths gives the instrument its timbre.
   • So a complicated motion decomposes into simple sinusoidal modes.
3. 3

   Fourier's 1822 heat theory and the birth of the series

   • Fourier presented his heat conduction work in 1822 in his book on the analytical theory of heat.
   • He claimed an arbitrary temperature profile can be expanded in sines and cosines.
   • The heat equation is linear, so each sinusoidal mode can be solved separately and added.
   • Convergence questions this raised drove much of later analysis.
4. 4

   Finding the coefficients by orthogonality

   • Sines and cosines of different integer frequencies are orthogonal over one period.
   • Multiplying the signal by one basis function and integrating isolates that coefficient.
   • Every other term integrates to zero, leaving only the matching one.
   • This is like finding a vector component with a dot product.
5. 5

   Building a square wave from sines

   • A square wave contains only odd harmonics, with amplitudes falling like 1/n.
   • Adding more terms makes the sum hug the flat tops more closely.
   • Near each jump an overshoot remains: the Gibbs phenomenon.
   • The overshoot narrows with more terms but does not vanish.
6. 6

   Letting the period grow without limit

   • For a non-periodic signal, let the period T grow toward infinity.
   • Harmonic frequencies get closer together and the sum becomes an integral.
   • Discrete coefficients become a continuous function of frequency.
   • The transform treats a non-repeating signal as having infinite period.
7. 7

   The forward and inverse transform as an integral pair

   • The forward transform integrates f(t) times e^(-iωt) over all time to give F(ω).
   • The inverse transform integrates F(ω) times e^(iωt) to recover f(t).
   • Conventions differ in where the factor of 2π is placed, so check the textbook.
   • The two integrals form a pair carrying the same information.
8. 8

   Common pairs: rectangle, Gaussian, exponential, delta

   • A rectangle pulse transforms into a sinc function.
   • A Gaussian transforms into another Gaussian; narrow in time means wide in frequency.
   • A one-sided decaying exponential transforms into a Lorentzian-type function.
   • A delta function transforms into a constant, containing all frequencies equally.
9. 9

   Linearity, shifting and scaling

   • Linearity: the transform of a sum is the sum of the transforms.
   • Shifting a signal in time multiplies its transform by a phase factor, leaving magnitude unchanged.
   • Compressing a signal in time stretches its transform in frequency.
   • These rules let us build new pairs from known ones.
10. 10

    Convolution becomes multiplication

    • Convolving two signals in time equals multiplying their transforms in frequency.
    • This turns a hard integral into a simple pointwise product.
    • Filtering is convolution with an impulse response, so it becomes multiplication by a frequency response.
    • The duality also holds: multiplication in time is convolution in frequency.
11. 11

    Sampling, aliasing and the discrete Fourier transform

    • Computers see only samples, so we sample the signal at regular intervals.
    • Sampling too slowly makes high frequencies masquerade as low ones: aliasing.
    • The sampling rate must exceed twice the highest frequency present.
    • The DFT maps N samples to N frequency values.
12. 12

    Why the direct sum is slow: N² against (N/2)·log₂N

    • The direct DFT needs N² complex multiplications.
    • The radix-2 FFT needs only (N/2)·log₂N.
    • At N = 1024, that is 1,048,576 versus 5,120 multiplications.
    • At N = 4096, it is 16,777,216 versus 24,576.
    • The gap widens as N grows.

    Table: Complex multiplications: direct DFT versus radix-2 FFT. Source: 2.161 Signal Processing: Continuous and Discrete, Lecture 12 notes (Fall 2008) · checked 2026-10-10

13. 13

    Cooley and Tukey's 1965 split into even and odd samples

    • Cooley and Tukey published their algorithm in 1965.
    • Split the N samples into even-indexed and odd-indexed halves.
    • Each half is a DFT of size N/2, combined using twiddle factors.
    • Repeating the split log₂N times gives the N log N cost.
14. 14

    MRI, audio compression and Wi-Fi: the transform at work

    • MRI scanners measure frequency-space data and use an inverse FFT to form images.
    • Audio compression transforms sound into frequency components so inaudible detail can be discarded.
    • Wi-Fi uses OFDM, where FFTs modulate and demodulate many subcarriers.
    • In all three, the FFT makes the transform fast enough for real use.
15. 15

    Key ideas to keep and where to read further

    • Key idea: signals decompose into sinusoids, found by orthogonality.
    • The transform turns convolution into multiplication.
    • Sampling leads to the DFT, and the FFT computes it in N log N time.
    • Read further in your signals and systems textbook and in Cooley and Tukey's 1965 paper.