In article <1326b66a-e7a1-4912-b1f1-
1455978ccb40@k17g2000yqh.googlegroups.com>, rbj@audioimagination.com 
says...

>i can't imagine that some IEEE dude hasn't already written a treatise
>about this in the 60s or 70s.  no?  maybe some old Bell System
>Technical Journal?  (*never* assume you've invented or discovered
>something novel until you check there.)

The problem was extensively studied in the 1970s. The classic IEEE book 
"Programs for Digital Signal Processing" contains a big Fortran program 
called EQIIR that handles exactly this problem and can take into account 
coefficient quantization. The program's author, G.F. Dehner, revisited 
the issue in 2003 in a paper called "Noise optimized IIR digital filter 
design: tutorial and some new aspects," Signal Processing, Volume 83,  
Issue 8  (August 2003).

http://portal.acm.org/citation.cfm?id=876820

Tim Wescott wrote:
> On Tue, 22 Dec 2009 23:04:06 -0500, Jerry Avins wrote:
> 
>> 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.
> 
> Can't be, at least not for a stable filter.  Any linear time-invariant 
> filter that's stable in the "poles strictly inside the stability region" 
> sense is also stable in the bounded-input, bounded-output sense.
> 
> If it's BIBO stable, then that means you can select your overflow level 
> to be just outside the output bounds (or your gain to _keep_ the output 
> bounds to just inside the overflow level).

Maybe Randy Yates remembers what's tickling my mind. (It was injected 
into one of our on-line arguments in which we were both right about what 
we wrote, but both wrong about what we understood the other to be 
writing.) The standard analyses -- and yours -- assume certain 
properties for the data. Someone here figured out -- Andor Bariska? -- a 
pathology that violated the standard assumptions. I'm not sure what 
structure or operation it applied to. but I clearly remember being 
astounded at the result.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Dec 23, 12:34�am, robert bristow-johnson
<r...@audioimagination.com> wrote:
>
> BTW, i might highly recommend the DF1 for cascaded biquads over the
> DF2. &#4294967295;for order N, the DF2 being canonical, requires N states and the
> cascaded DF1 requires N+2 states (not the 2N states that the naive
> think). &#4294967295;if you use a double-wide accumulator, there is only one point
> of quantization in the DF1 (two for a single DF2 stage, but if you're
> willing to carry a double precision result into the next section, you
> can make the number of quantizers N+1 for DF2 compared to N for DF1).

ooops, i forgot that N is the order (let's assume even for shits and
grins) not the number of sections which is N/2.  so there are 2
quantization points in a single DF2 section, but if you're carrying a
double precision result to the input of the following DF2 section, you
can make the total number of quantization points to be N/2 +1 compared
to N/2 for the DF1.

dotting the t's and crossing the i's is important.

r b-j

On Dec 22, 11:50&#4294967295;pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:
> Tim Wescott wrote:
> > On Tue, 22 Dec 2009 20:32:58 -0800, robert bristow-johnson wrote:
>
> >>it's not a proof, but a sorta rule of thumb that i thought made sense is
> >>to start with the pole pair (i'm gonna assume everything is complex
> >>conjugate) that are the least stable;
> > OTOH, leading with a more highly-damped pole pair would hinder energy
> > from getting through to overflow later stages.
>
> The higher Q stage is noisier then the lower Q stage. If you have low Q
> stage after high Q stage, the noise of the first stage gets filtered by
> the second stage. It is a tradeoff of noise vs overflow.

i might suggest being careful with terminology (perhaps you are, Vlad,
and if so, then i might disagree).  i consider the Q of a biquad
section to be a function solely of the poles of that section.  with
Direct Form 1 and a double-wide accumulator, i really think that the
noisiness depends on the whole frequency response, not just the
frequency response due to the poles (well, that's not right, the
quantization error for a section is filtered only by the poles - okay,
you're right for the DF1).

BTW, i might highly recommend the DF1 for cascaded biquads over the
DF2.  for order N, the DF2 being canonical, requires N states and the
cascaded DF1 requires N+2 states (not the 2N states that the naive
think).  if you use a double-wide accumulator, there is only one point
of quantization in the DF1 (two for a single DF2 stage, but if you're
willing to carry a double precision result into the next section, you
can make the number of quantizers N+1 for DF2 compared to N for DF1).
but the real reason is that if you have some nice "virtual" pole/zero
cancellation (like you would for a peak/cut parametric EQ) the DF2
applies poles first and inflates your signal up to a high level (where
clipping might happen unless you reduce the input signal thus lowering
the "S" in S/N) before the zeros get to beat it back down.  not a
problem in DF1.

also, surrounding the quantizer in a DF1 with simple noise shaping
with a zero at z=1 (a.k.a. "fraction saving" if your quantizer is
always rounding down or truncating) is a piece of cake.  it's what i
used in that simple DC blocker trick on Grant's website.

r b-j

On Dec 22, 11:41&#4294967295;pm, Tim Wescott <t...@seemywebsite.com> wrote:
>
>
> OTOH, leading with a more highly-damped pole pair would hinder energy
> from getting through to overflow later stages.

the idea of matching such poles with the zeros that would do the most
to "dampen" their resonance seems directed to that purpose.

dunno what you would do with cascaded all-pole biquad filters.
whether it's good to put the highest Q first or last.  i might think
it would be good to put the highest Q all-pole filter last.

all this assumes that each biquad stage has 5 coefficients so that you
can apportion the "right amount" of gain for each section and sweep
whatever leftover makeup gain into the last section.  i might put into
the first section the most constant gain possible so that from the
cascade input to the output of that particular section, no frequency
has gain exceeding 0 dB.  do that until the last section, then the
leftover gain would be whatever is needed to satisfy the spec for the
whole damn thang.

so maybe the flattest or broadest or least sharp magnitude response
goes first and each section has DC gain adjusted so that the maximum
gain (at any frequency) from the overall input to the output of that
section is 0 dB.

i can't imagine that some IEEE dude hasn't already written a treatise
about this in the 60s or 70s.  no?  maybe some old Bell System
Technical Journal?  (*never* assume you've invented or discovered
something novel until you check there.)


r b-j

Tim Wescott wrote:

> On Tue, 22 Dec 2009 20:32:58 -0800, robert bristow-johnson wrote:
> 
>>it's not a proof, but a sorta rule of thumb that i thought made sense is
>>to start with the pole pair (i'm gonna assume everything is complex
>>conjugate) that are the least stable;

> OTOH, leading with a more highly-damped pole pair would hinder energy 
> from getting through to overflow later stages.

The higher Q stage is noisier then the lower Q stage. If you have low Q 
stage after high Q stage, the noise of the first stage gets filtered by 
the second stage. It is a tradeoff of noise vs overflow.

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

robert bristow-johnson wrote:


> it's not a proof, but a sorta rule of thumb that i thought made sense
> is to start with the pole pair (i'm gonna assume everything is complex
> conjugate) that are the least stable; the poles closest to the unit
> circle.  group those poles with the pair of zeros that are closest to
> the poles.  that's your first section.  strike that pole pair and zero
> pair off the list and do it all over again for the next section and so
> on.

Yes, there are rules of thumb like alternate LPF and HPF sections, in 
the order from high Q to low Q, put together poles and zeroes with the 
closest frequencies. Those rules guarantee the result not too bad, 
however it may not be the very best either.

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

Jerry Avins  <jya@ieee.org> wrote:

>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. 

Not true.  A IIR lattice filter for a stable transfer function
using saturating arithmetic will never overflow, or otherwise exhibit 
instabilities, regardless of input or initial state.

(In Matlab parlance, said lattice filter is called an "ARMA-MA"
filter.)

They are historically unpopular because they have twice as
many multiplies as a transversal filter; but given how
cheap arithmetic is these days, I think they are due for
a resurgence in popularity.

Steve

On Tue, 22 Dec 2009 20:32:58 -0800, robert bristow-johnson wrote:

> On Dec 22, 10:53&nbsp;pm, Tim Wescott <t...@seemywebsite.com> wrote:
>> 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.
>>
> ...
>>
>> > 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 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.
> 
> it's not a proof, but a sorta rule of thumb that i thought made sense is
> to start with the pole pair (i'm gonna assume everything is complex
> conjugate) that are the least stable; the poles closest to the unit
> circle.  group those poles with the pair of zeros that are closest to
> the poles.  that's your first section.  strike that pole pair and zero
> pair off the list and do it all over again for the next section and so
> on.
> 
> r b-j

OTOH, leading with a more highly-damped pole pair would hinder energy 
from getting through to overflow later stages.

-- 
www.wescottdesign.com

On Dec 22, 10:53&#4294967295;pm, Tim Wescott <t...@seemywebsite.com> wrote:
> 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.
>
...
>
> > 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 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.

it's not a proof, but a sorta rule of thumb that i thought made sense
is to start with the pole pair (i'm gonna assume everything is complex
conjugate) that are the least stable; the poles closest to the unit
circle.  group those poles with the pair of zeros that are closest to
the poles.  that's your first section.  strike that pole pair and zero
pair off the list and do it all over again for the next section and so
on.

r b-j