FIR filter verification

Steve Pope <spope33@speedymail.org> wrote:
> Tim Wescott  <seemywebsite@myfooter.really> wrote:
 
>>To that it's probably a good idea to add an input stimulus purposely 
>>designed to cause overflow (if the filter is designed to allow it) to 
>>make sure that it is handled correctly.
 
> Whenever possible, I will generate a curve over the entire
> dynamic range -- that is, sweep the magnitude of the test signal 
> applied to the inputs from "below noise" to "above saturation", and 
> graph the RMS error (expressed in dBc) vs. input level (expressed in dB).

For FIR, it seems to me that for each tap you can figure out
the largest value that can be added to the total.  For IIR, it
isn't so obvious, but maybe not so hard.

Strange thought, if you take a FIR filter, then take the absolute
value of all the coefficients, what do you call the result?

-- glen

On Tue, 06 Oct 2015 01:42:08 +0000, glen herrmannsfeldt wrote:

> Steve Pope <spope33@speedymail.org> wrote:
>> Tim Wescott  <seemywebsite@myfooter.really> wrote:
>  
>>>To that it's probably a good idea to add an input stimulus purposely
>>>designed to cause overflow (if the filter is designed to allow it) to
>>>make sure that it is handled correctly.
>  
>> Whenever possible, I will generate a curve over the entire dynamic
>> range -- that is, sweep the magnitude of the test signal applied to the
>> inputs from "below noise" to "above saturation", and graph the RMS
>> error (expressed in dBc) vs. input level (expressed in dB).
> 
> For FIR, it seems to me that for each tap you can figure out the largest
> value that can be added to the total.  For IIR, it isn't so obvious, but
> maybe not so hard.

I had been thinking that it was damned near impossible, then I realized 
that you just need to take RBJ's idea and excite it with the sign 
function of the impulse response:

    x[n] = sgn{ h[n0-n] }

That'll take it the closest to hitting the rails.

To be complete you'd want to find the transfer function from input to 
each internal variable, because they won't be the same as the in to out 
transfer function.

In addition to this, since IIR filters are hugely more susceptible to 
quantization errors than FIR filters, you'd want to verify that the 
filter behaves nicely at very low input amplitudes.  Here again, having a 
knowledge of the inner workings of the filter is helpful because it 
informs you of the frequencies at which the filter will be most 
susceptible to error.

(A bit of analysis, if you consider that part of "verification", wouldn't 
go amiss either, although that really should be done as part of the 
design process.  Having a second person going over your math, or even 
working through it independently, isn't a bad idea at all.)

-- 
www.wescottdesign.com

On Mon, 05 Oct 2015 17:25:29 -0400, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 10/5/15 5:16 PM, Eric Jacobsen wrote:
>> On Mon, 05 Oct 2015 15:43:20 -0500, Tim Wescott
>> <seemywebsite@myfooter.really>  wrote:
>>
>>> On Mon, 05 Oct 2015 15:30:57 -0500, kaz wrote:
>>>
>>>
>>>>> Basically, I have designed a moving average filter with co-efficient -
>>>> 0.2
>>>>> 0.2 0.2 0.2 0.2 I have used two stimulus' currently to do a sanity check
>>>>> if the implementation is working.
>>>>>
>>>>>
>>>> you said it correctly, you want to verify implementation rather than
>>>> concept.
>>>> I wouldn't worry about impulse response, nonlinearity, frequency
>>>> response etc. that is all to do with verification of concept and is
>>>> waste of time at implementation. All you need some random data as input
>>>> and a simple fir mathematical model that is proven (Matlab) and check
>>>> output of your design Vs model output.
>>>
>>> To that it's probably a good idea to add an input stimulus purposely
>>> designed to cause overflow (if the filter is designed to allow it) to
>>> make sure that it is handled correctly.
>>>
>...
>> For example, a string of input samples at max value can help reveal
>> overflow issues, likewise a string of input samples at min value.
>> For filters with coefficients with differing signs, a string of
>> max-valued input samples with signs arranged to yield the largest
>> possible output can also be revealing.
>
>i.e.
>
>    x[n] = sgn{ h[n0-n] }
>
>for  0 < n <= n0
>
>and n0 >= L, the length of the FIR.

Actually,

    x[n] = A*sgn{ h[n0-n] }

where A is the maximum valued of the input amplitude.   Doing this
with both A = the max positive value and the A = the max negative
value is necessary, especially since the negative value magnitude is
larger in 2's complement.

>
>to me, that (assuming that max |x[n]| = 1) would decidedly be the acid 
>test for detecting overflow.
>
>
>-- 
>
>r b-j                  rbj@audioimagination.com
>
>"Imagination is more important than knowledge."
>
>

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Hello,

Thanks a lot for the responses. I am consolidating my comments in this
single post ...

>The one thing missing from your question, which boggles my mind a bit 
>since you're talking about testing, is the specified behavior of the 
>filter.

In this specific case, I have not started with filter design
specifications but I could have very well done that. I have deliberately
chosen a simple filter to   get my basics about filter verification
right.

>Shouldn't testing be making sure that the filter behaves as specified?  
>So -- how is the filter specified?

Sure. Assume we do have filter specifications then I would like to get
inputs on how to formalize verification of that filter.

>That it does not exhibit more than specified quantization anomalies (or 
>noise, if you want to spec it that way).  Strictly speaking this comes 
>under nonlinear behavior, but most people separate the two.

Correct. How can I verify to make sure that quantization effect is not
degrading the filter performance. This could be due to less than word size
or bug in the filter implementation ...

Should I pass a sine waveform with frequency within the pass band and then
measure SNR of ideal output VS actual output. Ideal output is from a
floating point Matlab implementation.

>All you need some random data as input and a simple fir
>mathematical model that is proven (Matlab) and check output of your
design
>Vs model output.

I really doubt if this method will ever help in case of algorithm
validation. A filter is frequency selective function and testing with
random data will hardly test the function.In fact, we will never know if
enough testing has been done. If we cant define what is sufficient for
testing, it is hard to say when enough testing has been done.

>To that it's probably a good idea to add an input stimulus purposely 
>designed to cause overflow (if the filter is designed to allow it) to 
>make sure that it is handled correctly.

Agree. But assuming an FIR filter and fixed point implementation, what is
this special input I can pass to make sure that data is not getting
saturated inside the filter? Can you throw some light or give an example?

>For exampe, a string of input samples at max value can help reveal
>overflow issues, likewise a string of input samples at min value.
>For filters with coefficients with differing signs, a string of
>max-valued input samples with signs arranged to yield the largest
>possible output can also be revealing.

Thanks

>Whenever possible, I will generate a curve over the entire
>dynamic range -- that is, sweep the magnitude of the test signal 
>applied to the inputs from "below noise" to "above saturation", and 
>graph the RMS error (expressed in dBc) vs. input level (expressed in
dB).
 
>Such a graph should have a wide region where the dBc error is
>satisfactorily low, corresponding the operating region, and will have
>degraded (higher) dBc error at both low and high input levels,
>corresponding to quantization and saturation/overflow errors
>respectively.
 
>Good test signals are sinusoids, and also lowpass-filtered white
>noise.

Thanks


>i.e.

>    x[n] = sgn{ h[n0-n] }

>for  0 < n <= n0

>and n0 >= L, the length of the FIR.

>to me, that (assuming that max |x[n]| = 1) would decidedly be the acid 
>test for detecting overflow.

Thanks

>For FIR, it seems to me that for each tap you can figure out
>the largest value that can be added to the total.  For IIR, it
>isn't so obvious, but maybe not so hard.

>Strange thought, if you take a FIR filter, then take the absolute
>value of all the coefficients, what do you call the result?

In case of moving average filter the sum is 1 but I dont think this is the
case with other filters. In fact, I have a question that filters such as
moving average filters dont act like filter intuitively because they
really dont remove anything from input but that topic is for other day
...

>A bit of analysis, if you consider that part of "verification", wouldn't

>go amiss either, although that really should be done as part of the 
>design process.  Having a second person going over your math, or even 
>working through it independently, isn't a bad idea at all.)

My situation is different. I verify filters designed by someone else









---------------------------------------
Posted through http://www.DSPRelated.com

On Tue, 06 Oct 2015 13:37:17 -0500, Sharan123 wrote:

> Hello,
> 
> Thanks a lot for the responses. I am consolidating my comments in this
> single post ...
> 
>>The one thing missing from your question, which boggles my mind a bit
>>since you're talking about testing, is the specified behavior of the
>>filter.
> 
> In this specific case, I have not started with filter design
> specifications but I could have very well done that. I have deliberately
> chosen a simple filter to   get my basics about filter verification
> right.
> 
>>Shouldn't testing be making sure that the filter behaves as specified?
>>So -- how is the filter specified?
> 
> Sure. Assume we do have filter specifications then I would like to get
> inputs on how to formalize verification of that filter.
> 
>>That it does not exhibit more than specified quantization anomalies (or
>>noise, if you want to spec it that way).  Strictly speaking this comes
>>under nonlinear behavior, but most people separate the two.
> 
> Correct. How can I verify to make sure that quantization effect is not
> degrading the filter performance. This could be due to less than word
> size or bug in the filter implementation ...
> 
> Should I pass a sine waveform with frequency within the pass band and
> then measure SNR of ideal output VS actual output. Ideal output is from
> a floating point Matlab implementation.

If you don't analyze the filter structure itself then it needs to be a 
swept sine wave.

In fact, in my opinion, I think it is necessary (if, perhaps, not 
sufficient) to analyze the code as written -- I don't think that black 
box testing is ever going to find all possible bugs.  If your job is to 
do black box testing after someone else has done verification by analysis 
-- fine -- but there are times when testing is like blindly shooting at 
noises in the dark, hoping to hit a deer, and I suspect that filters is 
one such case.

>>All you need some random data as input and a simple fir mathematical
>>model that is proven (Matlab) and check output of your
> design
>>Vs model output.
> 
> I really doubt if this method will ever help in case of algorithm
> validation. A filter is frequency selective function and testing with
> random data will hardly test the function.In fact, we will never know if
> enough testing has been done. If we cant define what is sufficient for
> testing, it is hard to say when enough testing has been done.

I agree, more or less. You can put in white noise and verify that the 
output has the right spectrum, but this won't help you with all possible 
bugs.

>>To that it's probably a good idea to add an input stimulus purposely
>>designed to cause overflow (if the filter is designed to allow it) to
>>make sure that it is handled correctly.
> 
> Agree. But assuming an FIR filter and fixed point implementation, what
> is this special input I can pass to make sure that data is not getting
> saturated inside the filter? Can you throw some light or give an
> example?

RBJ's +/- (max_in) * sgn(h(n))

> 
>>For exampe, a string of input samples at max value can help reveal
>>overflow issues, likewise a string of input samples at min value.
>>For filters with coefficients with differing signs, a string of
>>max-valued input samples with signs arranged to yield the largest
>>possible output can also be revealing.
> 
> Thanks
> 
>>Whenever possible, I will generate a curve over the entire dynamic range
>>-- that is, sweep the magnitude of the test signal applied to the inputs
>>from "below noise" to "above saturation", and graph the RMS error
>>(expressed in dBc) vs. input level (expressed in
> dB).
>  
>>Such a graph should have a wide region where the dBc error is
>>satisfactorily low, corresponding the operating region, and will have
>>degraded (higher) dBc error at both low and high input levels,
>>corresponding to quantization and saturation/overflow errors
>>respectively.
>  
>>Good test signals are sinusoids, and also lowpass-filtered white noise.
> 
> Thanks
> 
> 
>>i.e.
> 
>>    x[n] = sgn{ h[n0-n] }
> 
>>for  0 < n <= n0
> 
>>and n0 >= L, the length of the FIR.
> 
>>to me, that (assuming that max |x[n]| = 1) would decidedly be the acid
>>test for detecting overflow.
> 
> Thanks
> 
>>For FIR, it seems to me that for each tap you can figure out the largest
>>value that can be added to the total.  For IIR, it isn't so obvious, but
>>maybe not so hard.
> 
>>Strange thought, if you take a FIR filter, then take the absolute value
>>of all the coefficients, what do you call the result?
> 
> In case of moving average filter the sum is 1 but I dont think this is
> the case with other filters. In fact, I have a question that filters
> such as moving average filters dont act like filter intuitively because
> they really dont remove anything from input but that topic is for other
> day ..

Moving average filters are low-pass filters.  It shows up quite 
distinctly if you plot the magnitude response.

>>A bit of analysis, if you consider that part of "verification", wouldn't
> 
>>go amiss either, although that really should be done as part of the
>>design process.  Having a second person going over your math, or even
>>working through it independently, isn't a bad idea at all.)
> 
> My situation is different. I verify filters designed by someone else

That's no reason not to be that second person, working independently.

-- 

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

On Mon, 05 Oct 2015 21:51:59 -0500, Tim Wescott <tim@seemywebsite.com>
wrote:

>On Tue, 06 Oct 2015 01:42:08 +0000, glen herrmannsfeldt wrote:
>
>> Steve Pope <spope33@speedymail.org> wrote:
>>> Tim Wescott  <seemywebsite@myfooter.really> wrote:
>>  
>>>>To that it's probably a good idea to add an input stimulus purposely
>>>>designed to cause overflow (if the filter is designed to allow it) to
>>>>make sure that it is handled correctly.
>>  
>>> Whenever possible, I will generate a curve over the entire dynamic
>>> range -- that is, sweep the magnitude of the test signal applied to the
>>> inputs from "below noise" to "above saturation", and graph the RMS
>>> error (expressed in dBc) vs. input level (expressed in dB).
>> 
>> For FIR, it seems to me that for each tap you can figure out the largest
>> value that can be added to the total.  For IIR, it isn't so obvious, but
>> maybe not so hard.
>
>I had been thinking that it was damned near impossible, then I realized 
>that you just need to take RBJ's idea and excite it with the sign 
>function of the impulse response:
>
>    x[n] = sgn{ h[n0-n] }
>
>That'll take it the closest to hitting the rails.

I mentioned it and then Robert equationified it.   It works best if
you use it with Full Scale inputs, i.e., 

    x[n] = A*sgn{ h[n0-n] }

where A can be +FS, -FS, or even -(+FS).

I've found problems that way before.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On Tue, 06 Oct 2015 13:37:17 -0500, "Sharan123" <99077@DSPRelated>
wrote:

>Hello,
>
>Thanks a lot for the responses. I am consolidating my comments in this
>single post ...
>
>>The one thing missing from your question, which boggles my mind a bit 
>>since you're talking about testing, is the specified behavior of the 
>>filter.
>
>In this specific case, I have not started with filter design
>specifications but I could have very well done that. I have deliberately
>chosen a simple filter to   get my basics about filter verification
>right.
>
>>Shouldn't testing be making sure that the filter behaves as specified?  
>>So -- how is the filter specified?
>
>Sure. Assume we do have filter specifications then I would like to get
>inputs on how to formalize verification of that filter.
>
>>That it does not exhibit more than specified quantization anomalies (or 
>>noise, if you want to spec it that way).  Strictly speaking this comes 
>>under nonlinear behavior, but most people separate the two.
>
>Correct. How can I verify to make sure that quantization effect is not
>degrading the filter performance. This could be due to less than word size
>or bug in the filter implementation ...
>
>Should I pass a sine waveform with frequency within the pass band and then
>measure SNR of ideal output VS actual output. Ideal output is from a
>floating point Matlab implementation.
>
>>All you need some random data as input and a simple fir
>>mathematical model that is proven (Matlab) and check output of your
>design
>>Vs model output.
>
>I really doubt if this method will ever help in case of algorithm
>validation. A filter is frequency selective function and testing with
>random data will hardly test the function.In fact, we will never know if
>enough testing has been done. If we cant define what is sufficient for
>testing, it is hard to say when enough testing has been done.
>
>>To that it's probably a good idea to add an input stimulus purposely 
>>designed to cause overflow (if the filter is designed to allow it) to 
>>make sure that it is handled correctly.
>
>Agree. But assuming an FIR filter and fixed point implementation, what is
>this special input I can pass to make sure that data is not getting
>saturated inside the filter? Can you throw some light or give an example?

It's been mentioned several times, essentially:

    x[n] = A*sgn{ h[n0-n] }

where A can be +FS, -FS, or even -(+FS).   As Robert mentioned, the
length of x[n] must be at least as long as h[n] to get the full
effect.   Once the full length sequence has been cycled in, any
saturation of overflow problems will be evident.

The arithmetic inside the filter cannot ever exceed those particular
cases, as those are the pathological worst cases for saturation or
overflow.


>>For exampe, a string of input samples at max value can help reveal
>>overflow issues, likewise a string of input samples at min value.
>>For filters with coefficients with differing signs, a string of
>>max-valued input samples with signs arranged to yield the largest
>>possible output can also be revealing.
>
>Thanks
>
>>Whenever possible, I will generate a curve over the entire
>>dynamic range -- that is, sweep the magnitude of the test signal 
>>applied to the inputs from "below noise" to "above saturation", and 
>>graph the RMS error (expressed in dBc) vs. input level (expressed in
>dB).
> 
>>Such a graph should have a wide region where the dBc error is
>>satisfactorily low, corresponding the operating region, and will have
>>degraded (higher) dBc error at both low and high input levels,
>>corresponding to quantization and saturation/overflow errors
>>respectively.
> 
>>Good test signals are sinusoids, and also lowpass-filtered white
>>noise.
>
>Thanks
>
>
>>i.e.
>
>>    x[n] = sgn{ h[n0-n] }
>
>>for  0 < n <= n0
>
>>and n0 >= L, the length of the FIR.
>
>>to me, that (assuming that max |x[n]| = 1) would decidedly be the acid 
>>test for detecting overflow.
>
>Thanks
>
>>For FIR, it seems to me that for each tap you can figure out
>>the largest value that can be added to the total.  For IIR, it
>>isn't so obvious, but maybe not so hard.
>
>>Strange thought, if you take a FIR filter, then take the absolute
>>value of all the coefficients, what do you call the result?
>
>In case of moving average filter the sum is 1 but I dont think this is the
>case with other filters. In fact, I have a question that filters such as
>moving average filters dont act like filter intuitively because they
>really dont remove anything from input but that topic is for other day
>...
>
>>A bit of analysis, if you consider that part of "verification", wouldn't
>
>>go amiss either, although that really should be done as part of the 
>>design process.  Having a second person going over your math, or even 
>>working through it independently, isn't a bad idea at all.)
>
>My situation is different. I verify filters designed by someone else
>
>
>
>
>
>
>
>
>
>---------------------------------------
>Posted through http://www.DSPRelated.com

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

>Hello,
>
>Thanks a lot for the responses. I am consolidating my comments in this
>single post ...
>
>>The one thing missing from your question, which boggles my mind a bit 
>>since you're talking about testing, is the specified behavior of the 
>>filter.
>

>>All you need some random data as input and a simple fir
>>mathematical model that is proven (Matlab) and check output of your
>design
>>Vs model output.
>
>I really doubt if this method will ever help in case of algorithm
>validation. A filter is frequency selective function and testing with
>random data will hardly test the function.In fact, we will never know if
>enough testing has been done. If we cant define what is sufficient for
>testing, it is hard to say when enough testing has been done.

Now you are talking about algorithm validation. Your first post is about
proving implementation. The averaging filter can be studied in its
mathematical model before any form of implementation e.g.(Matlab function
"filter"):

x = [1 zeros(1,1024);
h = [.2,.2,.2,.2,.2];
y = filter(h,1,x);
then study frequency domain of y or its time domain. you will also need to
look after quantisation issues.

so you can use this function to see the response and then implement it and
test your implementation with random data through both model and design:

x = randn(1,1024);
yref = filter(h,1,x);

yref should be same as your design output taking into consideration bit
resolution issues and overflow.

Kaz

---------------------------------------
Posted through http://www.DSPRelated.com

>> I really doubt if this method will ever help in case of algorithm
>> validation. A filter is frequency selective function and testing with
>> random data will hardly test the function.In fact, we will never know
if
>> enough testing has been done. If we cant define what is sufficient for
>> testing, it is hard to say when enough testing has been done.
>
>I agree, more or less. You can put in white noise and verify that the 
>output has the right spectrum, but this won't help you with all possible

>bugs.

Dear Tim,

Please help me understand. Is it a good idea to add a bit of white noise
on top of test signal and check the spectrum? or, would doing this with
just with an impulse input and checking provide sufficient insight into
the filter behavior?

Also, when you say, spectrum, is it frequency domain representation?
---------------------------------------
Posted through http://www.DSPRelated.com

>I mentioned it and then Robert equationified it.   It works best if
>you use it with Full Scale inputs, i.e., 
>
>    x[n] = A*sgn{ h[n0-n] }
>
>where A can be +FS, -FS, or even -(+FS).
>
>I've found problems that way before.

Thanks 
---------------------------------------
Posted through http://www.DSPRelated.com