# Maximizing dynamic range of fixed point IIR filter

Started by December 22, 2009
```Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
typical implementation would be a cascade of biquads. So we factor P(z)
and Q(z) and distribute poles and zeroes between the stages.

The dynamic range of a filter is limited by overflow at the top, and by
quantization artifacts at the bottom. We can try all variants of
assignment of poles and zeroes to different stages to maximize the
dynamic range from rms quantization noise to full scale sine wave at the
"worst" frequency. So far so good.

However, this doesn't tell if some stage of filter can overflow if the
input is an arbitrary non-harmonic waveform. How could we optimize the
filter for this case?

DSP and Mixed Signal Design Consultant
http://www.abvolt.com
```
```On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:

> Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
> typical implementation would be a cascade of biquads. So we factor P(z)
> and Q(z) and distribute poles and zeroes between the stages.
>
> The dynamic range of a filter is limited by overflow at the top, and by
> quantization artifacts at the bottom. We can try all variants of
> assignment of poles and zeroes to different stages to maximize the
> dynamic range from rms quantization noise to full scale sine wave at the
> "worst" frequency. So far so good.
>
> However, this doesn't tell if some stage of filter can overflow if the
> input is an arbitrary non-harmonic waveform. How could we optimize the
> filter for this case?
>
> DSP and Mixed Signal Design Consultant http://www.abvolt.com

I _think_ that if the transfer function from input to each state in the
filter is less than unity (or whatever the critical gain is necessary to
prevent overflow) for all possible frequencies, you can't overflow.

But I don't _know_ -- I'd have to try to prove it, and may end up

--
www.wescottdesign.com
```
```
Tim Wescott wrote:
> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>
>
>>Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
>>typical implementation would be a cascade of biquads. So we factor P(z)
>>and Q(z) and distribute poles and zeroes between the stages.
>>
>>The dynamic range of a filter is limited by overflow at the top, and by
>>quantization artifacts at the bottom. We can try all variants of
>>assignment of poles and zeroes to different stages to maximize the
>>dynamic range from rms quantization noise to full scale sine wave at the
>>"worst" frequency. So far so good.
>>
>>However, this doesn't tell if some stage of filter can overflow if the
>>input is an arbitrary non-harmonic waveform. How could we optimize the
>>filter for this case?
>>
> I _think_ that if the transfer function from input to each state in the
> filter is less than unity (or whatever the critical gain is necessary to
> prevent overflow) for all possible frequencies, you can't overflow.
> But I don't _know_ -- I'd have to try to prove it, and may end up

Unfortunately, not. Think of a highpass filter with the gain of 1 and
the data range is +/-1.  Let the input -1,-1,-1....-1, +1, so here is
overflow.

DSP and Mixed Signal Design Consultant
http://www.abvolt.com

```
```Vladimir Vassilevsky wrote:
>
>
> Tim Wescott wrote:
>> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>>
>>
>>> Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
>>> typical implementation would be a cascade of biquads. So we factor P(z)
>>> and Q(z) and distribute poles and zeroes between the stages.
>>>
>>> The dynamic range of a filter is limited by overflow at the top, and by
>>> quantization artifacts at the bottom. We can try all variants of
>>> assignment of poles and zeroes to different stages to maximize the
>>> dynamic range from rms quantization noise to full scale sine wave at the
>>> "worst" frequency. So far so good.
>>>
>>> However, this doesn't tell if some stage of filter can overflow if the
>>> input is an arbitrary non-harmonic waveform. How could we optimize the
>>> filter for this case?
>>>
>> I _think_ that if the transfer function from input to each state in
>> the filter is less than unity (or whatever the critical gain is
>> necessary to prevent overflow) for all possible frequencies, you can't
>> overflow.
>> But I don't _know_ -- I'd have to try to prove it, and may end up
>
> Unfortunately, not. Think of a highpass filter with the gain of 1 and
> the data range is +/-1.  Let the input -1,-1,-1....-1, +1, so here is
> overflow.

I think I remember a proof here that there are pathological waveforms --
not the result of sampling -- that will cause any IIR structure to
overflow. The worst case for a transversal filter is easy to demonstrate
but unrealistically stringent.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```Vladimir Vassilevsky <nospam@nowhere.com> writes:

> Tim Wescott wrote:
>> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>>
>>
>>>Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
>>>typical implementation would be a cascade of biquads. So we factor P(z)
>>>and Q(z) and distribute poles and zeroes between the stages.
>>>
>>>The dynamic range of a filter is limited by overflow at the top, and by
>>>quantization artifacts at the bottom. We can try all variants of
>>>assignment of poles and zeroes to different stages to maximize the
>>>dynamic range from rms quantization noise to full scale sine wave at the
>>>"worst" frequency. So far so good.
>>>
>>>However, this doesn't tell if some stage of filter can overflow if the
>>>input is an arbitrary non-harmonic waveform. How could we optimize the
>>>filter for this case?
>>>
>> I _think_ that if the transfer function from input to each state in
>> the filter is less than unity (or whatever the critical gain is
>> necessary to prevent overflow) for all possible frequencies, you
>> can't overflow.
>> But I don't _know_ -- I'd have to try to prove it, and may end up
>
> Unfortunately, not. Think of a highpass filter with the gain of 1 and
> the data range is +/-1.  Let the input -1,-1,-1....-1, +1, so here is
> overflow.
>
> DSP and Mixed Signal Design Consultant
> http://www.abvolt.com
>

So if you're talking about a stage with *any* poles p_k, then if you
apply an input at z=p_k, you will get infinite output. A special case of
that is your HPF example, where you can apply this patholgical input
with finite amplitude input since the pole is on the unit circle. In
that case, you're hosed.

For other poles *inside* the unit circle, could you not try to work
backwards? You know that in that case, you need to apply an
exponentially increasing input (s=exp(a+jw)) envelope but your input
will necessarily saturate on the number of input bits.  Could you bound
the gain due to the pole as you reach clipping by computing the impulse
response to the saturated exponential input at z=p_k?  Not elegant, not
proved, but it might work.

- Kenn

```
```On Tue, 22 Dec 2009 17:35:26 -0600, Vladimir Vassilevsky wrote:

> Tim Wescott wrote:
>> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>>
>>
>>>Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
>>>typical implementation would be a cascade of biquads. So we factor P(z)
>>>and Q(z) and distribute poles and zeroes between the stages.
>>>
>>>The dynamic range of a filter is limited by overflow at the top, and by
>>>quantization artifacts at the bottom. We can try all variants of
>>>assignment of poles and zeroes to different stages to maximize the
>>>dynamic range from rms quantization noise to full scale sine wave at
>>>the "worst" frequency. So far so good.
>>>
>>>However, this doesn't tell if some stage of filter can overflow if the
>>>input is an arbitrary non-harmonic waveform. How could we optimize the
>>>filter for this case?
>>>
>> I _think_ that if the transfer function from input to each state in the
>> filter is less than unity (or whatever the critical gain is necessary
>> to prevent overflow) for all possible frequencies, you can't overflow.
>> But I don't _know_ -- I'd have to try to prove it, and may end up
>
> Unfortunately, not. Think of a highpass filter with the gain of 1 and
> the data range is +/-1.  Let the input -1,-1,-1....-1, +1, so here is
> overflow.
>
> DSP and Mixed Signal Design Consultant http://www.abvolt.com

Oh _fine_.

I thought "oh just find the transfer function from input to state for
each state, then try the inverse of that transfer function as an input"
-- so you'd get an impulse.

But I hardly think that's going to get you where you want to go, either.

--
www.wescottdesign.com
```
```On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:

> Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
> typical implementation would be a cascade of biquads. So we factor P(z)
> and Q(z) and distribute poles and zeroes between the stages.
>
> The dynamic range of a filter is limited by overflow at the top, and by
> quantization artifacts at the bottom. We can try all variants of
> assignment of poles and zeroes to different stages to maximize the
> dynamic range from rms quantization noise to full scale sine wave at the
> "worst" frequency. So far so good.
>
> However, this doesn't tell if some stage of filter can overflow if the
> input is an arbitrary non-harmonic waveform. How could we optimize the
> filter for this case?

Oh wait - I have it.  You didn't even distract me from paying work (just
a fun model airplane project, you b&^%\$#!).

For any given linear shift-invariant causal system that starts at rest,
the maximum value that it's output can ever reach for an input that is
subject to a bound on its absolute value is the sum of the absolute
values of the samples of its impulse response times the bound on the
input.  Why?  Because the best input you could choose to overload the
thing would be a time-inverted version of it's impulse response, run
through the sign function and multiplied by the worst-case bounds.  This
would result in an ever-growing output culminating at a sample whose
value is the afore-mentioned sum.

So find the impulse response from input to each state, then sum the
absolute values, then do the math.

This time I'm right.  Really.  I'm so sure that I'm right that if I'm
wrong and you come to the _right_ part of Oregon* this time I'll buy you
a beer.

In your case of H = (z-1)/z the impulse response is +1, -1, the sum of
the absolute values is 2, so you'd have to either (a) bound the inputs to
+/- 1/2, or (b) halve the transfer function.

My transfer function idea won't work because it'd be guaranteeing total
energy (via Parseval's Theorem), but that says little about crest factor.

* McMinnamin's Oregon City is the _right_ part of Oregon.

--
www.wescottdesign.com
```
```
Tim Wescott wrote:

> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>
>
>>The dynamic range of a filter is limited by overflow at the top, and by
>>quantization artifacts at the bottom. We can try all variants of
>>assignment of poles and zeroes to different stages to maximize the
>>dynamic range from rms quantization noise to full scale sine wave at the
>>"worst" frequency. So far so good.
>>
>>However, this doesn't tell if some stage of filter can overflow if the
>>input is an arbitrary non-harmonic waveform. How could we optimize the
>>filter for this case?
>
>
> So find the impulse response from input to each state, then sum the
> absolute values, then do the math.
>
> This time I'm right.  Really.

Yes!

1. Find the impulse response of stage #1, set stage #1 gain accordingly.
2. Find the impulse response of stages #1 + #2, set stage #2 gain
accordingly.
3. Find the impulse response of stages #1 + #2 + #3, set stage #3 gain
accordingly.

So on, so forth. The system is guaranteed not to overflow for any input.

> I'm so sure that I'm right that if I'm
> wrong and you come to the _right_ part of Oregon* this time I'll buy you
> a beer.

It's my turn to buy beers. If I won't be in Oregon before April, I hope
to see you at comp.dsp conferrence (www.compdsp.com) in Kansas City.

DSP and Mixed Signal Design Consultant
http://www.abvolt.com

```
```On Tue, 22 Dec 2009 20:50:42 -0600, Vladimir Vassilevsky wrote:

> Tim Wescott wrote:
>
>> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>>
>>
>>>The dynamic range of a filter is limited by overflow at the top, and by
>>>quantization artifacts at the bottom. We can try all variants of
>>>assignment of poles and zeroes to different stages to maximize the
>>>dynamic range from rms quantization noise to full scale sine wave at
>>>the "worst" frequency. So far so good.
>>>
>>>However, this doesn't tell if some stage of filter can overflow if the
>>>input is an arbitrary non-harmonic waveform. How could we optimize the
>>>filter for this case?
>>
>>
>> So find the impulse response from input to each state, then sum the
>> absolute values, then do the math.
>>
>> This time I'm right.  Really.
>
> Yes!
>
> 1. Find the impulse response of stage #1, set stage #1 gain accordingly.
> 2. Find the impulse response of stages #1 + #2, set stage #2 gain
> accordingly.
> 3. Find the impulse response of stages #1 + #2 + #3, set stage #3 gain
> accordingly.
>
> So on, so forth. The system is guaranteed not to overflow for any input.
>
>> I'm so sure that I'm right that if I'm wrong and you come to the
>> _right_ part of Oregon* this time I'll buy you a beer.
>
> It's my turn to buy beers. If I won't be in Oregon before April, I hope
> to see you at comp.dsp conferrence (www.compdsp.com) in Kansas City.
>
I suppose the next step is to apportion the stages so that the gains can
remain as high as possible without allowing overflow -- I'll bet that's
not as trivial.

--
www.wescottdesign.com
```
```Vladimir Vassilevsky wrote:
>
>
> Tim Wescott wrote:
>> On Tue, 22 Dec 2009 13:59:28 -0600, Vladimir Vassilevsky wrote:
>>
>>
>>> Let's say we need to implement H(z) = P(z)/Q(z) in the fixed point. The
>>> typical implementation would be a cascade of biquads. So we factor P(z)
>>> and Q(z) and distribute poles and zeroes between the stages.
>>>
>>> The dynamic range of a filter is limited by overflow at the top, and by
>>> quantization artifacts at the bottom. We can try all variants of
>>> assignment of poles and zeroes to different stages to maximize the
>>> dynamic range from rms quantization noise to full scale sine wave at the
>>> "worst" frequency. So far so good.
>>>
>>> However, this doesn't tell if some stage of filter can overflow if the
>>> input is an arbitrary non-harmonic waveform. How could we optimize the
>>> filter for this case?
>>>
>> I _think_ that if the transfer function from input to each state in
>> the filter is less than unity (or whatever the critical gain is
>> necessary to prevent overflow) for all possible frequencies, you can't
>> overflow.
>> But I don't _know_ -- I'd have to try to prove it, and may end up
>
> Unfortunately, not. Think of a highpass filter with the gain of 1 and
> the data range is +/-1.  Let the input -1,-1,-1....-1, +1, so here is
> overflow.

I think I remember a proof here that there are pathological waveforms --
not the result of sampling -- that will cause any IIR structure to
overflow. The worst case for a transversal filter is easy to demonstrate
but unrealistically stringent.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```