Skip to content

Lab 13: Correlation — Does My Signal Contain This Note?

Time: ~60 minutes | Prerequisites: Lab 12 | Hardware: Pico 2 (no microphone needed)

This is the one. Take your time.

Echo waving welcome Every remaining lab in this course stands on the idea in this file. The good news: it's one multiplication and one addition. Really. If you understand this lab, the FFT stops being magic and becomes bookkeeping. Time to transform!

What You'll Build

A frequency detector. Give it a signal and a candidate frequency, and it answers: is that frequency in here? You'll build it, watch it fail on a phase shift, and then fix it.

Learning Objectives

  • Explain how multiply-and-sum detects a frequency
  • Describe why non-matching frequencies cancel to zero
  • Demonstrate that a sine-only detector is blind to a phase-shifted signal
  • Combine sine and cosine correlations into a phase-independent magnitude
  • Connect correlation to the dot product

Concepts Introduced

ID Concept
320 Correlation
321 Multiply And Sum
322 Dot Product
323 Test Frequency
324 Similarity Measure
325 Orthogonal Functions
326 In Phase Component
327 Quadrature Component
328 Phase Independence
329 Correlation Magnitude
330 Basis Function
331 Projection Onto Basis

Background

The whole idea, in one sentence

Multiply your signal by a test wave, add up the results, and see whether the total is big.

That's it. Here it is in code:

1
2
3
total = 0
for i in range(N):
    total += signal[i] * test_wave[i]

Why it works

Think about what happens sample by sample.

When the frequencies match, the two waves rise and fall together. Positive times positive gives positive. Negative times negative also gives positive. Every product pushes the total the same direction, so it grows large.

When they don't match, the waves drift in and out of step. Sometimes both are positive, sometimes one is negative. The products land above and below zero at random and cancel each other out.

A large total means "yes, that frequency is in here." Near zero means "no."

You already know this as the dot product

Echo thinking Multiply matching elements, add up the results — that's the dot product from vector maths, the thing that measures how much two vectors point the same way. Here the "vectors" have 256 dimensions and each one is a wave. Two waves of different frequencies are orthogonal — mathematically perpendicular. Their dot product is zero, which is exactly why non-matching frequencies vanish.

Procedure

Step 1 — Play the guessing game

Open 13-correlation.py and run it:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# Lab 13: Correlation -- Does My Signal Contain This Note?
#
# THIS IS THE BIG ONE. Everything else in this course is built on the idea in
# this file, so take your time with it.
#
# The question: given a signal, how do we find out whether a particular
# frequency is hiding inside it?
#
# The trick: multiply the signal by a test wave and add up the results.
#
#   - If they match, positive parts line up with positive parts and the sum
#     grows large.
#   - If they do not match, the products land randomly above and below zero
#     and cancel out to nearly nothing.
#
# That is it. That is the whole idea behind the Fourier transform.

import config
import math

RATE = config.SAMPLE_RATE      # 12800 Hz
N = 256
BIN = RATE / N                 # 50 Hz -- frequencies that fit whole cycles


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)]


def cosine(freq, amp=1.0, n=N):
    return [amp * math.cos(2 * math.pi * freq * (i / RATE)) for i in range(n)]


def correlate(signal, reference):
    """Multiply point by point, then add it all up. That is correlation."""
    total = 0.0
    for i in range(len(signal)):
        total += signal[i] * reference[i]
    return total / len(signal)     # divide by N so the scale is comparable


# =========================================================================
# PART 1 -- a mystery signal, and a guessing game
# =========================================================================
MYSTERY_FREQ = 6 * BIN          # 300 Hz. Pretend you do not know this.
mystery = sine(MYSTERY_FREQ)

print("=== PART 1: hunting for a hidden frequency ===")
print("A mystery signal is hiding one tone. Let's test some candidates.")
print()
print("%10s %14s" % ("candidate", "correlation"))
for k in range(1, 11):
    test_freq = k * BIN
    score = correlate(mystery, sine(test_freq))
    bar = "#" * int(abs(score) * 100)
    print("%8.0f Hz %14.4f  %s" % (test_freq, score, bar))

print()
print("One candidate scores far above the rest. That is the hidden tone:")
print("%.0f Hz." % MYSTERY_FREQ)

# =========================================================================
# PART 2 -- WHY it works: look inside the sum
# =========================================================================
print()
print("=== PART 2: why the sum grows or cancels ===")
print()
print("Sampling products from across the WHOLE window (not just the start --")
print("cancellation is something that happens over the full length).")
print()

step = N // 12

print("MATCHING (300 Hz signal x 300 Hz test):")
match = sine(MYSTERY_FREQ)
prods = [mystery[i] * match[i] for i in range(0, N, step)]
print("  ", " ".join("%+.2f" % p for p in prods))
neg = sum(1 for p in prods if p < 0)
print("   %d of %d are negative -- almost all pull the SAME way, so the"
      % (neg, len(prods)))
print("   total grows. (A squared sine is never negative.)")

print()
print("NOT MATCHING (300 Hz signal x 150 Hz test):")
wrong = sine(3 * BIN)
prods = [mystery[i] * wrong[i] for i in range(0, N, step)]
print("  ", " ".join("%+.2f" % p for p in prods))
neg = sum(1 for p in prods if p < 0)
print("   %d of %d are negative -- they fight each other, and the total"
      % (neg, len(prods)))
print("   collapses to zero.")

# =========================================================================
# PART 3 -- the trap: phase
# =========================================================================
print()
print("=== PART 3: the trap ===")
print("Same 300 Hz tone, but shifted a quarter cycle (a cosine now).")
shifted = sine(MYSTERY_FREQ, phase=math.pi / 2)
score = correlate(shifted, sine(MYSTERY_FREQ))
print()
print("correlation with a SINE test wave: %.6f" % score)
print()
print("Nearly zero! The tone is definitely there, but our detector says no.")
print("A sine test wave is blind to a signal that happens to be a cosine.")

# =========================================================================
# PART 4 -- the fix: test with sine AND cosine
# =========================================================================
print()
print("=== PART 4: the fix -- use two test waves ===")
print("Test with a sine AND a cosine, then combine them like the sides of a")
print("right triangle:   magnitude = sqrt(sine_score^2 + cosine_score^2)")
print()
print("%22s %10s %10s %12s" % ("signal", "sin", "cos", "magnitude"))

for label, sig in (("300 Hz sine", mystery),
                   ("300 Hz cosine", shifted),
                   ("300 Hz, phase 0.7", sine(MYSTERY_FREQ, phase=0.7)),
                   ("300 Hz, phase 2.5", sine(MYSTERY_FREQ, phase=2.5)),
                   ("150 Hz (wrong)", sine(3 * BIN))):
    s = correlate(sig, sine(MYSTERY_FREQ))
    c = correlate(sig, cosine(MYSTERY_FREQ))
    mag = math.sqrt(s * s + c * c)
    print("%22s %10.4f %10.4f %12.4f" % (label, s, c, mag))

print()
print("The sin and cos scores move around as the phase changes -- but the")
print("MAGNITUDE stays put. We now have a detector that answers")
print("'is this frequency present?' no matter when the wave started.")
print()
print("Next lab: run this test at EVERY frequency, and you have a spectrum.")

Part 1 hides a tone in a signal and tests ten candidates:

1
2
3
4
5
6
 candidate    correlation
      50 Hz        -0.0000
     100 Hz        -0.0000
     250 Hz         0.0000
     300 Hz         0.5000  ##################################################
     350 Hz         0.0000

One candidate towers over the rest. You just found a hidden frequency using nothing but multiplication and addition.

Step 2 — Look inside the sum

Part 2 samples products from across the whole window:

1
2
3
4
5
6
7
MATCHING (300 Hz signal x 300 Hz test):
   +0.00 +0.00 +0.01 +0.02 +0.04 +0.06 +0.08 +0.11 +0.15 +0.18 +0.22 +0.26 +0.31
   0 of 13 are negative

NOT MATCHING (300 Hz signal x 150 Hz test):
   +0.00 +0.05 -0.00 -0.15 +0.02 +0.24 -0.04 -0.33 +0.07 +0.42 -0.11 -0.50 +0.16
   6 of 13 are negative

Matching: everything pulls the same way. Not matching: the signs alternate and fight. That's cancellation, visible.

Step 3 — Watch it break

Part 3 takes the same 300 Hz tone, shifts it by a quarter cycle, and tests again:

1
correlation with a SINE test wave: -0.000000

Zero. The tone is unquestionably there and our detector says it isn't.

The reason: a quarter-shifted sine is a cosine, and a sine is orthogonal to a cosine of the same frequency. Our detector is blind to it.

A broken detector is a good teacher

Echo encouraging This failure is the reason the real Fourier transform uses complex numbers. Not because mathematicians enjoy them — because you need two measurements to pin down a wave whose starting point you don't know. Meet the problem first and the solution stops looking arbitrary.

Step 4 — Fix it with two test waves

Test with a sine and a cosine, then combine them like the legs of a right triangle:

1
magnitude = sqrt(sin_score**2 + cos_score**2)

1
2
3
4
5
6
                signal        sin        cos    magnitude
           300 Hz sine     0.5000    -0.0000       0.5000
         300 Hz cosine    -0.0000     0.5000       0.5000
     300 Hz, phase 0.7     0.3824     0.3221       0.5000
     300 Hz, phase 2.5    -0.4006     0.2992       0.5000
        150 Hz (wrong)    -0.0000    -0.0000       0.0000

Look at that magnitude column. The sin and cos scores swing around wildly as the phase changes — but the magnitude is 0.5000 every single time, and 0.0000 for the wrong frequency.

You now have a detector that answers "is this frequency present?" regardless of when the wave happened to start.

Step 5 — Predict, then measure

Prediction: what magnitude would a 300 Hz tone at half amplitude produce?

Change the mystery signal's amplitude to 0.5 and check. Does the relationship match what you expected?

Expected Output

See the tables above. The two numbers that matter: 0.5000 for every phase of the right frequency, 0.0000 for the wrong one.

Troubleshooting

Symptom Likely cause Fix
All candidates score near zero Test frequencies don't fit whole cycles Use multiples of RATE/N
Correlation isn't exactly zero Floating-point rounding 1e-17 is zero
Magnitude varies with phase Using only the sine You need both sine and cosine
Every candidate scores high Signal has many frequencies Try a single pure tone first

Challenges

  1. Two tones. Make the mystery signal sine(300) + 0.5*sine(500). Do both show up? Are the magnitudes in the right ratio?
  2. In-between frequencies. Test 275 Hz against a 300 Hz signal. You'll get something that isn't zero or the full value. That leakage is Lab 22's whole subject.
  3. Recover the phase. The sin and cos scores encode when the wave started. math.atan2(sin_score, cos_score) gives it back. Check it against the phase you put in.

Check Your Understanding

  1. Describe correlation in one sentence, without equations.
  2. Why does correlating two different frequencies give approximately zero?
  3. Why is a sine-only detector blind to a cosine of the same frequency?
  4. How do the sine and cosine scores combine into a magnitude?
  5. What does it mean for two waves to be orthogonal?

You built a frequency detector from scratch

Echo celebrating One multiply, one add, and a square root at the end. Next lab you'll run this at every frequency at once — and discover you've written a DFT. Nobody's going to hand it to you. You're going to build it.

Next: Lab 14: Sweeping All Frequencies | Previous: Lab 12