# Newbie seeking some help understanding convolution

Started by February 7, 2004
```I am somewhat new to DSP and have some general questions about convolution in
regards to FIR filtering.

First, when it is desired to filter a signal and convolution is to be used,
how do I interpret the fact that the output sequence is longer than the input?
I guess it never occured to me that whenever you filter a signal you get more
out than you put in.

For example, if my data is x[n] of length 6 and my filter, h[n] is of length
6, then my output y[n] will be of length 6 + 6 - 1 = 11.

h[n] = { 1, 2, 3, 4, 5, 6 }  (assume already flipped)
^

x[n] = { 2, 3, 4, 5, 6, 7 }
^

6 * 2
6 * 3 + 5 * 2
6 * 4 + 5 * 3 + 4 * 2
6 * 5 + 5 * 4 + 4 * 3 + 3 * 2
6 * 6 + 5 * 5 + 4 * 4 + 3 * 3 + 2 * 1
6 * 7 + 5 * 6 + 4 * 5 + 3 * 4 + 3 * 2 + 2 * 1
5 * 7 + 4 * 6 + 3 * 5 * 2 * 4 + 1 * 3
4 * 7 + 3 * 6 + 2 * 5 * 1 * 4
3 * 7 + 2 * 6 + 1 * 5
2 * 7 + 1 * 6
1 * 7

Second, when filtering, there will be a point where there is no more new data
to traverse the length of the filter. In my example above, the stage where I
am multiplying 5 * 7 + 4 * 6 .... my delay line is becoming filled with one
less sample after each shift. It is looking for samples beyond my last x[n]
value. Effectively these values would be zero. So, do I need to append zeros
to the end of my data to finish out the convolution?

In a similar fashion, when I first start my filtering not all of the filter
taps are being multiplied by my data since the data hasn't yet been shifted
across the filter.

In the Scientists and Engineer's Guide to DSP, on page 120 in Chapter 6, it
calls this the "end effect" and claims that "the beginning and ending samples
will be quite useless". But what does this really mean? If they are useless,
should they even be calculated?

The FIR filtering examples I seem to run across seem to 'stop' when the last
data sample is read, effectively shortening the length of the total
convolution output. In a real world example, with say a stream of audio data,
do I have to pad the last sample with zeros to 'fill out' the length of the
filter?

Lastly, it appears to me that if the data sequence, x[n], is very long
compared to the filter length, h[n], then the extra samples in the
output due to convolution would be a small percentage of the overall output
file. Is this significant in any way?

Any explanation from you guys to help me understand this will be great.

This is one of the best usenet groups I've ever come across. You guys are
doing a great job.

-Larry

```
```Larry McFarren wrote:

> I am somewhat new to DSP and have some general questions about convolution in
> regards to FIR filtering.
>
> First, when it is desired to filter a signal and convolution is to be used,
> how do I interpret the fact that the output sequence is longer than the input?
> I guess it never occured to me that whenever you filter a signal you get more
> out than you put in.
>
> For example, if my data is x[n] of length 6 and my filter, h[n] is of length
> 6, then my output y[n] will be of length 6 + 6 - 1 = 11.
>
>
> h[n] = { 1, 2, 3, 4, 5, 6 }  (assume already flipped)
>                         ^
>
> x[n] = { 2, 3, 4, 5, 6, 7 }
>          ^
>
>
> 6 * 2
> 6 * 3 + 5 * 2
> 6 * 4 + 5 * 3 + 4 * 2
> 6 * 5 + 5 * 4 + 4 * 3 + 3 * 2
> 6 * 6 + 5 * 5 + 4 * 4 + 3 * 3 + 2 * 1
> 6 * 7 + 5 * 6 + 4 * 5 + 3 * 4 + 3 * 2 + 2 * 1
> 5 * 7 + 4 * 6 + 3 * 5 * 2 * 4 + 1 * 3
> 4 * 7 + 3 * 6 + 2 * 5 * 1 * 4
> 3 * 7 + 2 * 6 + 1 * 5
> 2 * 7 + 1 * 6
> 1 * 7
>
>
>
> Second, when filtering, there will be a point where there is no more new data
> to traverse the length of the filter. In my example above, the stage where I
> am multiplying 5 * 7 + 4 * 6 .... my delay line is becoming filled with one
> less sample after each shift. It is looking for samples beyond my last x[n]
> value. Effectively these values would be zero. So, do I need to append zeros
> to the end of my data to finish out the convolution?
>
> In a similar fashion, when I first start my filtering not all of the filter
> taps are being multiplied by my data since the data hasn't yet been shifted
> across the filter.
>
> In the Scientists and Engineer's Guide to DSP, on page 120 in Chapter 6, it
> calls this the "end effect" and claims that "the beginning and ending samples
> will be quite useless". But what does this really mean? If they are useless,
> should they even be calculated?
>
> The FIR filtering examples I seem to run across seem to 'stop' when the last
> data sample is read, effectively shortening the length of the total
> convolution output. In a real world example, with say a stream of audio data,
> do I have to pad the last sample with zeros to 'fill out' the length of the
> filter?
>
> Lastly, it appears to me that if the data sequence, x[n], is very long
> compared to the filter length, h[n], then the extra samples in the
> output due to convolution would be a small percentage of the overall output
> file. Is this significant in any way?
>
> Any explanation from you guys to help me understand this will be great.
>
> This is one of the best usenet groups I've ever come across. You guys are
> doing a great job.
>
> -Larry

Larry,

You're most of the way there. If your data start and end in silence,
then you can tack as many zeros onto the ends as you need, and all of
your output will be valid. In most cases, you won't be that lucky.
Assume a transversal FIR filter. When there's only one sample in it (the
stages being initialized to zero), it's output is clearly garbage. When
all but one tap is working with real data, the output is nearly perfect.
Only when it's entirely filled with real data does the output conform to
the design. While the number of output data points exceeds the number of
input data points, the number of good data points doesn't, and the
number of perfect data points is actually smaller. This becomes clear
very early with image processing, where the picture either shrinks at
the edges or new edge pixels need to be algorithmically synthesized.

Jerry
--
Engineering is the art of making what you want from things you can get.
&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;&#4294967295;

```
```Imagine when you hit a gong or a bell with a hammer.
The audio resonances carry on for much longer than
the bang time.

"Larry McFarren" <invalid@address.com> wrote in message
news:kIaVb.20307\$TQ2.7320@newssvr24.news.prodigy.com...
> First, when it is desired to filter a signal and convolution is to be
used,
> how do I interpret the fact that the output sequence is longer than the
input?

```