Implementing Filters

Direct forms, second-order sections, coefficient quantisation, round-off and limit cycles, overflow, and real-time block processing

8 April 1983 — a processor for signals

Texas Instruments introduces the TMS320 family with its first member, the TMS32010 — then the fastest digital signal processor on the market. It is built for exactly the operation a filter repeats on every sample: a fast multiply-and-accumulate, in a modified Harvard architecture that fetches instructions and data separately (TMS320). Its arithmetic is 16-bit fixed point: every coefficient is rounded to a 16-bit fraction, every product is rounded back, and every sum must stay within range. The filters of the last two lessons were exact. On chips like this one they are not — and the way a filter is built decides whether that matters.

One transfer function can be computed by many structures: direct form I and II, their transposed versions, a cascade of second-order sections, a parallel bank. In exact arithmetic they are identical. In finite precision they are not, because each structure rounds different numbers and feels each rounding differently.

Derivation

Why high-order polynomials are fragile

Let the denominator be

A(z) = z^N + a_1z^{N-1} + \dots + a_N

with roots

p_1, \dots, p_N

. Perturb one coefficient: at a root,

A

stays zero, so

A'(p_i)\,\delta p_i + p_i^{N-k}\,\delta a_k = 0 \quad\Longrightarrow\quad \frac{\delta p_i}{\delta a_k} = -\frac{p_i^{N-k}}{\prod_{j \ne i}(p_i - p_j)} .

When poles cluster — as they do for a narrow low-pass, all crowded near

z = 1

— every difference

p_i - p_j

is small, their product is tiny, and a minute change in one coefficient moves the poles a long way. A second-order section has only two poles, so the product has a single factor and stays modest.

📐Rounding an eighth-order filter

An eighth-order Butterworth low-pass with its cut-off at 4 % of the Nyquist frequency has its largest pole at radius 0.975840, and direct-form denominator coefficients ranging from 0.525 to 50.3. Round those coefficients to six decimal places and the largest pole moves to radius 1.083 — outside the unit circle: the filter is now unstable. Round the same filter's four second-order sections to six decimals and the largest pole sits at 0.975841. This is why practical IIR filters are built from second-order sections (output='sos' in SciPy).

💡Fixed point: round-off, overflow and limit cycles

Round-off. Every rounded product adds a small error, roughly uniform noise of variance $q^2/12$ for a step $q$ . A first-order smoother computed in Q15 (16-bit) arithmetic tracks its floating-point twin with a signal-to-error ratio of about 73 dB.
Overflow. A sum that exceeds the range wraps round to the opposite sign unless the hardware saturates; scaling the signal at each section keeps sums in range.
Limit cycles. Rounding inside a feedback loop can keep a filter alive with no input at all. $y[n] = \operatorname{round}(0.95\,y[n-1])$ , started at 100, decays to 10 and stays there for ever — the deadband $0.5/(1 - a) = 10$ — while the exact filter decays to 0.0035.

💡Real time: blocks and state

Live signals arrive in blocks — an audio driver may deliver 256 samples at a time — and the filter's memory, its state, must carry from each block to the next. SciPy passes it in and out as zi. Filtering four seconds of audio block by block with the state carried gives exactly the whole-signal result; resetting the state at every block leaves errors of up to 0.99 at every block boundary — a click 31 times a second.

Beware of bugs in the above code; I have only proved it correct, not tried it.

– Donald Knuth, closing a 1977 memo, quoted on Wikiquote

🕰A family that grew

The TMS32010 was the first of a long line. Later members of the TMS320 family came in both fixed- and floating-point versions, made on NMOS and then CMOS chips (TMS320). Floating point removes most overflow worries but not round-off, and fixed point remains common wherever power and cost are tight.

⚠Test in the arithmetic you ship

Simulate integer arithmetic with its real word length, rounding mode and saturation, feed the filter worst-case signals — full-scale steps, sinusoids at the band edge, silence after a loud passage — and look for overflow, limit cycles and pole migration. A filter that only ever ran in float64 has not been tested.

💡Where you will use this

Every embedded filter — in hearing aids, flight computers, motor drives and phones — faces these choices. The same block-and-state discipline runs real-time audio, sensor fusion and the digital receivers of Unit 10.

📚Further reading

Alan V. Oppenheim and Ronald W. Schafer, Discrete-Time Signal Processing (3rd ed., Pearson, 2010), chapter 6 — structures and the effects of finite precision.
Richard G. Lyons, Understanding Digital Signal Processing (3rd ed., Prentice Hall, 2010) — a practical view of fixed-point filtering.
TMS320 on Wikipedia.

↓But there is a problem

Filters shape signals. To carry a signal anywhere — across a room, a country, an ocean — it has to ride on something that travels: a carrier, many times higher in frequency than the message itself. On the evening of a United States presidential election in 1920, a station in Pittsburgh did exactly that, and a new medium began.