Lab 15: Validating Your DFT on a Known Signal

Time: ~45 minutes | Prerequisites: Lab 14 | Hardware: Pico 2 (no microphone needed)

Looking right isn't being right

Echo waving welcome Your DFT produced convincing-looking spectra last lab. So would a DFT with a sign error in it, or one that's off by a factor of two. Today we find out which one you have — by testing it on signals whose answers we already know. Let's tune in.

What You'll Build

A test suite for your own DFT: seven signals with spectra you can work out on paper, checked automatically with an honest tolerance.

Learning Objectives

Predict a spectrum analytically before computing it
Choose a tolerance appropriate to the arithmetic available
Distinguish absolute from relative error
Apply validation-before-trust as a working habit
Debug by bisection when a test fails
Explain why single-precision floats limit what "zero" means here

Concepts Introduced

ID	Concept
344	Ground Truth
345	Known Signal Test
346	Validation Before Trust
347	Numerical Tolerance
348	Absolute Error
349	Relative Error
350	Bin Exact Frequency
351	Expected Peak
352	Debugging By Bisection
353	Test Signal Design

Background

Why bother, when it looked fine?

Because in Lab 21 you'll point this DFT at a microphone. If the spectrum looks wrong then, the suspects are: the mic wiring, the sample format, the DC offset, the DFT, the magnitude calculation, or the display. Six candidates and no way to choose.

Unless you've already proven the DFT correct. Then it's five.

Every subsystem in this course gets tested against a known answer before it's trusted with an unknown one. The previous version of this kit skipped this step, and students who got garbage had no way to find out why.

Signals with spectra you can predict

Signal	Expected spectrum
all zeros	every bin 0
constant `D`	bin 0 = `D·N`, rest 0
sine, amplitude `A`, at bin `k`	bin `k` = `A·N/2` (mirrored at `N−k`)
impulse at sample 0	every bin = 1.0, perfectly flat
alternating +1/−1	bin `N/2` = `N`

The impulse is the loveliest of these: one sample of 1.0 and the rest zeros produces a completely flat spectrum. An instantaneous click contains every frequency equally — which is why a clap is a decent way to test a room's acoustics.

Where `A·N/2` comes from

A real sine splits its energy between its bin and the mirror bin. Each half gets A·N/2, so they sum to A·N. The program demonstrates this explicitly.

How close to zero is zero?

Echo thinking Bins that should be exactly 0 come out around 1×10⁻⁴ on this board. Not a bug — MicroPython here uses single-precision floats (check: repr(1/3) gives 0.3333333, only 7 digits). Our angle 2πkt/N climbs to about 390 radians for the top bins, and a float32 can't pin a number that large down better than ~4×10⁻⁵ radians. So cos() is inaccurate before it even runs.

Procedure

Step 1 — Predict before you run

Fill this in first, using the table above. N = 64.

Signal	Which bin peaks?	What value?
constant 0.5
sine amplitude 1.0 at bin 3
sine amplitude 0.25 at bin 7
impulse at sample 0

Step 2 — Run the suite

Open 15-validating.py and run it:

# Lab 15: Validating Your DFT on a Known Signal
#
# You wrote a DFT last lab and the output LOOKED right. That is not the same
# as being right.
#
# This lab builds signals whose spectra we can predict on paper, then checks
# the code against those predictions. If the DFT ever disagrees with theory,
# we find out here -- in a controlled test with a known answer -- and not in
# Lab 21 with a microphone attached and four things that could be at fault.
#
# This habit has a name: VALIDATE BEFORE YOU TRUST.

import config
import math

RATE = config.SAMPLE_RATE
N = 64
BIN = RATE / N

# How close is "equal"? This is a real decision, not a formality.
#
# MicroPython on this board uses SINGLE-precision floats -- about 7 digits.
# Worse, our angle 2*pi*k*t/N reaches ~390 radians for the highest bins, and
# a float32 can only pin that down to about 4e-5 radians. So bins that should
# be exactly zero come out around 1e-4 instead.
#
# A tolerance of 1e-6 would therefore fail every time, not because the DFT is
# wrong but because the tolerance is a fantasy. We express it RELATIVE to the
# size of the signal instead.
REL_TOL = 1e-3            # 0.1% of the largest expected value


def dft(signal):
    n = len(signal)
    real, imag = [], []
    for k in range(n):
        re = im = 0.0
        for t in range(n):
            angle = 2 * math.pi * k * t / n
            re += signal[t] * math.cos(angle)
            im -= signal[t] * math.sin(angle)
        real.append(re)
        imag.append(im)
    return real, imag


def magnitudes(real, imag):
    return [math.sqrt(real[k] ** 2 + imag[k] ** 2) for k in range(len(real))]


def sine(freq, amp=1.0, phase=0.0, n=N):
    return [amp * math.sin(2 * math.pi * freq * (i / RATE) + phase)
            for i in range(n)]


# =========================================================================
# The test cases. Each one has a spectrum we can work out on paper.
# =========================================================================
#
#  signal                     expected spectrum
#  -----------------------    -------------------------------------------
#  all zeros                  every bin 0
#  constant D                 bin 0 = D*N, everything else 0
#  sine, amplitude A, bin k   bin k = A*N/2  (and mirrored at N-k)
#  impulse at sample 0        EVERY bin = 1.0  (perfectly flat)
#  alternating +1/-1          bin N/2 = N, everything else 0

tests = []

tests.append((
    "silence",
    [0.0] * N,
    "every bin zero",
    lambda m: all(v < REL_TOL for v in m),
))

D = 0.5
tests.append((
    "constant %.1f" % D,
    [D] * N,
    "bin 0 = %.1f, rest zero" % (D * N),
    lambda m: abs(m[0] - D * N) < REL_TOL * D * N
              and all(v < REL_TOL * D * N for v in m[1:]),
))

A, K = 1.0, 3
tests.append((
    "sine amp %.1f at bin %d" % (A, K),
    sine(K * BIN, amp=A),
    "bin %d = %.1f" % (K, A * N / 2),
    lambda m: abs(m[K] - A * N / 2) < REL_TOL * A * N / 2,
))

A2, K2 = 0.25, 7
tests.append((
    "sine amp %.2f at bin %d" % (A2, K2),
    sine(K2 * BIN, amp=A2),
    "bin %d = %.1f" % (K2, A2 * N / 2),
    lambda m: abs(m[K2] - A2 * N / 2) < REL_TOL * A2 * N / 2,
))

tests.append((
    "phase-shifted sine",
    sine(K * BIN, phase=1.234),
    "bin %d still = %.1f (phase must not matter)" % (K, N / 2),
    lambda m: abs(m[K] - N / 2) < REL_TOL * N / 2,
))

impulse = [0.0] * N
impulse[0] = 1.0
tests.append((
    "impulse at sample 0",
    impulse,
    "every bin = 1.0 (flat spectrum)",
    lambda m: all(abs(v - 1.0) < REL_TOL for v in m),
))

alt = [1.0 if i % 2 == 0 else -1.0 for i in range(N)]
tests.append((
    "alternating +1/-1",
    alt,
    "bin %d = %d (Nyquist)" % (N // 2, N),
    lambda m: abs(m[N // 2] - N) < REL_TOL * N,
))

# =========================================================================
# Run them
# =========================================================================
print("Validating the DFT against hand-computed answers")
print("N = %d, bin width = %.0f Hz, relative tolerance = %g" % (N, BIN, REL_TOL))
print()
print("%-26s %-34s %s" % ("test signal", "expected", "result"))
print("-" * 74)

passed = failed = 0
for name, signal, expectation, check in tests:
    mags = magnitudes(*dft(signal))
    ok = check(mags)
    print("%-26s %-34s %s" % (name, expectation, "PASS" if ok else "*** FAIL ***"))
    if ok:
        passed += 1
    else:
        failed += 1
        # A failure should tell you WHERE to look, not just that it happened.
        top = max(range(len(mags)), key=lambda k: mags[k])
        print("      -> largest bin was %d (%.0f Hz) at magnitude %.4f"
              % (top, top * BIN, mags[top]))

print("-" * 74)
print("%d passed, %d failed" % (passed, failed))
print()

if failed == 0:
    print("Every prediction confirmed. The DFT is trustworthy -- so when")
    print("something looks wrong in a later lab, the DFT is not the suspect.")
else:
    print("Something disagrees with theory. Debug by BISECTION: start with")
    print("the simplest failing case and shrink N until you can check the")
    print("arithmetic by hand.")

# =========================================================================
# Where the expected numbers come from
# =========================================================================
print()
print("=== How close to zero is zero? ===")
zeros = magnitudes(*dft([0.5] * N))
worst = max(zeros[1:])
print("For a constant signal every bin above 0 should be EXACTLY zero.")
print("Largest one actually measured: %.3e" % worst)
print()
print("That is not a bug in the DFT. This board uses single-precision")
print("floats (repr(1/3) = %s), and our angle 2*pi*k*t/N climbs to about" % repr(1/3))
print("%.0f radians for the top bins. float32 cannot hold a number that" % (2 * math.pi * (N-1) * (N-1) / N))
print("large to better than ~1e-4 radians, so cos() starts out inaccurate")
print("before it even runs.")
print()
print("Two lessons:")
print("  1. A tolerance must match the arithmetic you actually have.")
print("  2. Recomputing big angles is wasteful AND imprecise -- which is")
print("     exactly why Lab 18 precomputes a small table of twiddle factors")
print("     instead of calling cos() half a million times.")

print()
print("=== Why a sine of amplitude A peaks at A*N/2 ===")
print("A real sine splits its energy between the positive frequency (bin k)")
print("and its mirror (bin N-k). Each half gets A*N/2.")
print()
mags = magnitudes(*dft(sine(K * BIN)))
print("amplitude 1.0, N = %d  ->  expected %.1f" % (N, N / 2))
print("  bin %2d  = %.4f" % (K, mags[K]))
print("  bin %2d  = %.4f   <- the mirror" % (N - K, mags[N - K]))
print("  total   = %.4f   = A * N" % (mags[K] + mags[N - K]))

test signal                expected                           result
--------------------------------------------------------------------------
silence                    every bin zero                     PASS
constant 0.5               bin 0 = 32.0, rest zero            PASS
sine amp 1.0 at bin 3      bin 3 = 32.0                       PASS
sine amp 0.25 at bin 7     bin 7 = 8.0                        PASS
phase-shifted sine         bin 3 still = 32.0                 PASS
impulse at sample 0        every bin = 1.0 (flat spectrum)    PASS
alternating +1/-1          bin 32 = 64 (Nyquist)              PASS
--------------------------------------------------------------------------
7 passed, 0 failed

Step 3 — Understand the tolerance

The suite uses a relative tolerance — 0.1% of the expected value — not an absolute one.

That's a deliberate choice. An absolute tolerance of 1e-6 fails every time on this hardware, not because the DFT is wrong but because the tolerance is a fantasy about precision we don't have. A tolerance must match the arithmetic you actually own.

A test that fails for the wrong reason is worse than no test

Echo warning If your suite cries wolf on every run, you'll start ignoring it — and then it won't catch the real bug when it appears. Getting the tolerance right is part of writing the test, not an afterthought.

Step 4 — Break it deliberately

Introduce a bug and confirm the suite catches it. Change the DFT's sign:

im += signal[t] * math.sin(angle)     # was -=

Which tests fail? Which still pass? Now try a scale error — divide re and im by 2. Notice that the impulse test still passes while the sine tests fail. Test suites have blind spots, and knowing yours is part of the job.

Step 5 — Debug by bisection

When something fails, don't stare at 64 bins. Shrink the problem:

Drop N to 8 — small enough to check by hand
Use the simplest failing signal
Print intermediate values inside the loop
Compare one bin against arithmetic you do yourself

Expected Output

All 7 tests pass, then the precision discussion, then a demonstration that bins 3 and 61 each hold 32.0 and sum to 64.0 = A·N.

Troubleshooting

Symptom	Likely cause	Fix
Everything fails	Tolerance too tight	Use relative, not absolute
Only sine tests fail	Scale or sign error in the DFT	Check the `A·N/2` derivation
Impulse test fails	Impulse not at index 0	A shifted impulse changes phase, not magnitude
Nyquist test fails	Off-by-one on `N/2`	With N = 64 the Nyquist bin is 32
Results differ run to run	Not possible here — it's deterministic	Something else changed; check your edits

Challenges

Add a test. Two sines at different bins and amplitudes. Predict both peaks, then check.
Find the limit. Lower REL_TOL until tests start failing. What's the tightest tolerance this hardware supports?
Parseval's theorem. The energy in the time domain equals the energy in the frequency domain (with a scale factor). Work out the factor and add it as a test — it's a strong whole-transform check.

Check Your Understanding

Why validate against a known signal before using a microphone?
What spectrum does an impulse produce, and why?
A sine of amplitude 1.0 with N = 128 — what's the peak bin value?
Why is a relative tolerance better than an absolute one here?
Describe debugging by bisection in your own words.

Now you can trust it

Echo celebrating Seven predictions, seven confirmations. Your DFT is correct — and you can prove it, which is a different and better thing than believing it. Next lab: find out whether it's fast enough. (It is not. Spectacularly.)

Next: Lab 16: Your DFT Is Too Slow | Previous: Lab 14