6
$\begingroup$

Background

My typical approach to fixed point design for digital filters is to iteratively scale and increase quantization while comparing the fixed point simulation to the floating point design target until errors are sufficiently minimized.

I've taken a recent interest in going deeper into the details of quantization effects of fixed point design and further considerations in digital filter structures. This has led me to the implementations for the 2nd order IIR Biquad in particular, and the recommended use of the "Coupled Form" when poles approach $z= \pm 1$ first proposed by Rader and Gold in 1967, and more recently summarized in Rick Lyon's very interesting (as all) blog post here, as well as numerous other references (such as in Discrete-Time Signal Processing by Oppenheim and Schafer, on page 383 in the 2nd edition). As developed in those references, the use of the Coupled-Form instead of the popular Direct Forms results in a uniform distribution of quantization levels for pole locations over the z-plane, for which when the poles are in vicinity of $z=\pm 1$ results in reduced precision requirements for frequency response accuracy, and as further detailed in this 1972 paper by Oppenhiem and Weinstein, improved SNR when limited by quantization noise.

In going through this, I got distracted by the pattern of the quantized poles on the z-plane (as well as the zeros) which I find quite interesting, and my question is the mathematical prediction of this pattern beyond that shown in the literature. I will first summarize the known mathematical relationships to avoid it being repeated in an answer. Below that I will articulate my question more specifically; seeking the mathematics of the pattern repetitions in the quantization of the poles.

The Existing Math; Poles vs Coefficients

Given transfer function for the 2nd order IIR biquad transfer function with real coefficients as

$$H(z) = \frac{b_0z^2 + b_1z + b_2}{z^2 + a_1z + a_2} $$

poles are located where denominator is zero:

$$z^2 + a_1z + a_2 = 0$$

or in the case of a complex conjugate pair

$$ (z-z_p)(z-z_p^*) = 0 $$

$$ z_p = r e^{j \theta} $$

It is easily shown, as detailed in the referenced literature, that the location of the poles (as the roots of the denominator of $H(z)$ in the z-plane) are related to the coefficients $a_1$ and $a_2$ according to:

$$z^2 - 2r\cos(\theta) + r^2 = 0$$

Where $r$ and $\theta$ is the magnitude and phase for one of the poles in the upper half plane (with it's complex conjugate pair in the lower half plane).

I have further derived this to a relationship for the pole $z_p$ in the upper half plane given $a_1$ and $a_2$ as follows:

$$z_p = -\frac{a_1}{2} + j\sqrt{a_2-\frac{a_1^2}{4}}$$

Thus given a uniform quantization for $a_1$ and $a_2$ as would be done in the Direct Form structures, the poles would be on the intersections of quantized radii according to $r=\sqrt{a_2}$ and the quantized real-axis according to $-\frac{a_1}{2}$. This results the patterns that have been shown in numerous texts and publications and recreated in the plots below, here showing the quantized locations of the possible pole locations in the first quadrant of the z-plane for 5 bits and 8 bits of quantization (including sign bit).

quantized poles on the z-plane

In this case to generate the plots above, the full precision was used over the possible range for $a_1$ and $a_2$ for all positions inside the unit circle as signed twos complement fixed point numbers (where "5 bits" and "8 bits" represents the word width $W$, the number of bits in including the sign bit), as $a_1 \in [-2,2)$ and $a_2 \in [-1, 1)$ according to:

$$a_1 = -2, -2+\frac{1}{2^{W-2}}, -2+\frac{2}{2^{W-2}}, \ldots 2-\frac{1}{2^{W-2}}$$

$$a_2 = -1, -1 +\frac{1}{2^{W-1}}, -1+\frac{2}{2^{W-1}}, \ldots 1-\frac{1}{2^{W-1}}$$

My Question

In creating the plots, I notice the repeating pattern along the real axis of concentric circles for the possible pole locations, as circled in the graphic below for the case of 5 bits:

pattern of concentric circles

In the similar plot for 8 bits given earlier, we also begin to see the appearance of smaller circles, and such a fractal-like pattern emerges as the number of bits increase. It is clear from my continued experimentation that the circle of possible poles in vicinity of $z=1$ reliably mirrors that for $z=0$, however I would like to prove this relationship mathematically. My primary question therefore is how to prove mathematically the circular pattern of poles in vicinity of $z=1$ is the same as that for the poles around $z=0$? As a secondary question in case it develops from the first one is how many poles will be on the real axis and what is their positions and resulting radii to the closest (Euclidean distance) poles, for a given bit size?

Ultimately this is to provide initial "rule of thumb" guidance in quantization needed for such Direct Form 2nd order IIR filters with poles or zeros in vicinity of $z= \pm 1$, even though as I noted it is simple enough to just simulate. I already have the equations given the apparent symmetry between $z=1$ and $z=0$, but still I would like to see the math that proves this symmetry exists or under which cases it exists.


The significance of the derivation completed by Robert Bistrow and myself in the answer below is a useful relationship of the worst case root quantization error versus coefficient precision in a 2nd order biquadratic filter. The radius $r$ of the largest circle with a origin at $z=1$ is given as:

$$r = 2^{-(W-1)/2}$$

Where $W$ is the precision size for the number of bits used, including sign bit, to quantize the coefficients.

For example, given a precision of 5 bits, the radius would be $2^{(5-1)/2}= 0.25$. A pole located in this region would therefore have a maximum possible error of this divided by two (0.125).

$\endgroup$
5
  • $\begingroup$ I feel like I’ve seen these types of plots in some Fred Harris lecture, maybe from the DSP online conference? $\endgroup$
    – Jdip
    Commented Dec 27, 2022 at 19:02
  • $\begingroup$ @Jdip possibly; they are "common knowledge" when it comes to fixed point IIR filter deisgn (in every DSP text book etc)--- what I haven't found yet is the mathematical relationship I'm mentioning in the post; but likely that is already worked out as well. $\endgroup$ Commented Dec 27, 2022 at 21:14
  • $\begingroup$ Can we just show that the distance or distance-squared, from the discrete poles to the center point (which appears to be a pole on the real axis) is constant? $\endgroup$ Commented Dec 27, 2022 at 21:56
  • 1
    $\begingroup$ @Jdip I found the fred harris reference you were likely thinking of: s3.amazonaws.com/embeddedrelated/user//… Very clever, his idea is to simply frequency translate a low pass to a bandpass rather than use the coupled approach that doubles the number of multipliers. $\endgroup$ Commented Dec 31, 2022 at 23:15
  • 1
    $\begingroup$ Yes that’s it! Fred Harris is always worth the read. $\endgroup$
    – Jdip
    Commented Jan 1, 2023 at 10:41

1 Answer 1

1
$\begingroup$

Okay, with

$$z_p = -\frac{a_1}{2} + j\sqrt{a_2-\frac{a_1^2}{4}}$$

and

$$ -\frac{a_1}{2} = \frac{n_1}{2^{W-1}} \qquad n_1 \in \mathbb{Z}$$

$$ a_2 = \frac{n_2}{2^{W-1}} \qquad n_2 \in \mathbb{Z} $$

Let's pick on the arc of circles orbiting around $z=\frac12$

Then ask if this can be a constant, and to answer the question show that is equal to the radius $R$ of circles orbiting around $z=0$:

$$ \Big|z_p - \tfrac12 \Big|^2 = R^2$$

$$ \left|-\frac{a_1}{2} + j\sqrt{a_2-\frac{a_1^2}{4}} - \tfrac12 \right|^2 = R^2$$

$$ \left| \frac{n_1}{2^{W-1}} + j\sqrt{\frac{n_2}{2^{W-1}}-\frac{n_1^2}{2^{2W-2}}}- \tfrac12\right|^2 = R^2$$

$$ \left|\frac{n_1}{2^{W-1}} - \tfrac12 + j\sqrt{\frac{n_2}{2^{W-1}}-\frac{n_1^2}{2^{2W-2}}} \right|^2 = R^2$$

$$ \left(\frac{n_1}{2^{W-1}} - \tfrac12 \right)^2 + \left(\sqrt{\frac{n_2}{2^{W-1}}-\frac{n_1^2}{2^{2W-2}}} \right)^2 = R^2$$

$$ \left(\frac{n_1}{2^{W-1}} - \tfrac12 \right)^2 + \frac{n_2}{2^{W-1}} - \frac{n_1^2}{2^{2W-2}} = R^2$$

$$ \frac{n_1^2}{2^{2W-2}} - \frac{n_1}{2^{W-1}} + \tfrac14 + \frac{n_2}{2^{W-1}} - \frac{n_1^2}{2^{2W-2}} = R^2$$

$$ -\frac{n_1}{2^{W-1}} + \tfrac14 + \frac{n_2}{2^{W-1}} = R^2$$

From which we get:

$$R^2 = \frac{n_2-n_1}{2^{W-1}} + \tfrac14$$

In the OP's graphic, each radius centered about the origin is associated with an increasing $n_2$, and the intersecting vertical lines are associated with an increasing $n_1$. As we move through the selected quantized values on the z-plane concentric about $z=0.5$, we see that we indeed have the case that for the adjacent quantized values on a given circle, $n_1$ and $n_2$ both increase by one, such that $n_2-n_1$ will always be constant on any given circle (centered about $z=0.5$).

Similarly solving this for the arc of circles orbiting around $z=1$ we get:

$$ \Big|z_p - 1 \Big|^2 = R^2$$

$$ \left|\frac{n_1}{2^{W-1}} - 1 + j\sqrt{\frac{n_2}{2^{W-1}}-\frac{n_1^2}{2^{2W-2}}} \right|^2 = R^2$$

$$ \left(\frac{n_1}{2^{W-1}} - 1\right)^2 + \frac{n_2}{2^{W-1}} - \frac{n_1^2}{2^{2W-2}} = R^2$$

$$ \frac{n_1^2}{2^{2W-2}} - \frac{2n_1}{2^{W-1}} + 1 + \frac{n_2}{2^{W-1}} - \frac{n_1^2}{2^{2W-2}} = R^2$$

$$ -\frac{2n_1}{2^{W-1}} + 1 + \frac{n_2}{2^{W-1}} = R^2$$

From which we get:

$$R^2 = \frac{n_2-2n_1}{2^{W-1}} + 1$$

Confirming this is constant, we see from the annotated graphic below for the case of $W=5$ that the $(n_1, n_2)$ values for the quantized locations on the closest circle to $z=1$ are $(12,9), (13,11), (14,13)$, and $(15,15)$. Note how in this case as we increment over $n_1$ from 12 to 15, $n_2$ increments in steps of two. This is in contrast to all the locations on the closest circle to $z=0.5$ where $n_2$ increases by 1 as $n_1$ increases by 1. Therefore in this case, $n_2-2n_1$ is also a constant for all these locations.

quantized poles for W=5

Further, to prove that this $R$ is the same as that centered about the origin:

We note that $R$ for the closest circle about the origin is the circle given by $n_2=1$.

The radius from the origin was established by the OP to be:

$$r = \sqrt{a_2}= \sqrt{\frac{n_2}{2^{W-1}}}= \frac{\sqrt{n_2}}{2^{(W-1)/2}}$$

$R$ as the radius of the smallest circle is $r$ with $n_2=1$, resulting in:

$$R = \frac{1}{2^{(W-1)/2}}$$

And $R^2$ is:

$$R^2 = \frac{1}{2^{W-1}}$$

Plugging this into the formula for the circles adjacent to $z=1$ results in:

$$\frac{1}{2^{W-1}} = \frac{n_2-2n_1}{2^{W-1}} + 1$$

We have already shown that the arc around $z=1$ is a constant, so we can select the final sample associated with $n_1=n_2 = 2^{W-1}-1$ (15 in our example with $W=5$) and show that the above equality holds:

$$\frac{1}{2^{W-1}} = \frac{n_2-2n_1}{2^{W-1}} + \frac{2^{W-1}}{2^{W-1}}$$

$$\frac{1}{2^{W-1}} = \frac{(2^{W-1}-1)-2(2^{W-1}-1)}{2^{W-1}} + \frac{2^{W-1}}{2^{W-1}}$$

$$\frac{1}{2^{W-1}} = \frac{(2^{W-1}-1)-(2^{W}-2)+2^{W-1}}{2^{W-1}}$$

$$\frac{1}{2^{W-1}} = \frac{2^{W-1}-1-2^{W}+2+2^{W-1}}{2^{W-1}}$$

$$\frac{1}{2^{W-1}} = \frac{1}{2^{W-1}}$$

And thus the circle of quantized roots on the z-plane about $z=1$ will always be in the mirrored locations to the circle of quantized roots on the z-plane about $z=0$. (and similarly $z=-1$.)

$\endgroup$
5
  • $\begingroup$ nice path--- I didn't want to edit it directly until you saw, but substitution for $a_1$ in third line of final group above doesn't appear to be correct? $\endgroup$ Commented Dec 28, 2022 at 13:46
  • $\begingroup$ With this correction the solution is $ (n_2-n_1)/2^{W-1) + 1/4 = R^2 $ for the vertex at $z=0.5$, and similarly $(n_2-2n_1)/2^{W-1) + 1 = R^2$ for the vertex at z=1. Where R is the distance to closest pole at these locations. Do you want me to edit your answer or do you want the fun of making the correction and checking my result? (I confirmed that works with the actual pole locations) $\endgroup$ Commented Dec 28, 2022 at 23:06
  • $\begingroup$ Feel free, @DanBoschen to show what's incorrect about the substitution. Given the definitions above. $\endgroup$ Commented Dec 29, 2022 at 2:24
  • $\begingroup$ oh, i think i see. sign problem. $$ $$ oh, and there is also a factor of 2. go ahead and fix it, Dan, if you want to. $\endgroup$ Commented Dec 29, 2022 at 2:26
  • $\begingroup$ oh dear. what have i done? $\endgroup$ Commented Dec 29, 2022 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.