Forums

Is this a FIR algorithm? If not could someone explain this?

Started by jshowa 2 years ago5 replieslatest reply 2 years ago111 views
I'm kind of out of my element here trying to understand this algorithm and I wanted to see if this is a FIR algorithm or not? If this isn't the right place to ask this, can someone point me to a place?

The reason I ask is because this code is not well commented and not defined anywhere and I'm relatively new to this problem domain.

=====Code Start==========

' Called BY CAntennaT with ref to a one-dim array of single's

'

Public Function Filter3_Ant(data As Variant, ByVal CNo As Integer, ByVal times As Integer) As Integer

Dim i As Integer, k As Integer

Dim Anz As Integer

Dim I_1 As Variant      ' value at I-1

Dim I_0 As Variant      ' saved value at I-0


    If times <= 0 Then Exit Function


    ' use filter3 only where it makes sense

    If (Module.GetTestFlag(CNo) And (SIMPLE_GAIN + SDARS_STD)) = 0 Then Exit Function


    Anz = VUbound(data)

    If Anz < 3 Then Exit Function


    Do

        I_1 = data(1)  ' preset with I+2, then first becomes 0.5 * F(I) + 0.5 * F(I+1)

        For i = 0 To Anz - 2

            I_0 = data(i)

            data(i) = I_1 * 0.25 + data(i) * 0.5 + data(i + 1) * 0.25

            I_1 = I_0

        Next

        data(i) = I_1 * 0.5 + data(i) * 0.5


        times = times - 1

    Loop While times > 0

End Function


=======CODE END========

I asked this on another form and they suggested it was and that the impulse responses are 0.25, 0.5, and 0.25. However what confuses me is that it looks like a convolution sum but presented in a very odd way.

I would've assumed if it was computing the convolution sum, it would be taking each point in the input and multiply it by 0.25, 0.5, and 0.25 added together, ie.

For i = 0 To Anz - 2
data(i) = data(i) * 0.25 + data(i) * 0.5 + data(i) * 0.25
Next

But its like its doing portions of it and then applying it again over the same points....
[ - ]
Reply by Y(J)SAugust 16, 2018

From a quick look, it seems to be an in-place FIR.

In a standard FIR you convolve on x and produce y. 

If you try do this in-place you overwrite a value (say x_i) and then use it in the next sum 0.25*x_i-1 + 0.5*x_i + 0.25*x_i+1. What is being done here is to save the original value so that x_i-1 is correct.

Of course, this is specific to a FIR filter with a single lag back in time.

Y(J)S

[ - ]
Reply by jshowaAugust 16, 2018

I've seen FIR algorithms with one future point, however this implementation perplexes me because it begins with data(1) twice. For example:

Loop iteration 1

----------------

data(0) = data(1) * 0.25 + data(0) * 0.5 + data(1) * 0.25 

I'm slightly confused as to why this is being done as I've never seen a FIR computed with the same input point more than once initially. My guess is that this was done because the using the causal portion of the the input (i.e. x[n - 1]) would've been x[-1] for the input array.

Would that be a correct analysis?

[ - ]
Reply by jbrowerAugust 16, 2018

Jshowa-

Y(J)S is spot on.  They want to avoid overwriting input data in a short range of 3 points (length of filter, M = 3), so they temporarily use input points as the "sum" and "delay elements" then replace those and move on to the next input point.

The example above without being done in-place would look like this:

  for (n=0, sum=0; n<times; n++) {)>

   // for (i=0; i<M-1; i++) replace inner loop with one line;>

        sum += data[n] * 0.25 + data[n-1] * 0.5 + data[n-2] * 0.25;

        data_out[n] = sum;

  }

But if you want to eliminate data_out[] then you have to do two things (i) not overwrite data[] until the filter has been applied and (ii) save last M-1 points of data[] for the next iteration of n.

The code above seems to do this by carefully re-using the last 3 points of data[] for each n.  I didn't go through it super carefully though, so couldn't tell you if it's working correctly.

-Jeff  


[ - ]
Reply by jshowaAugust 16, 2018

But wouldn't doing this:

for (n=0, sum=0; n<times; n++) {)>
   // for (i=0; i<M-1; i++) replace inner loop with one line;>
        sum += data[n] * 0.25 + data[n-1] * 0.5 + data[n-2] * 0.25;

        data_out[n] = sum;

  }

Cause a failure when accessing the array at data[n-1] and data[n-2] on the first and second iterations?

My follow up question was why it was in the form 

data(1) * 0.25 + data(0) * 0.5 + data(1) * 0.25

on the initial iteration. Because I thought it was in the form

y[n] = x[n-1] + x[n] + x[n+1]

and the input array was just being reused to hold the previous sum in order to compute the output points. 

And the start of form was just chosen to avoid accessing an array out of bounds on the initial iteration.


Also, would there be any reason as to why the impulse response was chosen as {0.25, 0.5, 0.25}?


I'm sorry I'm asking a lot of questions. I'm just very unfamiliar with this area. 

[ - ]
Reply by jbrowerAugust 16, 2018

Jshowa-

> Cause a failure when accessing the array at data[n-1] and data[n-2]
> on the first and second iterations?

Yes it would, so expanding on my simple example, data[0] and data[1] would have to be saved in static vars.  Here is code that does that, although unfortunately for forum purposes it's a little more complex:


int N = times;
static int data_savn1 = 0, data_savn2 = 0;

  data_out[0] = data[n] * 0.25 + data_savn1 * 0.5 + data_savn2 * 0.25;
  data_out[1] * 0.25 + data[0] * 0.5 + data_savn1 * 0.25;

  for (n=2, n<N; n++) {
   // for (i=0; i<M-1; i++) replace inner loop with one line
     data_out[n] = data[n] * 0.25 + data[n-1] * 0.5 + data[n-2] * 0.25;
  }
  data_savn1 = data[N-2];
  data_savn2 = data[N-3];

> Also, would there be any reason as to why the impulse response was
> chosen as {0.25, 0.5, 0.25}?

Normally FIR filter coefficients are symmetric, so with M = 3 yours fits that guideline.  As for the values themselves, they would be data dependent.  In your example the impulse response is a simple, all positive "inverted V" shape so that's a very elemental low pass filter.  A longer one with similar shape is here (Figure 4):

https://blricrex.hypotheses.org/filtering-introduc...

That page is EEG related.

-Jeff