IIR Form to prevent Limit Cycles?

Started by sparafucile17 December 18, 2007
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