The word length that is not a threshold

The same filter, rounded twice ends on a number: a factor of two hundred and fifty-six in the coefficient resolution required, between a cascade of second-order sections and the same eighth-order response written down as one denominator polynomial. One word in that sentence is doing more work than it appears to. Required is the language of a threshold — a word length below which the thing fails and above which it works — and what was measured was five word lengths, at all of which the direct form’s poles were outside the unit circle. The rest was inferred, reasonably, from a mechanism that is correct.

The mechanism is correct. The threshold is not there.

What is being solved, and what the predicate is #

A design arrives as a set of pole positions in the z-plane, obtained by mapping an analogue prototype through the bilinear transform with pre-warping at the corner, which is the arrangement the corner that moved measures and defends. At a 1 kHz corner and a 48 kHz clock those eight poles sit at a radius of 0.974852.

Storing them is where the two realisations part. A cascade keeps two numbers per conjugate pair — minus twice the real part, and the squared modulus — so each pair’s coefficients belong to that pair and nothing else. A direct form keeps one denominator polynomial, whose coefficients are the elementary symmetric functions of all eight poles at once: there is no coefficient that belongs to one of them.

Each set is scaled by its own largest member and rounded to a word of $N$ bits. The direct form’s rounded denominator is then rooted, the cascade’s rounded pairs are solved as quadratics, and the question asked of the result is one bit wide: is the largest pole radius greater than one? A radius above one is a recursion whose output grows without bound. It is not a filter with a disappointing passband, and no amount of good behaviour elsewhere in the response compensates for it.

That predicate is what makes a search seem available. A quantity that is true above some word length and false below it can be found by halving an interval, which is how nearly every edge in this collection is located — the amplitude in three cliffs and where they are, the crossing in the floor a converter sets. The search costs six evaluations where the sweep costs fifty-seven, and on a quantity that is genuinely monotone it returns the same answer.

What the rounding is actually doing #

The perturbation is worth making concrete, because its size is not the surprising part and its leverage is.

Expanding this design’s eight poles into one denominator gives nine coefficients of magnitude 1.000, 7.329, 23.527, 43.201, 49.632, 36.530, 16.820, 4.430 and 0.511 — the shape a cluster near $z = 0.975$ produces, which is close to $(1 - 0.975z^{-1})^8$ and is not it. Fixed-point storage scales the set by its largest member, so at $N$ bits the step is $49.632/2^{N-1}$ — 1.515 × 10⁻³ at sixteen bits — and every coefficient carries that same absolute error, including the leading one of magnitude 1.000, for which it is a relative error fifty times larger than it is for the largest.

The pole positions depend on differences between those terms. A polynomial near a repeated root is the canonical object whose roots are far more sensitive than its coefficients, and a cluster of eight is the eighth root of that sensitivity: halving the coefficient error moves the roots by a factor of $2^{-1/8}$, which is 0.917. Eight extra bits buy a factor of two in pole movement.

That is the arithmetic behind the slope measured further down, and it is also why the verdict is ragged. A perturbation this leveraged does not move the poles in a fixed direction. It moves them by an amount that shrinks slowly and predictably, along a direction that changes completely from one word length to the next, because the direction is set by which way each of nine coefficients happened to round. The magnitude is smooth. The sign is not, and the stability question is entirely about sign.

The control, which is a realisation with no threshold at all #

Before asking where the direct form’s edge is, it is worth establishing that the question has an answer for somebody. The cascade is that control, and it is a strong one.

Over every order from three to twelve and every coefficient word length from four bits to sixty — five hundred and seventy combinations — the cascade’s largest pole radius never exceeds one. Its worst value anywhere in that grid is exactly 1.000000000000, at third order and four bits, which is a pole sitting on the circle rather than outside it: a section whose squared-modulus coefficient rounded to unity, undamped rather than divergent. Everywhere else it is inside.

So one of the two realisations has no stability threshold in the range a processor could offer, and the other has something. The comparison is not between two edges; it is between an edge and its absence, which is a stronger version of the claim the rung below made and is the reason the sweep is worth its extra evaluations.

Twenty-three failures in thirty-five word lengths #

At eighth order the direct form fails at twenty-three of the thirty-five word lengths between six bits and forty. The failures are not the twenty-three smallest.

The interesting neighbourhood is between twenty-six bits and thirty, and the five radii there are worth setting out one under the other, because their shape is the whole essay:

Three things in that column are separately worth stating. The sequence is not monotone — it goes out, further out, in, out, in. The stable entry at twenty-eight bits is inside the circle by three parts in a billion, which is a margin no design would accept and which the predicate scores identically to a comfortable one. And the two adjacent entries at twenty-eight and twenty-nine bits have almost the same pole movement — 0.1232 and 0.1181 — so the difference in verdict is not a difference in how badly the filter was damaged. It is a difference in which direction one of eight poles happened to be pushed.

One more bit of coefficient is one more halving of the storage grid, which every intuition says can only help. The same design at twenty-nine bits is the counter-example, and it is worth looking at beside the picture above rather than as a number in a column, because the two drawings are almost identical and the verdict is not.

What a bisection is entitled to assume #

A bisection does not merely need a predicate. It needs the predicate to be monotone in the search variable, and it has no way to check.

Given “unstable at twenty-six” and “stable at thirty”, a search halves to twenty-eight, finds it stable, and halves down. It returns twenty-eight bits as the smallest word length that works, and it is right about twenty-eight and wrong about the answer, because twenty-nine does not work. A designer handed twenty-eight and told to leave margin would take thirty-two and be safe by accident; one who took the number at face value and rounded down to a convenient boundary would ship the oscillator.

The honest quantity is a different one and the sweep is the only thing that can produce it: the smallest word length above every failure. At this order that is thirty bits, not twenty-eight. The two differ by two, which is small, and the fact that they differ at all is not.

This is the same distinction the collection has made about a stability region rather than a stability boundary. Stable and unstable with less gain found a loop with two disjoint stable ranges — below a gain of 979 and again between 1.81 × 10⁶ and 3.36 × 10⁷ — so that reducing its gain is what breaks it. Nothing about a gain margin quoted at one operating point says so, and nothing about a word length quoted at one rounding says so here. The edge that is a region is the collection’s name for the shape.

What the sweep costs, which is the reason it is not done #

The argument against sweeping is always the same and it is always arithmetic. A bisection over word lengths from four to sixty converges in six evaluations; the sweep is fifty-seven. On a quantity that takes an hour to evaluate the difference decides whether the question gets asked at all.

Here it does not. Rooting a denominator of degree twelve and solving six quadratics costs about half a millisecond, so the whole grid behind the figure below — ten orders, fifty-seven word lengths each — is five hundred and seventy evaluations and a fraction of a second. The sweep was not skipped because it was expensive. It was skipped because five points looked like enough, and five points spread over sixteen bits with an eight-bit gap in them cannot see a feature one bit wide.

This is the same shape as the corner where averaging stops working, where a trend measured at a few points ran out between them, and it is worth stating as a rule of thumb rather than as an anecdote: a grid can only refute a claim about behaviour finer than its own spacing. A five-point sample of a sixty-point axis is not a coarse measurement of the threshold. It is a measurement of something else that happens to have the same units.

The law that is there instead #

Something survives the refusal, and it is more useful than the threshold would have been.

Taking the smallest safe word length at each order — the one above every failure — and fitting a straight line through orders three to twelve gives a slope of 4.533 bits for every pole added, with a root-mean-square residual of 0.83 bits and a worst residual of 1.67. Six bits at third order, twelve at fourth, twenty-one at sixth, thirty at eighth, forty-seven at twelfth.

Forty-seven bits at twelfth order is the number to carry out of that figure, because it is past every fixed-point word a processor offers and past a single-precision float’s twenty-four-bit significand as well. A twelfth-order direct form is not a filter that needs care with its arithmetic; it is a filter that cannot be built in the arithmetic that exists, and the same response as six cascaded biquads is safe at four bits of coefficient.

The exponent behind that slope is the one the same filter, rounded twice derived and could not check against a range: a polynomial near a repeated root has roots that move as the $n$th root of a coefficient perturbation, so halving the perturbation moves them by $2^{-1/n}$ and the word length needed for a fixed pole movement grows linearly in the order. A linear law is what a fitted slope of 4.53 bits an order is, and the fit is what turns a derivation into a measurement.

It is not the order, it is the corner #

The slope above is quoted at one corner frequency, and the corner turns out to matter more than the order does.

Forty-seven bits and four bits are the same specification — eighth-order Butterworth, maximally flat, one clock — differing only in where the corner sits relative to the sample rate. Nothing in the phrase “an eighth-order direct form” decides the arithmetic it needs. What decides it is how close the poles sit to the unit circle, and a corner at a hundred and ninety-second of the sample rate puts them at 0.9936 where a corner at a quarter of it puts them at 0.8207.

That is the practical form of the same advice zero in, and not zero out gives about round-off and the corner that moved gives about warping: a fast clock relative to the corner is a bad idea for conditioning and a good one for everything else, and the two pull in opposite directions with nothing to say where the balance is. Here the balance is quantified — every doubling of the corner is worth eight or nine bits of coefficient at this order — and the direction is the uncomfortable one, because a designer chooses the clock for anti-alias reasons and inherits the arithmetic.

The predicate is also wrong #

The refusal above is about monotonicity. There is a second one underneath it, and the corner sweep is where it becomes visible.

At a 2 kHz corner the smallest word length that works is five bits and the largest that fails is twenty-one, so the smallest safe word length is twenty-two and the two answers are seventeen bits apart. A search offered that interval returns five, with complete confidence.

Five bits is not a coincidence to be explained away. At five bits the direct form’s largest pole radius is exactly 1.000000000000000 and its poles have moved by 0.849571 — nearly the whole radius of the unit circle. The predicate is satisfied because the poles landed on the circle rather than outside it, and a rounded coefficient landing exactly on a representable value is precisely how that happens. What the search has found is a filter that is marginally stable, has lost every pole position it was designed with, and would ring rather than filter.

So the quantity being searched is not the quantity anybody wants. Stability is necessary and it is not sufficient, and a search for the smallest word length that passes a necessary condition will find a word length that passes it for reasons unrelated to the design. The right condition is a compound one — inside the circle and poles within some tolerance of where they were placed — and a compound condition is exactly the kind that is not monotone in anything.

The nested decision, and which half this is #

There are two representation decisions in a digital filter and they are usually collapsed into one.

The first is the one this essay measures: cascade or single polynomial, which decides whether the filter is stable at all and is worth every bit in the law above — twenty-six at eighth order, forty-three at twelfth, against the four the cascade needs at either. The second is which section goes first — having chosen a cascade, the twenty-four orderings of four sections realise the identical transfer function at round-off floors running from 24 to 100 least significant bits, with thirteen of the twenty-four beaten on both counts by another arrangement.

The two are not the same kind of choice. The second is a trade with a front, where every ordering is buildable and eleven of them are genuine choices between noise and headroom. The first is not a trade at all above about fourth order: one option works and the other cannot be made to. Collapsing them into “how the filter is written down matters” loses that difference, and the difference is what decides how much effort each deserves — the first needs one decision made once, the second needs a measurement per design.

Underneath both sits the third rounding, which is neither: the products inside the recursion, whose own floor and dead band zero in, and not zero out measures. A twelve-bit eighth-order cascade fed nothing at all settles two per cent of full scale from zero. That is a defect the coefficient question cannot see, and it belongs to the realisation this essay recommends.

What this does not say #

It does not weaken the design rule. Realise a digital filter as a cascade of second-order sections. That advice is unchanged and this measurement strengthens it, because the alternative turns out to be worse than “needs more bits”: it needs a number of bits that cannot be stated as a threshold, at a value that depends on the corner more than on the order, under a test that can pass for the wrong reason.

It does not say bisection is the wrong tool generally. It is the right tool for a monotone predicate and most of the edges in this collection are monotone — a settling time against a damping ratio, a floor against a source resistance. What is being refused is the assumption, not the method. The cost of checking is one sweep, and a sweep that confirms monotonicity is not wasted.

And it does not extend past uniform fixed point. Coefficients here are scaled by the largest and rounded to an absolute grid. Floating-point coefficients carry a relative error instead, so the smallest coefficients are stored well and the largest badly, which is a different perturbation with a different answer. The comparison between realisations survives that change; the bits-per-pole slope is for this one.

What is left open #

Two things, and the first is a measurement this collection is equipped to make.

The pole movement has been used here only as a commentary on the stability verdict. It is the quantity a compound predicate would be built on, and its own behaviour against word length is not monotone either — 0.1232 at twenty-eight bits, 0.1181 at twenty-nine, 0.0600 at thirty. A tolerance on it would produce a second non-monotone predicate, and whether the conjunction of two ragged conditions has a usable edge is a question with an answer and no figure yet.

The second is scaling. Nothing here scales the polynomial by anything but its own largest coefficient, and the ill-conditioning is a statement about differences between coefficients of very different sizes — which is the shape the matrix that is ill and the answer that is not finds in a nodal matrix, where a bad condition number bounds the error and does not predict it. A better-scaled direct form is a real object and its threshold, if it has one, is unmeasured.

The number worth carrying #

Four and a half bits of coefficient for every pole, forty-seven bits at twelfth order, and none at all for a cascade at any order down to four bits.

The habit that goes with it is shorter and is not about filters. A search for an edge assumes the thing being searched changes once. That assumption is free to make, cheap to state and almost never checked, and the check is the sweep the search was introduced to avoid. Where the sweep is affordable — sixty evaluations here, against a dozen — it is worth paying for once per class of problem rather than never, because a bisection given a ragged predicate does not fail. It returns a number, in the right units, of the right size, which is wrong.