Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 36 Ā· Fourier Transform

The DTFT, DFT and FFT

Understand the discrete-time Fourier transform, the DFT matrix and the fast Fourier transform. Build a DFT and a radix-2 FFT from scratch and compare with NumPy.

Computers work with samples, not continuous signals. Three related transforms handle sampled data. The discrete-time Fourier transform (DTFT) applies to an infinite sequence and produces a continuous, periodic spectrum. The discrete Fourier transform (DFT) applies to a finite block of N samples and produces N frequency values. The fast Fourier transform (FFT) is not a new transform: it is an efficient algorithm that computes the DFT in about N log N operations instead of N².

The DTFT

For a sequence x[n], the DTFT is X(ω) = Ī£ x[n] e^(-jωn), where ω is in radians per sample. It is periodic with period 2Ļ€, because e^(-j(ω+2Ļ€)n) = e^(-jωn) for integer n. Periodicity is a consequence of sampling: frequencies that differ by a multiple of the sampling rate look identical. The sampling theorem explores this idea in detail.

The DFT

If you only have N samples, evaluate the DTFT at N equally spaced frequencies ω_k = 2Ļ€k/N:

X[k] = Σ from n = 0 to N-1 of x[n] e^(-j2πkn/N), for k = 0 ... N-1.

The inverse is x[n] = (1/N) Σ X[k] e^(j2πkn/N). In matrix form, X = W x where W[k, n] = e^(-j2πkn/N) is the DFT matrix. Bin k corresponds to the frequency k · fs / N hertz, so the frequency resolution is fs / N. A longer record gives finer resolution.

Python A DFT built from its definition

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.

Why the FFT is fast

The DFT matrix has a lot of structure. Split x into even-indexed and odd-indexed samples. Each half has a DFT of length N/2, and the full transform combines them with N/2 multiplications by twiddle factors e^(-j2Ļ€k/N):

X[k] = E[k] + e^(-j2Ļ€k/N) O[k], and X[k + N/2] = E[k] - e^(-j2Ļ€k/N) O[k].

Applying the split recursively down to length 1 gives the radix-2 Cooley-Tukey FFT for lengths that are powers of two. The cost falls from N² to N log2 N: for N = 1,048,576 that is roughly 20 million operations instead of a trillion.

Python A recursive radix-2 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.

Using the FFT to read a frequency

Suppose you record 1 second at fs = 400 Hz containing a 50 Hz tone of amplitude 2 plus a 120 Hz tone of amplitude 0.5. Because both frequencies land exactly on bins, a scaled FFT gives their amplitudes directly. Divide by N/2 to convert bin magnitudes of a real signal into amplitudes (except at DC and Nyquist).

Python Finding tones and amplitudes

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.

rfft returns only the non-negative frequencies of a real signal, which is all you need because of conjugate symmetry.

Zero-padding and resolution

Padding a record with zeros before the FFT gives a smoother-looking spectrum (the DTFT is sampled more densely) but does not add real resolution. Resolution depends on the duration of actual data. Two tones closer than about fs/N apart cannot be separated no matter how much you pad. Windowing addresses a different problem: leakage when a tone does not fit the record exactly.

NumPy's FFT works for any length, not just powers of two, but lengths with small prime factors (like 1000 = 2³ · 5³) are much faster than large primes.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. A record of N = 2000 samples is taken at fs = 8000 Hz. What is the spacing between DFT bins?

    Bin spacing is fs / N = 8000 / 2000 = 4 Hz.
  2. 2. What is the main benefit of the FFT over the direct DFT?

    The FFT is an algorithm for the same DFT. It does not change the result, only the cost.
  3. 3. The DTFT of a sequence is periodic with period...

    Because e^(-jωn) repeats when ω increases by 2Ļ€ for integer n, the DTFT repeats every 2Ļ€ radians per sample.
  4. 4. Does zero-padding improve the ability to separate two close frequencies?

    Zero-padding samples the same DTFT more densely, which looks smoother but adds no information. Only a longer observation improves resolution.

Summary

  • The DTFT gives a 2Ļ€-periodic spectrum of a sequence; the DFT samples it at N points.
  • DFT bin k represents the frequency k Ā· fs / N, so resolution is fs / N.
  • The FFT splits the DFT into even and odd halves recursively, reaching N log N cost.
  • np.fft.rfft and rfftfreq are the everyday tools for real signals.

Next: The Laplace Transform