Forums

Maximizing dynamic range of fixed point IIR filter

Started by Vladimir Vassilevsky 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?

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. &#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;