# FIR Filter implementation without padding

Is it possible to implement FIR filtering action without padding the input and coefficients?

i.e. Let's say if the input and filter coefficients are of size 4, then the output will be 7 samples. So, while implementing, we generally add 3 more zeros to both input and filter coefficients making them equal to output size.

But, if the input and filter coefficients are of size 1024, then the output will be of 2047 samples. So, now, we need to add 1023 zeros to both input and filter coefficients. This is inefficient, right?

So, I just want to know is there any other way to implement FIR Filtering without padding?

The below code gives the idea I was talking about.

int main()
{
int x[4],h[4],y[7]={0};

int i,j;

for(i=0;i<4;i++)
{
x[i] = i+1;
h[i] = i+1;
}

for(int i=0;i<7;i++)
{
for(int j=0;j<4;j++)
{
y[i+j] = y[i+j]+x[i]*h[j]; //filtered signal of length M+N-1
}
}

for(i=0;i<7;i++)
printf("%d\n", y[i]);

}


Output: 1,4,10,20,25,24,16 - expected

But obtained results - 1,4,10,20,garbage value, garbage value, garbage value

• Implementing a FIR filter in the time domain doesn't require any padding. The output length is simply N(num of samples) + M (filter kernel length) -1. – dsp_user Feb 28 at 7:41
• @dsp_user Can you modify the code to get the results without padding? I modified, but couldn't get the correct results. – rkc Feb 28 at 7:48
• There are a number of issues with that code. The output length should be N+M-1 and yet your output length is only y[M]. Also, the main inner loop should go to M so change it accordingly. Also, I have y[i+j] whereas you have y[i], which is clearly wrong. The first 4 samples only seem correct because the output is shifted by M samples but your implementation is incorrect. – dsp_user Feb 28 at 9:01
• I have kept the changes whatever you told in the comments section in the code. Kindly, have a look. I am getting only M Correct samples if I used the commented section instead of my code. – rkc Feb 28 at 10:23
• ‘i’ should run for the length of x, which is 4, not 7 – Dan Szabo Feb 28 at 19:34

As I said in a comment, no padding is necessary. A simple FIR implementation might look like (it is assumed that the filter kernel h[] has already been implemented)

float y[N+M-1];
//set y[] to zero
for(int i=0;i<N;i++){ //N - signal length

for(int j=0;j<M;j++){ //M - filter kernel length (usually much shorter than N

y[i+j] = y[i+j]+x[i]*h[j]; //filtered signal of length M+N-1
}
}


h[] represents the filter kernel and is usually implemented as a window-sync filter of length M (in your case it's just the original signal).

For your use case, you'd have

int x[7],h[7],y[13]={0};

int i,j;

for(i=0;i<7;i++)
{
if(i<4)
{
x[i] = i+1;
h[i] = i+1;
}
if(i>=4)
{
x[i] = 0;
h[i] = 0;
}
}

for(int i=0;i<7;i++)
{
for(int j=0;j<7;j++)
{
y[i+j] = y[i+j]+x[i]*h[j]; //filtered signal of length M+N-1
}
}


Note that since you're convolving a signal with itself (x*h), you don't even need h[] but I kept it for clarity.

• I could get only M samples of expected value at the output, if I use the code without padding. – rkc Feb 28 at 8:33
• Post the entire code (including the filter kernel) you're using now and I'll have a look . – dsp_user Feb 28 at 8:35
• Hi, I added the whole code with the changes you mentioned. – rkc Feb 28 at 8:48
• @rkc, no you didn't. You see that I'm using y[i+j] whereas you have y[i]. Also , change the length of y to y[N+M-1]. There might be other issues too. – dsp_user Feb 28 at 9:07
• @rkc, If you're still having difficulty implementing this, just explain which part you don't understand so that I can help. – dsp_user Feb 28 at 9:36