Maximizing dynamic range of fixed point IIR filter

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?

Vladimir Vassilevsky
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?
> 
> Vladimir Vassilevsky
> 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 
disproving it instead!

-- 
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 
> disproving it instead!

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.

Vladimir Vassilevsky
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 
>> disproving it instead!
> 
> 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.
�����������������������������������������������������������������������

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
>> disproving it instead!
>
> 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.
>
> Vladimir Vassilevsky
> 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
>> disproving it instead!
> 
> 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.
> 
> Vladimir Vassilevsky
> 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.



Vladimir Vassilevsky
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 
>> disproving it instead!
> 
> 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.
�����������������������������������������������������������������������