Appearance
5.P — Worked Problems: Digital Signal Processing
Problem 1 — DFT resolution and record length
You must distinguish two tones 3 Hz apart in a signal sampled at 44.1 kHz. What FFT length is needed, and how long must you record? What if the tones are 0.5 Hz apart?
Solution
\Delta f=\frac{f_s}{N} \le 3\ \text{Hz} \;\Rightarrow\; N\ge\frac{44{,}100}{3}=14{,}700
Round up to a power of two: N = 16{,}384, giving \Delta f = 2.69 Hz.
T_{record}=\frac{16{,}384}{44{,}100}=0.372\ \text{s}
But a window widens the peak. A Hann window's main lobe is 4 bins wide, so two peaks 3 Hz apart at 2.69 Hz per bin are only 1.1 bins apart — they will merge into one. To resolve them with a Hann window you need roughly 4 bins of separation:
\Delta f\le\frac{3}{4}=0.75\ \text{Hz} \;\Rightarrow\; N\ge58{,}800 \;\to\; 65{,}536
T=1.49\ \text{s}
For 0.5 Hz separation, with the same factor of 4:
\Delta f\le0.125 \;\Rightarrow\; N\ge352{,}800 \;\to\; 524{,}288, \qquad T=11.9\ \text{s}
Twelve seconds of recording, and there is no way around it.
The lesson stated plainly. Resolution is set by record length in seconds and nothing else. Zero-padding a 0.372 s record to a million points would produce a beautifully smooth plot showing one peak where there are two. The plot would look better and be more wrong.
Problem 2 — Spectral leakage
A 1 kHz sine of amplitude 1 V is sampled at 8 kHz. Compare N = 800 with N = 1024, without windowing.
Solution
N = 800. Bin width is 8000/800 = 10 Hz. The tone is at bin 100 exactly.
The signal completes 1000 \times (800/8000) = 100 whole cycles in the record, so the periodic extension joins seamlessly. One clean peak at bin 100, essentially nothing elsewhere.
Peak magnitude: AN/2 = 1\times400 = 400.
N = 1024. Bin width is 8000/1024 = 7.8125 Hz. The tone is at bin 1000/7.8125 = 128.0.
Also an integer — 128 exactly. The signal completes 1000\times(1024/8000)=128 cycles. Also clean.
Now change the tone to 1010 Hz with N = 1024. Bin 1010/7.8125=129.28 — not an integer, and the record contains 129.28 cycles.
The discontinuity in the periodic extension spreads energy everywhere. With a rectangular window the sidelobes fall as 1/\Delta f, so the first sidelobe is at -13 dB and the level is still around -30 dB twenty bins away.
The practical consequence. A second tone at -40 dB, 150 Hz away (about 19 bins), would be completely hidden. With a Hann window the leakage 19 bins away is below -90 dB and the small tone appears clearly.
The rule this establishes: if you can arrange for your signal to be exactly periodic in the record — which you can when you control the test signal — use no window and get perfect results. When you cannot, which is always with real signals, window.
Problem 3 — FFT operation count and speedup
Compare the direct DFT and the FFT for N = 4096, and find the real-time limit for a processor doing 200 million complex multiplies per second.
Solution
Direct: N^2 = 16{,}777{,}216 complex multiplies.
FFT: \frac{N}{2}\log_2N = 2048\times12=24{,}576.
\text{speedup}=\frac{16{,}777{,}216}{24{,}576}=683\times
Time on a 200 MMAC/s processor:
\text{Direct: } \frac{1.68\times10^7}{2\times10^8}=84\ \text{ms}
\text{FFT: } \frac{24{,}576}{2\times10^8}=123\ \mu\text{s}
How many transforms per second are possible?
Direct: 12 per second. FFT: 8,138 per second.
For a spectrogram with 50% overlap at 48 kHz, frames arrive every 2048 samples = 42.7 ms. The FFT uses 123 µs of that — 0.3% of the processor. The direct DFT would need 84 ms per frame, which is twice the available time. The direct method makes the application impossible; the FFT makes it free.
And note the scaling. At N = 65,536 the speedup is 8,192×. The FFT's advantage is not a constant factor; it grows without limit, which is why it changed what was computable rather than merely how fast.
Problem 4 — Design an FIR low-pass
Design a linear-phase FIR low-pass: sample rate 48 kHz, passband to 4 kHz, stopband from 5 kHz, 60 dB attenuation. Find the order, the latency, and the computation.
Solution
Normalise the frequencies:
\omega_p=2\pi\frac{4000}{48000}=0.1667\pi, \qquad \omega_s=2\pi\frac{5000}{48000}=0.2083\pi
\Delta\omega=0.0417\pi=0.1309\ \text{rad/sample}
Kaiser's estimate:
M\approx\frac{A-8}{2.285\Delta\omega}=\frac{60-8}{2.285\times0.1309}=\frac{52}{0.2991}=174
Use 175 taps (odd, so the delay is a whole number of samples).
Latency:
\frac{M}{2}=87\ \text{samples}=\frac{87}{48000}=1.81\ \text{ms}
Computation: 175 MACs per sample, so
175\times48{,}000=8.4\ \text{million MACs/s}
Trivial for any DSP, and about 2% of a 100 MHz single-MAC device. Exploiting the symmetry (b_k = b_{M-k}) lets you add the symmetric pairs before multiplying, halving it to 4.2 million.
Now compare with an IIR. An 8th-order elliptic filter meets the same specification:
4\ \text{biquads}\times5\ \text{MACs}\times48{,}000=960{,}000\ \text{MACs/s}
Nearly ten times cheaper, with latency of a few samples rather than 87.
Which to choose. If this is an anti-alias filter before a converter, or an audio playback filter, the IIR is the right answer — phase distortion near 4 kHz is inaudible and the saving is real.
If it is filtering a pulse train where the shape carries data, the FIR's linear phase is the entire reason for filtering and 1.81 ms of latency is a small price.
Problem 5 — IIR design with the bilinear transform
Design a 2nd-order Butterworth low-pass with a 1 kHz cut-off at 10 kHz sample rate. Give the difference equation.
Solution
Step 1 — prewarp.
\omega_d=2\pi\times1000=6283\ \text{rad/s}, \qquad T=10^{-4}\ \text{s}
\omega_a=\frac2T\tan\frac{\omega_dT}{2}=20{,}000\tan(0.3142)=20{,}000\times0.3249=6498\ \text{rad/s}
Design the analog filter for 1034 Hz, not 1000 Hz.
Step 2 — the analog prototype. A 2nd-order Butterworth:
H(s)=\frac{\omega_a^2}{s^2+\sqrt2\,\omega_as+\omega_a^2}
Step 3 — substitute the bilinear transform. Let K = 2/T = 20{,}000 and u = z^{-1}:
s=K\frac{1-u}{1+u}
H(z)=\frac{\omega_a^2(1+u)^2}{K^2(1-u)^2+\sqrt2\omega_aK(1-u)(1+u)+\omega_a^2(1+u)^2}
Numbers. \omega_a^2 = 4.22\times10^7, K^2=4\times10^8, \sqrt2\omega_aK=1.838\times10^8.
Denominator, collecting powers of u:
- u^0: 4\times10^8+1.838\times10^8+4.22\times10^7 = 6.26\times10^8
- u^1: -8\times10^8+0+8.44\times10^7=-7.156\times10^8
- u^2: 4\times10^8-1.838\times10^8+4.22\times10^7=2.584\times10^8
Numerator: 4.22\times10^7(1+2u+u^2).
Divide everything by 6.26\times10^8:
H(z)=\frac{0.0674+0.1348z^{-1}+0.0674z^{-2}}{1-1.1431z^{-1}+0.4128z^{-2}}
Difference equation:
y[n]=0.0674x[n]+0.1348x[n-1]+0.0674x[n-2]+1.1431y[n-1]-0.4128y[n-2]
Check the DC gain by setting z=1:
\frac{0.0674+0.1348+0.0674}{1-1.1431+0.4128}=\frac{0.2696}{0.2697}=1.0 \ ✓
Check Nyquist by setting z=-1:
\frac{0.0674-0.1348+0.0674}{1+1.1431+0.4128}=\frac{0}{2.556}=0 \ ✓
Exactly zero at Nyquist, which is what the (1+z^{-1})^2 numerator guarantees — the bilinear transform maps analog infinity to z=-1.
Check the poles. z^2-1.1431z+0.4128=0 gives z = 0.5716\pm j0.2896, magnitude \sqrt{0.3267+0.0839}=0.641. Inside the unit circle ✓ stable.
Problem 6 — Fixed-point scaling
Implement the filter of Problem 5 in Q15 arithmetic on a 16-bit processor. Identify the problem and fix it.
Solution
The immediate problem: a_1 = 1.1431 exceeds the Q15 range of \pm1. It cannot be represented.
Fix 1 — use Q14 for the coefficients, giving a range of \pm2:
a_1 = 1.1431\times16384=18{,}728 \;\to\; \text{fits in 16 bits signed? } 18{,}728 \lt 32{,}767 \ ✓
b_0=0.0674\times16384=1104, \quad b_1=2208, \quad b_2=1104, \quad a_2=-0.4128\times16384=-6764
Then each product is Q14 × Q15 = Q29, so shift right by 14 to return to Q15.
Fix 2 — scale the coefficients by 1/2 and compensate with an output shift. Then everything fits in Q15 and the multiplication is the standard Q15×Q15 = Q30, shift left 1, take upper word.
Now the quantisation error. a_1 stored as 18,728/16,384 = 1.14307, against 1.14310 — an error of 2.6\times10^{-5}.
Where do the poles move? z^2-1.14307z+0.41278=0 gives essentially the same roots. The magnitude changes in the fifth decimal place — harmless.
But try the same filter as an 8th-order single section. The coefficient of z^{-1} would be around 7, needing Q12, and the quantisation error would be 2^{-12}=2.4\times10^{-4}. In an 8th-order polynomial that error can move the roots by several percent, and a pole at radius 0.98 can easily be pushed past 1.0.
Which is exactly why biquads are compulsory. Four cascaded 2nd-order sections, each with the small coefficients above, are numerically robust; one 8th-order section is not.
Also check overflow. The filter's peak gain is 1.0 at DC, but the internal state in Direct Form II can exceed that. Compute the peak of 1/A(z) — for this filter, about 1.6. So scale the input down by a factor of 2 before the filter and up by 2 after, or the internal state overflows on a full-scale input.
Problem 7 — Decimation design
Reduce a 48 kHz signal containing content up to 3 kHz down to 8 kHz. Design the filter and compute the saving from polyphase implementation.
Solution
Decimation factor: M = 48/8 = 6.
New Nyquist: 4 kHz. Anything above 4 kHz must be removed before discarding samples, or it aliases into the 0–4 kHz band.
Filter specification: passband to 3 kHz, stopband from 4 kHz, at the original 48 kHz rate.
\Delta\omega=2\pi\frac{4000-3000}{48000}=0.1309\ \text{rad/sample}
For 60 dB:
M_{taps}\approx\frac{52}{2.285\times0.1309}=174 \;\to\; 175\ \text{taps}
Direct implementation cost:
175\times48{,}000=8.4\ \text{million MACs/s}
But five out of every six outputs are discarded immediately. Computing them is pure waste.
Polyphase implementation computes only the retained outputs:
175\times8{,}000=1.4\ \text{million MACs/s}
A saving of exactly 6× — the decimation factor, which is the general result.
Two-stage alternative. Decimate by 3 then by 2.
Stage 1 (48 → 16 kHz): passband 3 kHz, stopband 8 kHz. Transition is 5 kHz wide, so \Delta\omega = 0.654 and
M_1\approx\frac{52}{2.285\times0.654}=35\ \text{taps}
Cost: 35\times16{,}000=560 kMACs/s.
Stage 2 (16 → 8 kHz): passband 3 kHz, stopband 4 kHz at 16 kHz rate, so \Delta\omega=0.3927:
M_2\approx\frac{52}{2.285\times0.3927}=58\ \text{taps}
Cost: 58\times8{,}000=464 kMACs/s.
Total: 1.02 million MACs/s against 1.4 million for one stage — another 27% saved, and less memory too.
The general principle: multistage decimation is cheaper because the early stages can use wide transition bands (the stopband requirement is loose while the rate is still high), and only the final stage needs the sharp filter, by which time the sample rate is low.
Problem 8 — Compute budget for a real product
An 8-channel audio processor at 48 kHz applies, per channel: a 5-band parametric equaliser, a compressor, and a 512-tap convolution reverb. Assess the load.
Solution
Equaliser. Each band is a biquad: 5 multiplies, 4 adds.
5\ \text{bands}\times5\ \text{MACs}\times48{,}000\times8=9.6\ \text{MMACs/s}
Compressor. Level detection (one exponential filter, 2 MACs), gain computation (a logarithm and an exponential, say 20 operations), and one multiply. Call it 25 operations per sample:
25\times48{,}000\times8=9.6\ \text{Moperations/s}
Reverb, direct convolution:
512\times48{,}000\times8=196.6\ \text{MMACs/s}
Total: about 216 MMACs/s. On a 400 MHz DSP achieving 60% efficiency, that is 240 MMACs available — 90% loaded. Too tight.
Reverb via FFT. With a block size of 1024 and L = 2048:
Three transforms: 3\times1024\times11=33{,}792 complex operations, each about 4 real MACs, so 135,168 real MACs. Plus 2048 complex multiplies = 8,192 real. Total about 143,000 per block per channel.
Blocks arrive every 1024 samples = 21.3 ms:
\frac{143{,}000}{0.0213}\times8=53.7\ \text{MMACs/s}
Down from 196.6 to 53.7 — a factor of 3.7.
New total: 73 MMACs/s, or 30% loaded. Comfortable.
The cost is latency. Block processing adds 1024 samples of buffering:
\frac{1024}{48{,}000}=21.3\ \text{ms}
Acceptable for playback, unacceptable for a live performer monitoring themselves.
The professional solution is partitioned convolution: use small blocks (64 samples, 1.3 ms) for the first part of the impulse response and progressively larger blocks for the later parts, which do not need low latency because they are already delayed. You get FFT efficiency with direct-convolution latency, and it is what every low-latency convolution reverb does.
Problem 9 — Welch's method
You have 8 seconds of data at 10 kHz (80,000 samples) and need a noise spectrum with 1 dB confidence. Design the analysis.
Solution
For roughly 1 dB of uncertainty, the standard deviation of the estimate should be about 12% of the mean, so
\frac{1}{\sqrt K}\approx0.12 \;\Rightarrow\; K\approx70\ \text{segments}
With 50% overlap, K segments of length L cover (K+1)L/2 samples:
\frac{71\times L}{2}=80{,}000 \;\Rightarrow\; L=2254 \;\to\; \textbf{2048}
Recompute: with L=2048 and 50% overlap, the number of segments is
K=\frac{2\times80{,}000}{2048}-1=77
\text{uncertainty}=\frac{1}{\sqrt{77}}=11.4\% \approx 0.94\ \text{dB} \ ✓
Resolution:
\Delta f=\frac{10{,}000}{2048}=4.88\ \text{Hz}
Check that is enough. For a broadband noise measurement, 4.88 Hz is plenty. But if you also need to see a discrete tone's exact frequency, 4.88 Hz may not be, and then you would take a separate single long FFT for that purpose.
The trade in numbers. One 80,000-point FFT would give 0.125 Hz resolution and 100% uncertainty — the plot would be unreadable jagged noise. 77 segments give 4.88 Hz resolution and a clean, trustworthy curve. Same data, and the choice depends entirely on which question you are asking.
Report it correctly. Noise must be quoted as spectral density:
\text{PSD}=\frac{\text{power in bin}}{\Delta f} \ \text{in V}^2/\text{Hz}, \text{ or } \text{V}/\sqrt{\text{Hz}}
Quoting a noise level in dBV without the per-hertz would make it depend on your FFT length, which is a meaningless way to report a physical property.
Problem 10 — JPEG bit rate
A 12-megapixel photo (4000 × 3000) is saved at JPEG quality 75. Estimate the file size and check it against the compression ratio.
Solution
Uncompressed: 4000\times3000\times3 bytes = 36 MB.
After 4:2:0 chroma subsampling: luma is full resolution, chroma is quarter resolution in each of two channels:
12\ \text{M} + 2\times3\ \text{M}=18\ \text{M samples}
Half the data gone before compression starts.
Number of 8×8 blocks: luma has 12\times10^6/64=187{,}500; each chroma channel has 46,875, so 281,250 blocks total.
At quality 75, typical JPEG output is about 20:1 overall, so
\frac{36\ \text{MB}}{20}=1.8\ \text{MB}
Bits per pixel:
\frac{1.8\times10^6\times8}{12\times10^6}=1.2\ \text{bits per pixel}
against 24 uncompressed.
Bits per block:
\frac{1.8\times10^6\times8}{281{,}250}=51\ \text{bits per 8×8 block}
Fifty-one bits to describe sixty-four pixels. Most blocks in a photograph are smooth, so after quantisation only the DC coefficient and two or three low-frequency terms survive, and the rest is one end-of-block symbol.
Where the compression actually comes from, in order:
- Chroma subsampling: 2×
- Quantisation zeroing most coefficients: about 8×
- Huffman coding of what remains: about 1.25×
2\times8\times1.25=20\times \ ✓
Note that step 2 does nearly all the work, and it is the only lossy step. Step 1 is also lossy and step 3 is not. So the entire quality setting is a knob on the quantisation table, and everything else is fixed.
Problem 11 — Masking and MP3 bit allocation
In one MP3 frame, a critical band contains a tone at 80 dB. A neighbouring band has content at 45 dB, and the masking threshold there is 52 dB. How many bits should each band get?
Solution
The neighbouring band's content at 45 dB is below the 52 dB masking threshold, so it is inaudible. Allocate zero bits — discard it entirely.
For the band containing the 80 dB tone, the quantisation noise must sit at or below the masking threshold within that band, which for a tone masking itself is roughly 80 − 20 = 60 dB (a typical signal-to-mask ratio for a tonal component).
\text{SNR needed}=80-60=20\ \text{dB}
From Chapter 3.5's relation:
n=\frac{\text{SNR}-1.76}{6.02}=\frac{20-1.76}{6.02}=3.03 \;\Rightarrow\; \textbf{4 bits}
Four bits for a component that arrived with sixteen.
Contrast with lossless coding, which must preserve all 16 bits regardless of audibility. That is the whole difference in one example: the perceptual coder asks "will anyone hear the error?" and the lossless coder asks "can I predict this value?".
And the number that makes MP3 work: across a typical frame, most bands are either masked (zero bits) or need only 3 to 6 bits. Averaged over all 576 frequency lines and both channels, that is the 1.45 bits per sample computed in Chapter 5.4.
Where it fails. A signal with no strong tonal components — applause, a cymbal wash, pink noise — has no masker, so nothing can be discarded and the encoder must either use more bits or produce audible artifacts. This is exactly why applause is the classic test signal for revealing codec problems.
Problem 12 — Noise cancelling limits
Estimate the highest frequency at which feedforward noise cancellation works, given a microphone 2 cm from the ear canal entrance and 30 µs of total electronic delay.
Solution
Two independent limits.
Acoustic travel time from the microphone to the ear:
t_{acoustic}=\frac{0.02}{343}=58\ \mu\text{s}
The electronics have this long to produce the anti-noise. With 30 µs of processing delay there is 28 µs of margin — adequate, so the electronics are not the binding constraint here.
Phase accuracy is the real limit. For cancellation of 20 dB, the anti-noise must match in amplitude to within about 10% and in phase to within about 6°.
A 30 µs error is 6° of phase at:
f=\frac{6/360}{30\times10^{-6}}=\frac{0.0167}{3\times10^{-5}}=556\ \text{Hz}
So 20 dB of cancellation is achievable up to roughly 550 Hz with this delay.
For 10 dB of cancellation, the phase tolerance relaxes to about 18°, giving 1.67 kHz.
And the spatial limit. Cancellation requires the anti-noise source to be within roughly a tenth of a wavelength of the point being cancelled. With 2 cm separation:
\lambda=10\times0.02=0.2\ \text{m} \;\Rightarrow\; f=\frac{343}{0.2}=1.7\ \text{kHz}
Both limits land around 1 to 2 kHz, which matches every real product's measured performance.
Above that, passive isolation takes over. A well-sealed earcup gives 20 to 30 dB above 1 kHz simply by blocking sound, which no active system approaches.
The design conclusion, which the numbers make inescapable: active for the low rumble, passive for everything else, and the two are complementary rather than competing. A noise-cancelling headphone with a poor seal fails at high frequencies no matter how good its electronics are.
Problem 13 — Choosing a processor
A design needs: 4 channels at 96 kHz, 128-tap FIR per channel, an FFT of 1024 points every 512 samples, and a 5 ms latency budget. Choose between a 200 MHz microcontroller with DSP instructions, a 600 MHz DSP, and an FPGA.
Solution
Compute the load.
FIR: 4\times96{,}000\times128=49.2 MMACs/s.
FFT: one 1024-point transform every 512 samples at 96 kHz, so every 5.33 ms, which is 188 per second. Each costs \frac{1024}{2}\times10=5120 complex multiplies ≈ 20,480 real MACs:
188\times20{,}480=3.85\ \text{MMACs/s}
Total about 53 MMACs/s.
Microcontroller at 200 MHz, achieving perhaps 0.8 MACs per cycle in a well-written FIR loop: 160 MMACs/s available. Load is 33% — feasible, leaving room for control code and interrupts.
DSP at 600 MHz with dual MAC units: 1200 MMACs/s. Load is 4% — enormously over-specified for this job.
FPGA: trivially capable, and far more expensive in both part cost and development time.
Now check latency.
The FFT needs 512 samples of buffering: 512/96{,}000=5.33 ms. That alone exceeds the 5 ms budget.
So the specification is inconsistent as written, and this is the genuinely useful part of the exercise. Options:
- Reduce the FFT hop to 256 samples — 2.67 ms of buffering, leaving 2.3 ms for everything else. Doubles the FFT load to 7.7 MMACs/s, which is nothing.
- Question whether the FFT output is really on the critical path. If it feeds a slow control decision rather than the audio itself, it does not contribute to audio latency at all, and the budget is met.
Verdict: the microcontroller, with a 256-sample FFT hop. It is the cheapest part that meets the requirement, and the exercise's real lesson is that latency, not computation, was the binding constraint — which is the usual situation and the one most often discovered late.
Problem 14 — Diagnose a broken measurement
A vibration measurement shows a strong 60 Hz peak and harmonics at 120, 180 and 240 Hz. The machine runs at 1750 rpm. Is the peak real?
Solution
Convert the machine speed:
\frac{1750}{60}=29.2\ \text{Hz}
So mechanical harmonics would appear at 29.2, 58.3, 87.5, 116.7 Hz — not at 60, 120, 180.
The 60 Hz series is mains interference, and the harmonics at exact multiples confirm it: a distorted mains waveform produces exactly this pattern.
How it got in. Three usual routes:
- A ground loop — the sensor's ground and the instrument's ground are at slightly different potentials, and the difference appears in series with the signal.
- Capacitive coupling from a nearby power cable into a high-impedance sensor lead.
- Magnetic coupling into a loop formed by the signal and return wires.
The fixes, in order of preference:
- Fix the wiring. Twisted pair reduces magnetic pickup because the loop area collapses. Shielding grounded at one end only reduces capacitive pickup without creating a loop. Single-point grounding removes ground loops.
- Use differential inputs with a good common-mode rejection ratio (Chapter 2.5), since the interference is common to both wires.
- Add a notch filter, exactly as designed in Chapter 4.6.
Why the notch is last on the list. It removes the symptom and leaves the cause. And 58.3 Hz — the machine's real second harmonic — is only 1.7 Hz from the notch, so a notch narrow enough to spare it must have r very close to 1, which brings the numerical problems of Chapter 5.2.
The genuinely correct answer: fix the wiring. A measurement whose interference has been filtered out is always less trustworthy than one where it was never present, because you can no longer tell what else the filter removed.
And there is one real finding hiding here. With the mains series identified, look again for peaks at 29.2 Hz and its harmonics — those are the machine, and they are what the measurement was for.
Part 6 turns from analysing signals to controlling machines, and the feedback that Chapter 2.6 made oscillate is put to work making things behave.