Newbie needs help optimizing quantized FIR LPF coefficients

Hi,

I want to implement a speed-critical FIR LPF (order about 50-60) in a
16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
could overflow with bad results if I don't scale down the coefficients
so the peak value is about 7000 (decimal). I've installed SciLab
hoping to find a way to optimize the coefficients, but I can't find
anything in Signals that directly relates. Is there a toolbox, or some
SciLab code somewhere, or MatLab code I could convert? Or some other
place to get a clue?

Tony (remove the "_" to reply by email)

On Tue, 26 Oct 2004 19:04:01 +1000, Tony <tony_roe@tpg.com.au> wrote:

>Hi,
>
>I want to implement a speed-critical FIR LPF (order about 50-60) in a
>16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
>could overflow with bad results if I don't scale down the coefficients
>so the peak value is about 7000 (decimal). I've installed SciLab
>hoping to find a way to optimize the coefficients, but I can't find
>anything in Signals that directly relates. Is there a toolbox, or some
>SciLab code somewhere, or MatLab code I could convert? Or some other
>place to get a clue?
>
>Tony (remove the "_" to reply by email)

Hi,
  If I understand your question, can you not just 
multiply all your coefficients by a factor that's 
less than one?  These will make all your 
coefficients smaller and reduce the amplitude 
of your filter's output.

Now, please realize that
reducing the coefficients (all by the same factor) 
will aggrevate the "quantized" nature of the coefficients 
and degrade your stopband attenuation.   So you 
must carefully model (simulate) the effect of that 
increased quantization of the coefficients.
If your new coefficients don't satisfy your desired 
stopband attenuation, you'll just have to increase 
the number of coefficients (increase the number 
of taps).

Have you considered using a "cascade arrangement" of 
lower-order FIR filters?
Will you be performing any decimation or 
interpolation in your system?

[-Rick-]

Hi Tony,

Tony wrote:

>Hi,
>
>I want to implement a speed-critical FIR LPF (order about 50-60) in a
>16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
>could overflow with bad results if I don't scale down the coefficients
>so the peak value is about 7000 (decimal). I've installed SciLab
>hoping to find a way to optimize the coefficients, but I can't find
>anything in Signals that directly relates. Is there a toolbox, or some
>SciLab code somewhere, or MatLab code I could convert? Or some other
>place to get a clue?
>
>Tony (remove the "_" to reply by email)
>  
>
Where does the number 7000 come from? You make the problem sound worse 
than it is. Remember that overflows in additions are reversible by later 
subtractions. That is, a long string of additions whose final result 
does not exceed 32 bits will be correct, even if lots of overflowing 
occurs at the intermediate stages. As long as the overall gain of your 
filter does not exceed one at any frequency, the final result will be 
OK. If you are using a filter design tool, it most probably draws a 
frequency response plot for you. It should be easy to see from that if 
your filter meets the unity gain criteria. If not, scale everything down 
until is does. If you are way below unity, you might want to scale 
everything up to get better resolution in the fixed point calculations. 
Finally, it is a good idea to try the resulting filter in SciLab, to see 
if the quantisation you are left with is acceptable. It is usually 
easier to investigate this in a modelling tool, than in your target machine.

Regards,
Steve

On Tue, 26 Oct 2004 10:07:38 GMT, r.lyons@_BOGUS_ieee.org (Rick Lyons)
wrote:

>On Tue, 26 Oct 2004 19:04:01 +1000, Tony <tony_roe@tpg.com.au> wrote:
>
>>Hi,
>>
>>I want to implement a speed-critical FIR LPF (order about 50-60) in a
>>16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
>>could overflow with bad results if I don't scale down the coefficients
>>so the peak value is about 7000 (decimal). I've installed SciLab
>>hoping to find a way to optimize the coefficients, but I can't find
>>anything in Signals that directly relates. Is there a toolbox, or some
>>SciLab code somewhere, or MatLab code I could convert? Or some other
>>place to get a clue?
>>
>>Tony (remove the "_" to reply by email)
>
>Hi,
>  If I understand your question, can you not just 
>multiply all your coefficients by a factor that's 
>less than one?  These will make all your 
>coefficients smaller and reduce the amplitude 
>of your filter's output.

Yes, that's what I've done.

>Now, please realize that
>reducing the coefficients (all by the same factor) 
>will aggrevate the "quantized" nature of the coefficients 
>and degrade your stopband attenuation.   So you 
>must carefully model (simulate) the effect of that 
>increased quantization of the coefficients.
>If your new coefficients don't satisfy your desired 
>stopband attenuation, you'll just have to increase 
>the number of coefficients (increase the number 
>of taps).

Yes, I realized that, and that was the purpose of my post. But I had
vaguely hoped that there might be a method of "fiddling" the quantized
coefficients to minimize the effect of the quantizing. From your post
it would seem that's not the case, and I really just need to simulate
the effect, and keep trying different combinations of sets of
quantized filter coefficients until I get something acceptable.

>Have you considered using a "cascade arrangement" of 
>lower-order FIR filters?
>Will you be performing any decimation or 
>interpolation in your system?
>
>[-Rick-]

The system is actually decimating 6:1 (because I couldn't find a
multi-channel delta-sigma ADC that could sample slowly enough). Before
addressing the quantizing issue I tried doing it in two stages, but
after taking the overhead into account there was no benefit. Of course
now that you've brought that back to mind, there may be a benefit
after all as the two smaller FIRs may well not cause the overflow
problem in the first place. Good thought!!!

Tony
Tony (remove the "_" to reply by email)

On Tue, 26 Oct 2004 18:25:59 +0800, Steve Underwood <steveu@dis.org>
wrote:

>Hi Tony,
>
>Tony wrote:
>
>>Hi,
>>
>>I want to implement a speed-critical FIR LPF (order about 50-60) in a
>>16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
>>could overflow with bad results if I don't scale down the coefficients
>>so the peak value is about 7000 (decimal). I've installed SciLab
>>hoping to find a way to optimize the coefficients, but I can't find
>>anything in Signals that directly relates. Is there a toolbox, or some
>>SciLab code somewhere, or MatLab code I could convert? Or some other
>>place to get a clue?
>>
>>Tony (remove the "_" to reply by email)
>>  
>>
>Where does the number 7000 come from? You make the problem sound worse 
>than it is. Remember that overflows in additions are reversible by later 
>subtractions. That is, a long string of additions whose final result 
>does not exceed 32 bits will be correct, even if lots of overflowing 
>occurs at the intermediate stages.

I calculated the nett total result of the coefficient table times the
worst-case input stream (trapezoidal mains frequency - an over-driven
sine wave), assuming that the overflows you mentioned would be
corrected. 

> As long as the overall gain of your 
>filter does not exceed one at any frequency, the final result will be 
>OK. If you are using a filter design tool, it most probably draws a 
>frequency response plot for you. It should be easy to see from that if 
>your filter meets the unity gain criteria. If not, scale everything down 
>until is does.

That's what happened - I had to scale back (for the prototype FIR a
peak coefficient of 7000 produced a gain sufficiently below unity that
the fundamental sinusoidal component of my trapezoidal input should
stay just below clipping).

> If you are way below unity, you might want to scale 
>everything up to get better resolution in the fixed point calculations. 

That was the reason for the post - the coefficients are so heavily
quantized after scaling back that I'm sure the performance is
sub-optimum. I'd like a way to automatically optimize the many
parameters, but failing that, a way to use SciLab to check the results
of my manual work.

>Finally, it is a good idea to try the resulting filter in SciLab, to see 
>if the quantisation you are left with is acceptable. It is usually 
>easier to investigate this in a modelling tool, than in your target machine.
>Regards,
>Steve

So I installed SciLab today, and looked in the Signals macro section,
but nothing jumped out at me that looked like the answer to my
prayers. How would I "try the resulting filter in SciLab"? Is this the
kind of thing for which I should write a dedicated script (Newbie,
remember?)? Are the SciLab demos/help enough for this topic, or is
there some 3rd party reference I need?

Tony (remove the "_" to reply by email)

Tony wrote:

> Hi,
> 
> I want to implement a speed-critical FIR LPF (order about 50-60) in a
> 16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
> could overflow with bad results if I don't scale down the coefficients
> so the peak value is about 7000 (decimal). I've installed SciLab
> hoping to find a way to optimize the coefficients, but I can't find
> anything in Signals that directly relates. Is there a toolbox, or some
> SciLab code somewhere, or MatLab code I could convert? Or some other
> place to get a clue?
> 
> Tony (remove the "_" to reply by email)

The MSP430 hardware multiplier includes a sum extend register that 
extends the accumulator to 48 bits, so you should be able to do a 16-bit 
FIR with tens of thousands of taps without overflow.  See 
http://focus.ti.com/lit/an/slaa042/slaa042.pdf for details.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"Tony" <tony_roe@tpg.com.au> wrote in message 
news:u84sn01nced6u122qkapassmf8o85evmku@4ax.com...
> Hi,
>
> I want to implement a speed-critical FIR LPF (order about 50-60) in a
> 16bit MCU (MSP430), but it's MAC accumulator is only 32 bits, so it
> could overflow with bad results if I don't scale down the coefficients
> so the peak value is about 7000 (decimal). I've installed SciLab
> hoping to find a way to optimize the coefficients, but I can't find
> anything in Signals that directly relates. Is there a toolbox, or some
> SciLab code somewhere, or MatLab code I could convert? Or some other
> place to get a clue?

I don't know if this addresses your situation, but it may.  It depends on 
the DSP:
Some FIR implementations, particularly in FPGAs, attempt to reduce the 
number of multiplies by replacing them with shifts and adds.  So, what's 
done is to replace the coefficients with sums of powers of 2 - effectively 
truncating the coefficients to a small number of bits.  Of course, the 
shifts are done in the "wiring" so add no operational load - so it's a 
matter of whether adds are "cheaper" in some way than multiplies.

0.625 would be a perfect case: 0.5 + 0.125, etc.

So, you attempt to find the "best" result for quantized coefficients over 
the universe of possible coefficient values - truncated to some number of 
bits.

There's a lot of literature and there are some discussions in comp.dsp about 
this approach.

Fred 

Tony wrote:
> [snip]
> 
> So I installed SciLab today, and looked in the Signals macro section,
> but nothing jumped out at me that looked like the answer to my
> prayers. How would I "try the resulting filter in SciLab"? Is this the
> kind of thing for which I should write a dedicated script (Newbie,
> remember?)? Are the SciLab demos/help enough for this topic, or is
> there some 3rd party reference I need?
> 

You might try posting your Scilab specific questions to 
comp.soft-sys.math.scilab .

They can be quite helpful for well described questions/problems.
A. Fellow Newbie ;}

Tony wrote:

> 
> So I installed SciLab today, and looked in the Signals macro section,
> but nothing jumped out at me that looked like the answer to my
> prayers. How would I "try the resulting filter in SciLab"? Is this the
> kind of thing for which I should write a dedicated script (Newbie,
> remember?)? Are the SciLab demos/help enough for this topic, or is
> there some 3rd party reference I need?
> 
> Tony (remove the "_" to reply by email)

You need a dedicated script, AFAIK.  Make your filter vector, quantized 
to 7000 points or whatever.  Then make a polynomial out of it and use 
SciLab's Horner function, or make a ratio of polynomials and fling out a 
bode plot -- keeping in mind that I've only tried the latter two for 
filters that are much smaller than yours.

You did see my post about the extension register in the MSP430 multiply 
unit, yes?

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Tue, 26 Oct 2004 12:02:05 -0700, Tim Wescott
<tim@wescottnospamdesign.com> wrote:

>Tony wrote:
>
>> 
>> So I installed SciLab today, and looked in the Signals macro section,
>> but nothing jumped out at me that looked like the answer to my
>> prayers. How would I "try the resulting filter in SciLab"? Is this the
>> kind of thing for which I should write a dedicated script (Newbie,
>> remember?)? Are the SciLab demos/help enough for this topic, or is
>> there some 3rd party reference I need?
>> 
>> Tony (remove the "_" to reply by email)
>
>You need a dedicated script, AFAIK.  Make your filter vector, quantized 
>to 7000 points or whatever.  Then make a polynomial out of it and use 
>SciLab's Horner function, or make a ratio of polynomials and fling out a 
>bode plot -- keeping in mind that I've only tried the latter two for 
>filters that are much smaller than yours.

Thanks - I'll try that.

>You did see my post about the extension register in the MSP430 multiply 
>unit, yes?

No I didn't. Where was it? The extension register didn't look too
useful to me (for signed arithmetic), as it slowed down the loop a
lot. Sure would like a way to load MACS and OP2 in less than 4 clocks
each, too, but the register-indirect modes didn't seem to work.
Tony (remove the "_" to reply by email)