IIR Form to prevent Limit Cycles?

Hello all,

Does anyone know an IIR form that would prevent/reduce the effects of
limit cycles?  Just so everyone is clear about what I mean when I say
"limit cycles":  

It is the phenomena whereby fixed point DSP's cannot quantize very precise
multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
cause what appears to be moments of instabilities at very low input
levels. (only a couple of lsb's toggling) a.k.a. small scale limit
cycles.

In the audio processing wold, I've seen this manifest itself as a
subwoofer grumbling when several low cutoff LPF's were used in series.  It
was essentially reacting to the noise floor of the A/D converters and
providing a signal much louder than the input.

I have heard from another DSP Engineer that there is an IIR form that
reduces the effect of limit cycles so that it is barely noticable.  Today
we use double-precision data storage to eliminate this problem, but I want
to remove this MIPS hit if possible.

Any ideas?

Jeff

sparafucile17 wrote:
> Hello all,
> 
> Does anyone know an IIR form that would prevent/reduce the effects of
> limit cycles?  Just so everyone is clear about what I mean when I say
> "limit cycles":  
> 
> It is the phenomena whereby fixed point DSP's cannot quantize very precise
> multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
> cause what appears to be moments of instabilities at very low input
> levels. (only a couple of lsb's toggling) a.k.a. small scale limit
> cycles.
> 
> In the audio processing wold, I've seen this manifest itself as a
> subwoofer grumbling when several low cutoff LPF's were used in series.  It
> was essentially reacting to the noise floor of the A/D converters and
> providing a signal much louder than the input.
> 
> I have heard from another DSP Engineer that there is an IIR form that
> reduces the effect of limit cycles so that it is barely noticable.  Today
> we use double-precision data storage to eliminate this problem, but I want
> to remove this MIPS hit if possible.

Search for "fraction saving" in this newsgroup.

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

Jerry Avins wrote:
> sparafucile17 wrote:
>> Hello all,
>>
>> Does anyone know an IIR form that would prevent/reduce the effects of
>> limit cycles?  Just so everyone is clear about what I mean when I say
>> "limit cycles": 
>> It is the phenomena whereby fixed point DSP's cannot quantize very 
>> precise
>> multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
>> cause what appears to be moments of instabilities at very low input
>> levels. (only a couple of lsb's toggling) a.k.a. small scale limit
>> cycles.
>>
>> In the audio processing wold, I've seen this manifest itself as a
>> subwoofer grumbling when several low cutoff LPF's were used in 
>> series.  It
>> was essentially reacting to the noise floor of the A/D converters and
>> providing a signal much louder than the input.
>>
>> I have heard from another DSP Engineer that there is an IIR form that
>> reduces the effect of limit cycles so that it is barely noticable.  Today
>> we use double-precision data storage to eliminate this problem, but I 
>> want
>> to remove this MIPS hit if possible.
> 
> Search for "fraction saving" in this newsgroup.

That may greatly greatly increase the compute requirement, by stretching 
the word length beyond the machine's. Adding TPD noise to each bi-quad 
(assuming it's a biquad structured filter) can be effective amd more 
efficient.

Steve

On Dec 18, 10:44 pm, Steve Underwood <ste...@dis.org> wrote:
> Jerry Avins wrote:
> > sparafucile17 wrote:
> >> Hello all,
>
> >> Does anyone know an IIR form that would prevent/reduce the effects of
> >> limit cycles?  Just so everyone is clear about what I mean when I say
> >> "limit cycles":
> >> It is the phenomena whereby fixed point DSP's cannot quantize very
> >> precise
> >> multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
> >> cause what appears to be moments of instabilities at very low input
> >> levels. (only a couple of lsb's toggling) a.k.a. small scale limit
> >> cycles.
>
> >> In the audio processing wold, I've seen this manifest itself as a
> >> subwoofer grumbling when several low cutoff LPF's were used in
> >> series.  It
> >> was essentially reacting to the noise floor of the A/D converters and
> >> providing a signal much louder than the input.
>
> >> I have heard from another DSP Engineer that there is an IIR form that
> >> reduces the effect of limit cycles so that it is barely noticable.  Today
> >> we use double-precision data storage to eliminate this problem, but I
> >> want
> >> to remove this MIPS hit if possible.
>
> > Search for "fraction saving" in this newsgroup.
>
> That may greatly greatly increase the compute requirement, by stretching
> the word length beyond the machine's. Adding TPD noise to each bi-quad
> (assuming it's a biquad structured filter) can be effective amd more
> efficient.

i don't quite get it, Steve.  would not a LSW (least significant word)
be needed in either case?  at least with the old 56K (or with the
current SHArC, if you use the 80-bit accumulator), saving the LSW and
restoring it (zero extended) for the next sample's accumulation, is
much cheaper than computing two decent rectangular samples of noise
(so to add them together to get TPD).

one reason for "fraction-saving" (otherwize known as: round-to-neg-
infinity truncation surrounded by first-order noise shaping with a
single zero at z=1 in the transfer function for quantization error to
output) is that it requires so little complexity in the
implementation.

r b-j

robert bristow-johnson wrote:
> On Dec 18, 10:44 pm, Steve Underwood <ste...@dis.org> wrote:
>> Jerry Avins wrote:
>>> sparafucile17 wrote:
>>>> Hello all,
>>>> Does anyone know an IIR form that would prevent/reduce the effects of
>>>> limit cycles?  Just so everyone is clear about what I mean when I say
>>>> "limit cycles":
>>>> It is the phenomena whereby fixed point DSP's cannot quantize very
>>>> precise
>>>> multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
>>>> cause what appears to be moments of instabilities at very low input
>>>> levels. (only a couple of lsb's toggling) a.k.a. small scale limit
>>>> cycles.
>>>> In the audio processing wold, I've seen this manifest itself as a
>>>> subwoofer grumbling when several low cutoff LPF's were used in
>>>> series.  It
>>>> was essentially reacting to the noise floor of the A/D converters and
>>>> providing a signal much louder than the input.
>>>> I have heard from another DSP Engineer that there is an IIR form that
>>>> reduces the effect of limit cycles so that it is barely noticable.  Today
>>>> we use double-precision data storage to eliminate this problem, but I
>>>> want
>>>> to remove this MIPS hit if possible.
>>> Search for "fraction saving" in this newsgroup.
>> That may greatly greatly increase the compute requirement, by stretching
>> the word length beyond the machine's. Adding TPD noise to each bi-quad
>> (assuming it's a biquad structured filter) can be effective amd more
>> efficient.
> 
> i don't quite get it, Steve.  would not a LSW (least significant word)
> be needed in either case?  at least with the old 56K (or with the
> current SHArC, if you use the 80-bit accumulator), saving the LSW and
> restoring it (zero extended) for the next sample's accumulation, is
> much cheaper than computing two decent rectangular samples of noise
> (so to add them together to get TPD).
> 
> one reason for "fraction-saving" (otherwize known as: round-to-neg-
> infinity truncation surrounded by first-order noise shaping with a
> single zero at z=1 in the transfer function for quantization error to
> output) is that it requires so little complexity in the
> implementation.

Its also known as "don't throw away what you aren't really forced to". 
When you have long enough registers you certainly aren't forced to throw 
information away, and you are a fool if you do. However, this does 
assumes you can keep all the bits through all the stages. When you need 
to store intermediate results things can get messier. I could have 
expressed myself more clearly, I guess. The reason I said about 
dithering each bi-quad is that's typically the level at which you have 
to store values in smaller spaces, or suffer big overheads.

Steve

jeff,

approach 1.

   a second order IIR section that is free of zero input limit
   cycles is given on page 726 of sanjit k mitra book. fig 12.54.
   3rd edition, digital signal processing. I am not too confident
   about this structure as limit cycle oscillations are caused
   by the quantizers in the structure and not by the structures
   themselves. limit cycle oscillations are caused mainly by 2's
   complement arithmetic, either when the iir coefficients are negative
   (which is mostly the case), or if the input goes both positive and
   negative. normally when we floor negative numbers their bias 
   increases more towards minus infinity. This is the prime reason
   behind the oscillations. Hence choosing a structure won't help.
   You need to change the way how you would quantize things in the
   loop. Hence I would recommend approach 2.

approach 2.

   limit cycles can completely be eliminated by using a "fix quantizer"
   fix is a terminology used by matlab. you can type "help fix" for more
   details. Fix quantizer will floor the data towards 0 for both positive
   and negative numbers. This flooring towards 0 of both positive and 
   negative data causes dead band near origin which results in some amount
  
   harmonic distortion.

   you need to perform SNR analysis and check if you are ok with THD.
   providing some extra fractional bits helps in reducing or eliminating
   harmonic distortion.

Regards
Bharat Pathak

Founder and CEO
Arithos Designs
www.arithos.com
   



>Hello all,
>
>Does anyone know an IIR form that would prevent/reduce the effects of
>limit cycles?  Just so everyone is clear about what I mean when I say
>"limit cycles":  
>
>It is the phenomena whereby fixed point DSP's cannot quantize very
precise
>multiplies within a feedback (a-terms) mac's of an IIR filter.  This can
>cause what appears to be moments of instabilities at very low input
>levels. (only a couple of lsb's toggling) a.k.a. small scale limit
>cycles.
>
>In the audio processing wold, I've seen this manifest itself as a
>subwoofer grumbling when several low cutoff LPF's were used in series. 
It
>was essentially reacting to the noise floor of the A/D converters and
>providing a signal much louder than the input.
>
>I have heard from another DSP Engineer that there is an IIR form that
>reduces the effect of limit cycles so that it is barely noticable. 
Today
>we use double-precision data storage to eliminate this problem, but I
want
>to remove this MIPS hit if possible.
>
>Any ideas?
>
>Jeff
>

"sparafucile17" <sparafucile17@hotmail.com> wrote in message
news:MaCdnYFVzoMYovXanZ2dnUVZ_ommnZ2d@giganews.com...
> Hello all,
>
> Does anyone know an IIR form that would prevent/reduce the effects of
> limit cycles?

There can't be such thing. However:

1. You can implement noise shaping (as suggested by Jerry and RBJ)
2. You can dither (as suggested by Steve)
3. You can use some sort of nonlinear processing (noise gate or crossover
notch)
4. You can do the FIR filter instead of IIR

What would be the preferred way depends on what is your hardware and what
are you trying to accomplish.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

>
>"sparafucile17" <sparafucile17@hotmail.com> wrote in message
>news:MaCdnYFVzoMYovXanZ2dnUVZ_ommnZ2d@giganews.com...
>> Hello all,
>>
>> Does anyone know an IIR form that would prevent/reduce the effects of
>> limit cycles?
>
>There can't be such thing. However:
>
>1. You can implement noise shaping (as suggested by Jerry and RBJ)
>2. You can dither (as suggested by Steve)
>3. You can use some sort of nonlinear processing (noise gate or
crossover
>notch)
>4. You can do the FIR filter instead of IIR
>
>What would be the preferred way depends on what is your hardware and
what
>are you trying to accomplish.
>
>Vladimir Vassilevsky
>DSP and Mixed Signal Consultant
>www.abvolt.com
>
>

Thanks guys, I like where this discussion is going.  Just to re-cap, I am
currently implementing a double-precision data storage to solve the
problem.  My data/coefficients are 28-bit and the accumulator is 56-bits. 
So when the output sample from the biquad is stored I use the entire 56-bit
value.

This requires one additional data store and two more MAC's.  See below:

[single-precision data storage] ==> 6 cycles
MAC B0
MAC B1
MAC B2
MAC A1
MAC A2
STORE ACCUM-HI

[double-precision data storage] ==> 9 cycles (* are extra precision
instr.)
MAC B0
MAC B1
MAC B2
MAC A1-HI
MAC A1-LO*
MAC A2-HI
MAC A2-LO*
STORE ACCUM-HI
STORE ACCUM-LO*


This method works for my application but can be MIPS intensive.  I'm using
up to 100 biquads so this 3 cycle difference translates into 300 cycles!
and this is huge for me.

Thus it would be nice to keep the 6 cycle biquad but prevent small-scale
limit cycles from occuring.  So any solution for me needs to be less than
a 9 cycle biquad.  I have used the round-to-0 approach at my former
employer to solve the same problem.  I just wonder if I can do the same
but less than 3 cycles!!

I will also quiz one of our European branch of DSP guys to see if they can
elaborate on the *new IIR form* (That's who I heard this nasty rumor from)

Thanks,
Jeff

On Dec 19, 7:21 am, "bharat pathak" <bha...@arithos.com> wrote:
>
> approach 1.
>
>    a second order IIR section that is free of zero input limit
>    cycles is given on page 726 of sanjit k mitra book. fig 12.54.
>    3rd edition, digital signal processing. I am not too confident
>    about this structure as limit cycle oscillations are caused
>    by the quantizers in the structure and not by the structures
>    themselves. limit cycle oscillations are caused mainly by 2's
>    complement arithmetic, either when the iir coefficients are negative
>    (which is mostly the case), or if the input goes both positive and
>    negative. normally when we floor negative numbers their bias
>    increases more towards minus infinity. This is the prime reason
>    behind the oscillations. Hence choosing a structure won't help.
>    You need to change the way how you would quantize things in the
>    loop.

i don't have this book.  could you draw out the structure using "ASCII-
art" or spell it out with pseudo-code (or C code or MATLAB/Octave
code)?

> ... Hence I would recommend approach 2.
>
> approach 2.
>
>    limit cycles can completely be eliminated by using a "fix quantizer"
>    fix is a terminology used by matlab. you can type "help fix" for more
>    details. Fix quantizer will floor the data towards 0 for both positive
>    and negative numbers.

yes, that will eliminate the one problem of the filter getting stuck
on a non-zero output even after the input goes to zero and is held at
zero.

> This flooring towards 0 of both positive and
>    negative data causes dead band near origin which results in some amount
>    harmonic distortion.

yes, it has crossover distortion that is less of a problem for loud
signals and more of a problem with very quiet signals.  it is the crap
that you get with signals fading to silence which was one of the first
motivations for additive dither.

i still think that fraction saving is the cheapest means to solve the
specific problem of limit-cycles in an IIR causing your output to be
stuck to a non-zero value even when dead silence is going in.  unless
your hardware is designed to do "round-toward-zero", actually rounding
toward zero requires either sign-magnitude arithmetic or at least a
couple of conditional execution statements which DSPs are not well
suited for.




On Dec 19, 10:19 am, "sparafucile17" <sparafucil...@hotmail.com>
wrote:
> My data/coefficients are 28-bit and the accumulator is 56-bits.
> So when the output sample from the biquad is stored I use the entire 56-bit
> value.
>
> This requires one additional data store and two more MAC's.  See below:
>
> [single-precision data storage] ==> 6 cycles
> MAC B0
> MAC B1
> MAC B2
> MAC A1
> MAC A2
> STORE ACCUM-HI
>
> [double-precision data storage] ==> 9 cycles (* are extra precision
> instr.)
> MAC B0
> MAC B1
> MAC B2
> MAC A1-HI
> MAC A1-LO*
> MAC A2-HI
> MAC A2-LO*
> STORE ACCUM-HI
> STORE ACCUM-LO*
>
> This method works for my application but can be MIPS intensive.  I'm using
> up to 100 biquads so this 3 cycle difference translates into 300 cycles!

i don't know your instruction set (is this the ADI Sigma DSP?) but
fraction saving really *is* cheap.  consider this as pseudo-code
(since i dunno the instruction set)

 CLEAR ACCUM-HI            (perhaps this won't be necessary)
 RESTORE ACCUM-LO      (whatever you stored at the last sample)
 MAC B0
 MAC B1
 MAC B2
 MAC A1
 MAC A2
 STORE ACCUM-HI           (this truncated word is your output sample)
 STORE ACCUM-LO

that's it.  that's all you have to do to implement "fraction saving".


r b-j

robert bristow-johnson wrote:


>>This flooring towards 0 of both positive and
>>   negative data causes dead band near origin which results in some amount
>>   harmonic distortion.
> 
> 
> yes, it has crossover distortion that is less of a problem for loud
> signals and more of a problem with very quiet signals.  it is the crap
> that you get with signals fading to silence which was one of the first
> motivations for additive dither.
> 
> i still think that fraction saving is the cheapest means to solve the
> specific problem of limit-cycles in an IIR causing your output to be
> stuck to a non-zero value even when dead silence is going in.  unless
> your hardware is designed to do "round-toward-zero",


The noise shaping has to be done at every biquad stage. The nonlinear 
thing or a noise gate can be done only once for the whole system, hence 
it could be simpler.

But usually the problem with IIRs is not only because of the limit 
cycles. The loss of precision is bad, and the only way to deal with that 
is the noise shaping. BTW, BlackFin architecture is very inconvenient 
for that purpose.


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