Project 4: The Discrete Fourier Transform (The Magic Eye)

Build a DFT analyzer that reveals the frequency content of signals.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate Weekend
Main Language C
Alternative Languages Python, Rust, C++
Knowledge Area Frequency analysis
Tools Plotting tool, test signals from P01
Main Book “Understanding Digital Signal Processing” by Richard G. Lyons

What you’ll build: A tool that computes the DFT of a signal block and outputs magnitude spectra.

Why it teaches DSP: The DFT is the gateway to the frequency domain. It changes how you think about signals.

Core challenges you’ll face:

  • Understanding complex numbers as rotating vectors
  • Managing DFT resolution and windowing
  • Interpreting leakage and spectral artifacts

Real World Outcome

You will input a signal and get a frequency plot that shows peaks at expected frequencies. A 440Hz sine should show a dominant peak at 440Hz.

Example Output:

$ ./dft_analyzer --input output.wav --size 2048 --output spectrum.csv
Computed DFT for 2048 samples
Wrote magnitude spectrum to spectrum.csv

Verification steps:

  • Plot the spectrum and find dominant peaks
  • Compare expected vs observed frequencies

The Core Question You’re Answering

“How can a time signal be represented as a sum of rotating frequency components?”

The DFT is not a trick. It is a change of basis that reveals the hidden structure of a signal.

Concepts You Must Understand First

Stop and research these before coding:

  1. Complex numbers as rotation
    • Why does a complex exponential represent a rotating vector?
    • Book Reference: “Understanding Digital Signal Processing” by Richard G. Lyons, Ch. 3
  2. Frequency bins and resolution
    • How does DFT size affect frequency spacing?
    • Book Reference: “The Scientist and Engineer’s Guide to DSP” by Steven W. Smith, Ch. 8
  3. Spectral leakage
    • Why do non-integer frequencies smear across bins?
    • Book Reference: “Understanding Digital Signal Processing” by Richard G. Lyons, Ch. 9

Questions to Guide Your Design

  1. Windowing
    • Will you apply a window function before the DFT?
    • How will you choose between rectangular, Hann, or Hamming?
  2. Output format
    • Will you output magnitude only, or magnitude and phase?
    • How will you scale the output to be human-readable?

Thinking Exercise

Bin Mapping

Assume a 1024-sample DFT at a 1024Hz sample rate.

  • What frequency does bin 0 represent?
  • What frequency does bin 1 represent?
  • What frequency does bin 256 represent?

Questions while working:

  • How many Hz per bin?
  • What happens if the signal frequency is 100.5Hz?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is the DFT doing mathematically?”
  2. “Why do we need complex numbers in the DFT?”
  3. “What is spectral leakage and how do windows reduce it?”
  4. “How do you determine the frequency resolution of a DFT?”
  5. “What is the difference between magnitude and phase?”

Hints in Layers

Hint 1: Starting Point Think of the DFT as a sum of correlations with sine and cosine waves.

Hint 2: Next Level For each bin, compute the dot product against a rotating basis vector.

Hint 3: Technical Details Use precomputed sine and cosine values to reduce repeated work.

Hint 4: Tools/Debugging Test with a single-tone signal and check that only one bin is dominant.

Books That Will Help

Topic Book Chapter
DFT fundamentals “Understanding Digital Signal Processing” by Richard G. Lyons Ch. 3
Frequency resolution “The Scientist and Engineer’s Guide to DSP” by Steven W. Smith Ch. 8
Windowing and leakage “Understanding Digital Signal Processing” by Richard G. Lyons Ch. 9

Implementation Hints

  • Start with small DFT sizes to validate correctness.
  • Normalize magnitudes so that pure tones are easy to recognize.
  • Provide a simple CSV output so any plotting tool can display it.

Learning Milestones

  1. First milestone: You can detect the dominant frequency of a tone.
  2. Second milestone: You can explain leakage and its causes.
  3. Final milestone: You can interpret magnitude spectra for multi-tone signals.