Newbie seeking some help understanding convolution

Started by Larry McFarren 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. �����������������������������������������������������������������������
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?