Lab 3.5 — FFT complexity and selected-bin trade-off

This lab strengthens the DSP foundation of the course without using notebooks. It is a deterministic script-driven lab that connects transform complexity to SDR measurement and FPGA design decisions.

Goal

Compare three analysis strategies:

Strategy	When it is useful	Engineering consequence
Direct DFT	Small reference vectors and teaching.	Simple but scales poorly.
Full FFT	Spectrum displays, measurement dashboards and unknown signals.	Efficient full-spectrum analysis, but requires memory, ordering and architecture choices.
Selected-bin detection	Known tones, pilots or narrow checks.	Can be cheaper than full FFT when only a few frequencies matter.

Run command

From the repository root:

python blocks/block_03_dsp_basics/python/lab_3_5_fft_complexity.py

Or run it as part of the reproducibility suite:

python tools/run_all_labs.py

Generated artifacts

Artifact	Purpose
docs/assets/lab35_dft_fft_complexity.png	Direct DFT vs FFT operation growth.
docs/assets/lab35_selected_bin_tradeoff.png	Full-spectrum FFT vs selected-bin detector.
docs/assets/lab35_fft_complexity_metrics.json	Machine-readable ratios for CI and reports.

Engineering questions

1. At what vector sizes does direct DFT become unreasonable for SDR analysis?
2. When is a full FFT justified instead of selected-bin detection?
3. How would the choice change for an FPGA streaming design?
4. What memory and latency trade-offs appear when moving from a script to RTL?

What to expect

DFT/FFT ratio at N=65536: 4096.0
FFT/selected-bin ratio at N=65536: 4.0

• The operation counts are normalised models: a direct DFT costs N^2, an FFT N/2 * log2(N), and evaluating K selected bins costs K * N.
• At N = 65 536 the direct DFT is 4096 times more work than the FFT (2N / log2 N). This ratio grows without bound, which is why nobody computes a full spectrum with a direct DFT.
• Four selected bins are still 4 times cheaper than the full FFT at that size. The break-even is K = log2(N) / 2 = 8 bins: above that, the full FFT wins even if you only need a few frequencies. That is exactly the Goertzel-versus-FFT decision you make for pilot or tone detection.

Exercises

1. Compute the DFT/FFT ratio for N = 64, 1024 and 65 536 by hand and check against the plot.
2. How many selected bins can you afford at N = 4096 before a full FFT becomes cheaper?
3. The counts ignore memory. A streaming FFT needs N complex words of buffer; a Goertzel detector needs two per bin. Which would you choose for detecting 3 known pilots in an FPGA with little block RAM, and why?

Answers (checked by running the lab script)

1. With the model counts N² and N/2·log2 N the ratio is 2N / log2 N: 21.3 at N = 64, 204.8 at 1024, 4096 at 65 536.
2. K selected bins cost K·N, the FFT N/2·log2 N, so the break-even is K = log2(N)/2 = 6 bins at N = 4096. Five or fewer bins are cheaper one by one.
3. Goertzel: three detectors need 6 words of state instead of a 4096-word buffer, and 3·N multiplies per block, less than one FFT. With little block RAM and few known frequencies it wins on both counts.

Report checklist

• Include both generated plots.
• Report the DFT/FFT complexity ratio at the largest tested N.
• Report the FFT/selected-bin ratio at the largest tested N.
• Explain which method you would use for:
• spectrum monitoring;
• single pilot detection;
• wideband unknown-signal search;
• FPGA resource-constrained implementation.

Bridge to later blocks

This lab feeds directly into:

• Block 05: FFT resource and streaming architecture decisions;
• Block 08: pilot and synchronization detection;
• Block 09: spectrum analysis of recorded IQ files;
• Block 11: measurement dashboard design.