Adaptive filters and the APS-2 signal chain

Every filter so far has had fixed coefficients, designed in advance from a specification. Some problems cannot be specified in advance because the system to be filtered is unknown or keeps changing. The APS-2 faces one of them. Its microphone hears the street, but it also hears the APS-2's own speaker, through the pole housing and the air, by a path that changes when rain fills the grille, ice coats the housing or a truck parks beside the pole. If the level meter measured the microphone signal directly, the device would hear its own voice as street noise, turn itself up, hear itself louder and keep climbing. An adaptive filter solves this by learning the echo path continuously and subtracting its estimate. This final lesson develops the least-mean-squares (LMS) algorithm and its normalized form, applies it to echo cancellation, adds the Goertzel algorithm for the self-test, and assembles the whole revision C signal chain for Daniel's design review.

The adaptive filtering problem

An adaptive filter has an input x[n], the reference, and a desired signal d[n]. It produces an output y[n] = wᵀx[n], where w is a vector of N FIR coefficients and x[n] holds the last N reference samples, and it adjusts w to make the error e[n] = d[n] − y[n] as small as possible in the mean-square sense. In the echo canceller, the reference is the signal sent to the speaker, the desired signal is the microphone signal, and the filter learns to imitate the echo path from speaker to microphone. The error is then the microphone signal with the echo removed: the street noise that the level meter should measure.

The Wiener solution

If the statistics of the signals were known, the best coefficients could be computed directly. The mean-square error E[e²] is a quadratic bowl in w, with a single minimum where its gradient vanishes. Setting the gradient to zero gives the Wiener-Hopf equations, in which R is the autocorrelation matrix of the reference and p is the cross-correlation between the desired signal and the reference. The solution is the Wiener filter, the optimal linear estimator. For the echo canceller, if the street noise is uncorrelated with the reference, the Wiener filter is exactly the echo path's impulse response, truncated to N taps. Real systems rarely know R and p, and they change, so they cannot simply solve the equations once.

The LMS algorithm

Widrow and Hoff's LMS algorithm, from 1960, walks down the error bowl using the crudest possible estimate of its slope: the instantaneous gradient from one sample, −2e[n]x[n]. Each sample, every coefficient moves a small step μ in the direction that reduces the current error. The cost is two multiply-accumulates per tap per sample, one for the output and one for the update, and nothing else: no matrices, no inversions. Its simplicity and robustness have made it the most widely used adaptive algorithm in engineering, in echo cancellers, channel equalizers, noise cancelling headphones and active vibration control.

The step size μ controls everything. Too large, and the coefficients overshoot and diverge. The algorithm is stable in the mean for 0 < μ < 2/λ_max, where λ_max is the largest eigenvalue of R, and a practical bound uses the total input power instead, μ < 2/(N P_x), where P_x is the reference power. Within that range, a larger μ converges faster but leaves more noise in the coefficients, measured by the misadjustment, the excess mean-square error relative to the Wiener minimum. Convergence speed also depends on the spread of the eigenvalues of R: white references converge quickly, while strongly coloured references such as speech, whose spectrum is far from flat, converge slowly in some directions.

Normalized LMS

The APS-2's output level changes by tens of decibels between a quiet night-time locator tone and a daytime voice announcement, so a fixed μ would be too slow for one and unstable for the other. Normalized LMS (NLMS) divides the step by the current reference power, so that the effective step adapts to the signal level. Its stability range for the normalized step, 0 < μ < 2, no longer depends on the signal at all, and values of μ around 0.1 to 0.5 are typical. A small constant ε in the denominator prevents division by zero during silence. NLMS costs one extra multiply-accumulate per sample to update the running power, which is why it is the default in practical echo cancellers.

Designing the echo canceller

Leo measures the acoustic path from speaker to microphone in the pole housing with the swept-tone method of lesson 6. The direct sound arrives after about 0.6 ms, and reflections from the housing, the pole and the push-button plate die away within about 4 ms. At 16 kHz, a filter of 64 taps covers 4 ms; Amara chooses 128 taps, 8 ms, to allow for reflections from a nearby wall or a parked vehicle. The success measure is the echo return loss enhancement (ERLE), the ratio of echo power before and after cancellation. An ERLE of 20 dB means the residual echo is 20 dB below the original. How much is needed follows from how loud the echo is at the microphone. Although the APS-2 sets its output only about 5 dB above the ambient level at the crosswalk, its microphone sits a few centimetres from the speaker, where the echo can be 20 dB or more above the street noise. To keep the residual echo from raising the measured level by more than about a quarter of a decibel, the residual must be about 12 dB below the street noise, so the canceller needs an ERLE of roughly 32 dB.

Two practical problems need attention. The street noise acts as noise on the desired signal, so with a large step size it disturbs the coefficients; a modest μ keeps the misadjustment small at the cost of slower convergence, which is acceptable because the echo path changes slowly. And the reference must be exactly the signal that reaches the speaker, including the volume control and the equalizer, and aligned in time with the microphone samples, including the codec's fixed latency and the block buffering of lesson 1. Amara measures the total fixed delay once at production test and inserts it as a pure delay in front of the adaptive filter, so that its taps are spent on the acoustics, not on the latency.

import math, random
random.seed(11)
fs, N, secs = 16000, 64, 3.0
# echo path: 10-sample delay, then a decaying reflection pattern (about 4 ms)
path = [0.0] * N
for k in range(10, N):
    path[k] = 0.6 * math.exp(-(k - 10) / 12) * (1 if k == 10 else random.uniform(-1, 1))
# reference: speech-like noise with a sloping spectrum (first-order low-pass of white noise); street noise 20 dB lower
ref, s = [], 0.0
for n in range(int(fs * secs)):
    s = 0.9 * s + random.gauss(0, 1); ref.append(0.3 * s)
street = [random.gauss(0, 0.06) for _ in ref]
def run(mu, eps=1e-3):
    w = [0.0] * N; buf = [0.0] * N; pw = 0.0
    erle, echo_acc, res_acc, out = [], 0.0, 0.0, []
    for n, x in enumerate(ref):
        pw += x * x - buf[-1] * buf[-1]
        buf = [x] + buf[:-1]
        echo = sum(p * b for p, b in zip(path, buf))
        d = echo + street[n]
        y = sum(c * b for c, b in zip(w, buf))
        e = d - y
        g = mu * e / (eps + pw)
        w = [c + g * b for c, b in zip(w, buf)]
        echo_acc += echo * echo; res_acc += (echo - y) ** 2
        if (n + 1) % (fs // 2) == 0:
            erle.append(10 * math.log10(echo_acc / res_acc)); echo_acc = res_acc = 0.0
        out.append(e)
    return erle, out
for mu in (0.1, 0.5):
    erle, out = run(mu)
    tail = out[-fs // 2:]; st = street[-fs // 2:]
    meas = 10 * math.log10(sum(v * v for v in tail) / sum(v * v for v in st))
    print(f"NLMS mu = {mu}: ERLE per 0.5 s block (dB):", " ".join(f"{v:5.1f}" for v in erle), f"| street level error {meas:+.2f} dB")
echo_db = 10 * math.log10(sum(sum(p * ref[n - k] for k, p in enumerate(path) if n - k >= 0) ** 2 for n in range(fs, fs + 4000)) / sum(v * v for v in street[fs:fs + 4000]))
print(f"echo is {echo_db:.1f} dB above the street noise at the microphone")

NLMS mu = 0.1: ERLE per 0.5 s block (dB):  15.5  26.0  31.1  32.1  32.3  32.6 | street level error +0.23 dB
NLMS mu = 0.5: ERLE per 0.5 s block (dB):  19.7  24.4  24.7  24.5  24.5  24.8 | street level error +1.28 dB
echo is 20.3 dB above the street noise at the microphone

The simulation uses a shorter 64-tap filter and a 3 s run so that it finishes quickly, but it shows the trade clearly. Before cancellation the echo is about 20 dB louder than the street noise, so measuring the microphone directly would overstate the ambient level by about 20 dB. With μ = 0.5, the canceller converges within the first half second but then stalls at an ERLE of about 24.5 dB, because the street noise keeps jostling its coefficients; the residual echo still raises the measured street level by about 1.3 dB. With μ = 0.1 it converges more slowly but settles above 32 dB, and the measured level is within a quarter of a decibel of the truth. That is the misadjustment trade in numbers. Amara picks μ = 0.1 for the firmware, with μ = 0.5 for the first few seconds after power-up, when the coefficients start from zero and speed matters more than precision.

The Goertzel algorithm for the self-test

Every night at a quiet hour, the APS-2 runs a self-test: it plays the 880 Hz locator tone and checks that the microphone hears it at the expected level, which proves that the speaker, the amplifier, the microphone and the whole chain still work. Only one frequency matters, so a full FFT is wasteful. The Goertzel algorithm computes a single DFT bin with a second-order recursion, one real multiply and two adds per sample, followed by a short calculation at the end of the block. For N = 400 at 16 kHz, 880 Hz falls exactly on bin 22, as lesson 6 noted, so there is no leakage or scalloping.

The recursion is the resonator of lesson 4, run for exactly N samples and then read out, so the same cautions about coefficient precision apply; with 32-bit arithmetic and N = 400 they are negligible. The self-test passes if the tone is within ±3 dB of the level recorded at installation and fails otherwise, and the result is reported to the cabinet over the TLR-1 link. A failed test raises a maintenance call before a pedestrian notices a silent signal.

The volume law

The final block turns the measured ambient level into an output level. The guidance municipalities follow in Canada, including the Transportation Association of Canada's material on accessible pedestrian signals and the city's own specification, calls for sounds that are audible near the push button and at the start of the crosswalk without being excessive, with automatic adjustment to ambient noise. Fredericton's specification for the APS-2 sets the locator tone at 5 dB above the A-weighted ambient level, within a minimum and a maximum output level set at installation. Amara implements that rule with smoothing: the ambient estimate uses the slow time weighting of lesson 1, the output rises quickly when the street gets louder and falls slowly when it gets quieter, so a single passing truck does not leave the signal blaring.

import math, random
random.seed(2)
fs, N, k = 16000, 400, 22
c = 2 * math.cos(2 * math.pi * k / N)
def goertzel(x):
    s1 = s2 = 0.0
    for v in x:
        s1, s2 = v + c * s1 - s2, s1
    return s1 * s1 + s2 * s2 - c * s1 * s2
A = 0.05
x = [A * math.sin(2 * math.pi * 880 * n / fs) + random.gauss(0, 0.01) for n in range(N)]
P = goertzel(x)
amp = 2 * math.sqrt(P) / N
re = sum(v * math.cos(2 * math.pi * k * n / N) for n, v in enumerate(x)); im = sum(v * math.sin(2 * math.pi * k * n / N) for n, v in enumerate(x))
print(f"bin {k} = {k*fs/N:.0f} Hz; Goertzel amplitude {amp:.4f}, DFT bin amplitude {2*math.hypot(re, im)/N:.4f}, true {A}")
print(f"cost: Goertzel {N} multiplies, direct single-bin DFT {2*N}, 512-point FFT about {512//2*9*4}")
def volume(ambient_dba, vmin=40.0, vmax=89.0, margin=5.0):
    return min(vmax, max(vmin, ambient_dba + margin))
print("ambient dB(A) -> locator tone dB:", ", ".join(f"{a} -> {volume(a):.0f}" for a in (30, 45, 60, 75, 90)))
# attack and release smoothing of the output level (fast up, slow down), one update per 0.125 s
ambient = [55] * 16 + [78] * 8 + [55] * 40
level, out = 60.0, []
for a in ambient:
    target = volume(a)
    rate = 0.5 if target > level else 0.05
    level += rate * (target - level); out.append(level)
print("output level every 1 s:", " ".join(f"{v:4.1f}" for v in out[::8]))

bin 22 = 880 Hz; Goertzel amplitude 0.0504, DFT bin amplitude 0.0504, true 0.05
cost: Goertzel 400 multiplies, direct single-bin DFT 800, 512-point FFT about 9216
ambient dB(A) -> locator tone dB: 30 -> 40, 45 -> 50, 60 -> 65, 75 -> 80, 90 -> 89
output level every 1 s: 60.0 60.0 71.5 81.8 74.4 69.6 66.4 64.2

The Goertzel result matches the full DFT bin exactly and recovers the 0.05 tone amplitude within the effect of the added noise, at a quarter of the cost of the smallest useful FFT. The volume law keeps the locator tone 5 dB above the ambient level between the installation limits. When a truck raises the ambient level from 55 to 78 dB(A) for one second, the output climbs most of the way within that second and then eases back down over the following seconds instead of dropping abruptly.

The complete revision C chain

Amara's design review document summarizes every block with its rate, design, structure, word length and cost, and links each to the lesson that justified it. Daniel's questions at the review are the ones this course has prepared for: Where can aliasing still happen, and what stops it? What happens to the filters at −40 °C? (Nothing; that is the point of DSP.) What happens with a stuck microphone or a broken speaker? (The self-test catches both.) Is any filter at risk of overflow or limit cycles? (No: 32-bit direct form I, saturating arithmetic, dither on the 16-bit output.) How much processor is left? (Most of it.)

The total is about a tenth of the processor, consistent with the first budget of lesson 1 but now backed by actual structures. Verification follows the same pattern for every block: a bit-accurate reference model in Python, test vectors generated from it, the firmware run on the vectors in a test harness, and the outputs compared sample by sample, followed by acoustic tests on a finished pole station in the lab and a pilot at two intersections. Leo writes the test vectors, which is a fitting last job for a co-op term spent learning what every block does.