Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 68 ยท Series, Transforms and PDEs

The Fourier Transform and the FFT

From Fourier series to the Fourier transform and the FFT: spectra, frequency bins, spectral leakage, windowing and filtering a noisy signal with NumPy.

A Fourier series handles signals that repeat forever. Real signals rarely do: a spoken word, a single pulse, a vibration measured for two seconds. The Fourier transform removes the need for periodicity. It takes any signal in the time domain and tells you how much of each frequency it contains, a picture called the spectrum.

On a computer you never have a continuous signal; you have samples. The discrete Fourier transform (DFT) does the same job for a list of numbers, and the fast Fourier transform (FFT) is a clever algorithm that computes it in about N log N steps instead of N**2. That speed-up is why spectrum analysers, audio software, MRI scanners and Wi-Fi radios exist.

Continuous transform

For a function f(t), the Fourier transform is

F(w) = integral from -infinity to infinity of f(t) * e**(-i w t) dt

and the inverse recovers the signal:

f(t) = (1/(2*pi)) * integral of F(w) * e**(i w t) dw

Here w is angular frequency in radians per second (ordinary frequency is f = w/(2*pi) in hertz). F(w) is complex: its magnitude says how strong that frequency is, its angle says how it is shifted in time. Euler's formula, covered in Complex Numbers and Phasors, is what makes e**(-i w t) a rotating pointer that "tunes in" to frequency w.

Some pairs worth remembering:

  • A pure tone cos(w0 t) becomes two sharp spikes at +w0 and -w0.
  • A narrow pulse has a wide spectrum; a wide pulse has a narrow one. Time and frequency spread trade off against each other (the engineering cousin of the uncertainty principle).
  • A Gaussian pulse transforms into another Gaussian.
  • Differentiating f(t) multiplies F(w) by i*w, which turns calculus into algebra. The Laplace transform uses the same idea.

The discrete Fourier transform

Sample a signal N times, at spacing dt (sampling rate fs = 1/dt). The DFT produces N numbers:

X[k] = sum over n = 0..N-1 of x[n] * e**(-2*pi*i*k*n/N)

Index k corresponds to the frequency k * fs / N hertz. Two facts decide how you read an FFT plot:

  1. Resolution. Bins are fs/N = 1/T apart, where T is the recording length. To tell two close tones apart you need a longer recording, not a faster sampler.
  2. Nyquist limit. Only frequencies below fs/2 can be represented. A faster tone is aliased: it masquerades as a lower one (a wagon wheel appearing to spin backwards in film).

For real signals, the second half of the spectrum mirrors the first, so NumPy offers rfft, which returns only the non-negative frequencies, and rfftfreq, which gives their values in hertz.

flowchart LR
    A["samples x[n]<br/>time domain"] --> B["FFT"]
    B --> C["spectrum X[k]<br/>frequency domain"]
    C --> D["modify:<br/>filter, scale, mask"]
    D --> E["inverse FFT"]
    E --> F["new signal"]

Filtering with the FFT means transform, change some bins, and transform back.

Python Finding the tones in a signal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The amplitude scaling 2*|X|/N is the convention that turns the spectrum back into the sizes of the original tones (the 2 accounts for energy split between +f and -f).

Leakage and windowing

An FFT assumes your recording repeats forever. If the recording contains a whole number of cycles, the copies join smoothly. If it does not, the copied pieces meet with a jump, and that artificial discontinuity smears energy across many bins: spectral leakage. It is the same ringing as the Gibbs phenomenon.

The cure is a window: multiply the recording by a smooth taper that fades to zero at both ends, so there is no jump to smear. The Hann window 0.5 - 0.5*cos(2*pi*n/(N-1)) (np.hanning) is a good default. The price is a slightly wider main peak and a lower height (a Hann window halves the average amplitude, so rescale by the window's mean if you need true amplitudes).

Python Leakage with and without a Hann window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without a window, bins far away from the tone still carry a visible fraction of the peak; with Hann they are about 160 times smaller. Divide by sum(window) rather than N when you rescale a windowed spectrum. Because 52.5 Hz falls between two bins, neither version shows the true height of 1 (the peak is under-read), which is called scalloping loss.

Filtering a noisy signal

Because convolution in time becomes multiplication in frequency, filtering is easy: transform, zero (or scale) the bins you do not want, transform back. A low-pass filter keeps frequencies below a cutoff and removes the rest; a high-pass does the opposite; a band-pass keeps a window of frequencies.

Python Low-pass filtering with the FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The noise was spread over all frequencies up to 250 Hz, while the useful signal sits below 15 Hz. Throwing away everything above 20 Hz removes most of the noise power and leaves the tones untouched, so the error drops sharply.

A brick-wall cutoff like this is simple but not perfect: its sharp edge in frequency creates ringing in time (the Gibbs effect once more), and real-time filters use smoother designs from scipy.signal. Still, offline analysis is where the FFT filter shines.

Common slips. Forgetting to divide by N (or sum(window)) when quoting amplitudes. Mixing up angular frequency (rad/s) and hertz. Reading bins above fs/2 as real. Using fft with the wrong n when you call irfft: always pass n=len(original) so odd lengths round-trip correctly.

Why the FFT is fast

A direct DFT multiplies an N x N matrix by a vector: N**2 operations. The FFT notices that a DFT of size N can be built from two DFTs of size N/2 (the even and odd samples) plus N extra multiplications. Splitting again and again gives about N log2 N operations. For N = 1,000,000, that is roughly 20 million operations instead of a trillion.

Python Naive DFT versus FFT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A signal is sampled at 800 Hz. What is the highest frequency that can be represented?

    The Nyquist limit is half the sampling rate, 400 Hz. Higher frequencies alias to lower ones.
  2. 2. You record 4 seconds of a signal. What is the spacing between FFT bins?

    Bin spacing is fs/N = 1/T. With T = 4 s that is 0.25 Hz. Longer recordings give finer resolution.
  3. 3. What causes spectral leakage, and what reduces it?

    An FFT assumes the recording repeats, so a partial cycle creates a jump at the seam. A window that fades to zero at the edges removes that jump.
  4. 4. Why does rfft return about N/2 values for N real samples?

    For real input the spectrum is conjugate-symmetric, so the negative-frequency values carry no new information.
  5. 5. The FFT reduces the cost of a DFT from about N**2 to about

    Repeatedly splitting the transform into even and odd halves gives roughly N log2 N operations.

Summary

  • The Fourier transform turns a signal into a spectrum of frequencies; the DFT does the same for samples, and the FFT computes it in N log N steps.
  • Bin k sits at k * fs / N; resolution is 1/T, and only frequencies below fs/2 are valid.
  • Windowing (for example Hann) fights spectral leakage from partial cycles.
  • Filtering with the FFT means transform, zero or scale bins, inverse transform; use rfft/irfft for real signals.
  • Scale amplitudes by 2/N (or 2/sum(window)) to read true tone heights.

Next: Complex Numbers and Phasors.