Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 38 ยท Signal Processing

The Fast Fourier Transform

Use scipy.fft to find the frequencies hidden in a signal: rfft and rfftfreq, amplitude scaling, aliasing, windowing, zero padding, the DCT and why the FFT is fast.

A sound, a vibration, a heartbeat or a stock price is a signal: numbers measured over time. Often the most useful question is not what is the value at each moment but which rhythms is it made of. A chord is three notes; a washing machine hums at its motor speed; a daily temperature curve has a 24-hour cycle. The Fourier transform takes a signal and tells you how much of each frequency it contains.

The Fast Fourier Transform (FFT) is the algorithm that makes this practical: it computes the transform of N samples in roughly N log N steps instead of Nยฒ. scipy.fft is the modern module for it. This lesson shows how to read a spectrum correctly (frequency axis, amplitude scaling, aliasing), how to tame spectral leakage with windows, and what zero padding and the discrete cosine transform are good for. The next lesson, Filter Design and Filtering Signals, uses the same ideas to remove unwanted frequencies.

flowchart LR
    S["signal in time<br/>N samples at rate fs"] -->|"rfft"| C["N/2+1 complex numbers"]
    C --> M["abs: how much of each frequency"]
    C --> P["angle: phase of each frequency"]
    F["rfftfreq(N, 1/fs)"] --> X["frequency axis in Hz<br/>0 up to fs/2"]
    M --> PL["spectrum plot"]
    X --> PL

The FFT output has no units of its own. The frequency axis comes from rfftfreq, and the magnitude must be scaled by the number of samples.

Your first spectrum

Create a signal made of two sine waves, 5 Hz with amplitude 2 and 12 Hz with amplitude 0.8, sampled 100 times per second for 2 seconds. For a real-valued signal, use rfft: it returns only the non-negative frequencies (the negative half is a mirror image), which is half the work and half the output. rfftfreq(n, d) gives the matching frequencies in Hz, where d is the sample spacing in seconds.

To convert magnitudes to amplitudes, divide by N and double everything except the zero-frequency (and, for even N, the Nyquist) entry, because the mirrored half was dropped.

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 output lists three peaks: 0 Hz (the constant offset of 1), 5 Hz (amplitude 2) and 12 Hz (amplitude 0.8). The jumble in the time plot becomes three clean spikes in the spectrum. The spacing between bins, fs / N, is the frequency resolution: to separate two close tones you need a longer recording, not a faster one.

Two other functions complete the picture. ifft/irfft go back from a spectrum to the signal, and np.angle(spectrum) gives the phase of each component. Together magnitude and phase contain exactly the same information as the original samples.

Python The round trip loses nothing

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.

Sampling rate, Nyquist and aliasing

A signal sampled fs times per second can only represent frequencies up to fs / 2, the Nyquist frequency. Anything faster does not disappear: it gets folded back into the valid range and masquerades as a lower frequency. This is aliasing, the reason wagon wheels appear to spin backwards in films. It cannot be repaired after sampling, so real instruments filter out frequencies above Nyquist before digitizing.

Python A 70 Hz tone sampled at 100 Hz

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 70 Hz tone shows up at 30 Hz, the mirror image fs - 70. Always pick a sampling rate at least a little more than twice the highest frequency you care about.

Spectral leakage and windows

The FFT quietly assumes that your recording repeats forever. If the recording contains a whole number of cycles, the end joins the start smoothly. If not, there is a jump at the seam, which smears the energy of a single tone across many bins. This is spectral leakage.

The remedy is a window: multiply the signal by a smooth function that fades to zero at both ends before the transform. The scipy.signal.windows module provides Hann, Hamming, Blackman and many more. The Hann window is a good default. Windowing lowers the overall amplitude (scale by the window's sum, as the example does) and slightly widens the main peak, but the far-away leakage drops dramatically.

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.

Neither peak reads exactly 1.0, because 10.3 Hz falls between two bins. On a logarithmic axis the difference in leakage is obvious: the unwindowed spectrum has a slowly decaying skirt of leakage, the Hann spectrum falls away steeply. The price is a slightly wider main peak, so for two tones very close together a different window or a longer recording may be needed.

Zero padding

Calling rfft(x, n=N_bigger) pads the signal with zeros up to N_bigger samples. This does not add information or improve true resolution (two tones closer than about fs / N_original stay unresolved). What it does is interpolate the spectrum: the bins get closer together, so a peak position can be read off more precisely and the plot looks smoother. A side benefit: lengths that factor into small primes are faster, and fft.next_fast_len(n) tells you the next good size.

Python Reading a peak position more precisely

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 discrete cosine transform

The DCT (fft.dct, fft.idct) is a cousin of the FFT that uses only cosines and returns real numbers. For smooth data most of the energy lands in the first few coefficients, which makes it the basis of JPEG image compression and of many audio codecs: keep the large coefficients, drop the small ones. Use norm="ortho" to get an energy-preserving transform.

Python Compressing a smooth signal with the DCT

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.

Sixteen numbers, 6% of the data, rebuild the signal almost perfectly. Noise or sharp jumps spread energy across many coefficients, which is why photos with fine texture compress worse than smooth gradients.

Multidimensional transforms: fft2, fftn and dctn

Everything so far transformed one-dimensional signals. The same ideas extend to images and volumes: fft.fft2 transforms along the two axes of a 2D array, fft.fftn along any number of axes, and fft.dctn / fft.idctn are the n-dimensional versions of the cosine transform. They all take an axes argument to restrict which axes are transformed, s to zero pad, and norm.

A 2D transform of an image tells you how much of each spatial frequency it contains: slow brightness changes sit near the corner or centre, fine detail and sharp edges far from it. Image compression such as JPEG applies the 2D DCT to 8 by 8 blocks, and keeps only the largest coefficients. The next example builds a smooth picture with a few sharp edges, transforms it with dctn, keeps only the 6 percent of coefficients with the largest absolute value, and rebuilds it with idctn.

Python 2D DCT compression with dctn and idctn

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 reconstruction from a handful of coefficients is recognisable and the energy count shows that norm="ortho" keeps total energy (Parseval's theorem). In the third panel fftshift moves the zero-frequency term to the centre, which puts the low frequencies in the middle and lets you see how the energy spreads along the horizontal and vertical directions of the square's straight edges. For real-valued data rfft2 and rfftn compute only the non-redundant half and are about twice as fast.

Inverse FFT: filtering a signal and getting it back

The forward transform is only half of the story. Because ifft inverts fft, you can edit the spectrum and transform back: zero the bins you do not want and the signal returns without them. This is the simplest possible filter. For real signals use rfft and irfft, which keep only the non-negative frequencies and return real output.

Python A brick-wall low-pass filter with rfft and irfft

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 hum disappears and the 5 Hz wave comes back with an error of zero at the printed precision, because both tones fit a whole number of cycles into the one-second window. Passing n=len(t) to irfft tells it the original length, which matters for odd lengths. A sharp cut-off like this one can ring near the edges of the signal; for production filters use the designs in Filtering.

Why the FFT is fast

The straightforward discrete Fourier transform multiplies the signal by an N x N matrix of complex exponentials: about Nยฒ operations. The FFT exploits symmetries in that matrix by splitting the problem into smaller transforms again and again, which takes about N logโ‚‚ N operations. For one million samples that is the difference between 10ยนยฒ and 2ยท10โท steps.

Python A naive DFT against 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 FFT is fastest when N has only small prime factors, such as powers of two; an awkward length like a large prime can be much slower. fft.next_fast_len and zero padding avoid that trap.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A signal has 500 samples recorded at 250 samples per second. What is the spacing between FFT bins?

    The bin spacing is fs / N = 250 / 500 = 0.5 Hz. A longer recording gives finer resolution.
  2. 2. A 70 Hz tone is sampled at 100 Hz. Where does it appear in the spectrum?

    The Nyquist frequency is 50 Hz. A tone above it folds back to fs - f = 30 Hz and cannot be told apart from a real 30 Hz tone.
  3. 3. Why apply a Hann window before the FFT?

    The FFT assumes the data repeats. A window fades the edges so the seam does not create artificial broadband energy.
  4. 4. What does zero padding (rfft(x, n=larger)) accomplish?

    Padding does not add information, so true resolution is unchanged, but the closer bins make peaks easier to locate and plot.
  5. 5. Roughly how many operations does the FFT need for N samples?

    The FFT needs about N log2 N operations, against N squared for the direct matrix method.

Summary

  • fft.rfft transforms a real signal into frequency components; rfftfreq(n, d) supplies the frequency axis and the bin spacing is fs / N.
  • Divide magnitudes by N (and double all but the end bins) to read amplitudes; angle gives phases; irfft reverses the transform.
  • Frequencies above the Nyquist limit fs / 2 alias onto lower ones, so sample fast enough.
  • Windows such as Hann reduce spectral leakage; zero padding interpolates the spectrum but cannot add real resolution.
  • The DCT concentrates the energy of smooth data in few coefficients, which is the basis of compression.
  • The FFT takes about N log N steps instead of Nยฒ, and it is fastest for lengths with small prime factors.

Next up: remove unwanted frequencies in Filter Design and Filtering Signals.