Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 ยท DFT and FFT

The DFT from Scratch

Implement the discrete Fourier transform with loops and as a matrix, learn frequency bins, amplitude scaling and the inverse DFT, and check everything against NumPy's FFT.

The discrete Fourier transform (DFT) takes N samples and returns N complex numbers that say how much of each of N evenly spaced frequencies the signal contains. It is the computer's version of the Fourier series. In this lesson you build it in a few lines, learn how to read the result, and prove it is correct by inverting it.

Definition

For a sequence x[0], ..., x[N-1]:

X[k] = sum for n = 0..N-1 of x[n] * e^(-j 2 pi k n / N), for k = 0, 1, ..., N-1

and the inverse is

x[n] = (1/N) * sum for k = 0..N-1 of X[k] * e^(+j 2 pi k n / N).

Read the first formula as "correlate the signal with the complex exponential that makes k full turns across the record." Every X[k] is one such correlation, a complex number carrying the amplitude and phase of that frequency component.

flowchart LR
    A["N samples x[n]"] -->|"DFT"| B["N complex values X[k]"]
    B -->|"inverse DFT"| A

The DFT loses no information: N numbers in, N numbers out, and the inverse returns the original.

A direct implementation

Two nested loops follow the formula word for word. The cost is N multiplications for each of N outputs, so N^2 operations in total. That is fine for a few hundred samples and painful for millions, which is why the FFT exists.

Python DFT with loops, compared with numpy.fft.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.

X[0] is the sum of all samples (the DC term). The rest of the vector describes the oscillating parts.

The DFT as a matrix

Collect the exponentials into the DFT matrix W with entries W[k, n] = e^(-j 2 pi k n / N). Then the whole transform is one matrix-vector product X = W x. The inverse matrix is conj(W) / N. Seeing the DFT as linear algebra explains its properties and gives a loop-free implementation.

Python The DFT matrix and the inverse DFT

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.

Reading the output: bins and scaling

The index k is a frequency bin. Bin k corresponds to the frequency

f_k = k * fs / N hertz,

and the spacing between neighbouring bins, the frequency resolution, is fs / N. To get finer resolution you need a longer record (N larger), not just a faster sampling rate.

For a real signal the second half of the output mirrors the first: X[N-k] = conj(X[k]). Bins above N/2 stand for the negative frequencies. So you only need bins 0 ... N/2, which is what np.fft.rfft returns.

To read amplitudes, scale: a sinusoid of amplitude A that fits a whole number of periods gives |X[k]| = A*N/2 at its bin. So amplitude = 2*|X[k]|/N (and |X[0]|/N for the DC value).

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 three components (DC 1.5, 50 Hz with amplitude 2.0, 120 Hz with amplitude 0.7) are found exactly. The phases are reported for a cosine reference: the 50 Hz sine appears at -pi/2 and the 120 Hz component at 0.6.

Which frequencies does bin k represent?

For N = 8 and fs = 8000, bins 0..7 stand for 0, 1000, 2000, 3000, -4000, -3000, -2000, -1000 Hz (the Nyquist bin is reported as -4000, though +4000 is the same frequency). The negative frequencies come last. np.fft.fftfreq returns them in that order, and np.fft.fftshift rearranges to put 0 in the middle for plotting.

Python Bin frequencies and fftshift

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.

Energy is preserved

Parseval's theorem says the energy is the same in both domains: sum |x[n]|^2 = (1/N) * sum |X[k]|^2. It is a useful sanity check for any spectrum code, and it explains why the squared magnitude |X[k]|^2 is called the power spectrum.

Python Parseval check

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 ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. x has N = 500 samples recorded at fs = 2000 Hz. What is the spacing between DFT bins?

    fs / N = 2000 / 500 = 4 Hz.
  2. 2. What does X[0] represent?

    At k = 0 every exponential equals 1, so X[0] is the plain sum of the samples.
  3. 3. How many operations does the direct DFT of N samples need?

    N outputs, each a sum of N products.
  4. 4. For a real signal with N = 16, bin 13 is the complex conjugate of which bin?

    X[N-k] = conj(X[k]), so X[13] = conj(X[3]).

Summary

  • X[k] = sum x[n] e^(-j 2 pi k n / N); the inverse divides by N and flips the sign of the exponent.
  • Bin k is the frequency k*fs/N; the resolution is fs/N.
  • For real signals, bins above N/2 mirror the lower half; use rfft.
  • A sinusoid of amplitude A gives |X[k]| = A N / 2.
  • The direct DFT costs N^2, and the transform preserves energy (Parseval).

Next: The FFT Algorithm