# circular convolution

Started by September 19, 2006
I'm perusing the web and I suspect worse case I'll grab a few texts to
further assist me, nonetheless, given two sequences ( radar application
) - reference and receive of length 1024.
It was explained to me that the for linear convolution, I'll pad the
sequences with zeros, then compute the FFTs.
For circular convolution there's no need for padding.    None of this
makes sense to me as a result armed with the information above ( two
arrays ( sequences ) of length 1024 ), how would one describe linear
and circular convolution?
Furthermore what if the lengths of the sequences differ?  Not sure if
my question makes sense but I'm trying to understand some information I

forums_mp@hotmail.com wrote:
> I'm perusing the web and I suspect worse case I'll grab a few texts to > further assist me, nonetheless, given two sequences ( radar application > ) - reference and receive of length 1024. > It was explained to me that the for linear convolution, I'll pad the > sequences with zeros, then compute the FFTs. > For circular convolution there's no need for padding. None of this > makes sense to me as a result armed with the information above ( two > arrays ( sequences ) of length 1024 ), how would one describe linear > and circular convolution? > Furthermore what if the lengths of the sequences differ? Not sure if > my question makes sense but I'm trying to understand some information I > received earlier today. > > > Thanks in advance
For linear convolution, you form the sum of products as the arrays slip past one another, the product being zero if there is no overlap. For circular convolution, there is always overlap because the arrays wrap around. x y z c b a Partial products = cz x y z c b a Partial products = cy, bz x y z c b a Partial products = cx, by, az x y z c b a Partial products = bx, ay x y z c b a Partial products = ax Linear convolution sum = cz + cy + bz + cx + by + az + bx + ay + ax Can you do the circular convolution yourself? It is shorter. 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;
>
> Can you do the circular convolution yourself? It is shorter.
Jerry appreaciate the prompt response. The answer is No. The impression I'm got is it's indeed shorter and I suspect 'faster'. I'm slowly trying to get acclimated with the various terminologies. That said, most literature I peruse refers to the input signal multiplied by an impulse response. The impulse response muddles things a little since from my perspective - given two sequences which is the so called impulse response? Admittidely, I still struggle with ( software background ) with this idea of an impulse response since in my view I'm not understanding how it's derived. Meaning, if I give you a signal - for practical purposes - a sequence. So now we have x(n). Where does 'h ( n )' come from? Lot of stuff to get my head around right now.
Jerry Avins wrote:

> Linear convolution sum = cz + cy + bz + cx + by + az + bx + ay + ax
Excellent. Sometimes I wish the various literatures / text would start off real simple for some of us.
> Can you do the circular convolution yourself? It is shorter.
Now I'm off to knock myself out on this one.
forums_mp@hotmail.com wrote:
> > >> Can you do the circular convolution yourself? It is shorter. > Jerry appreaciate the prompt response. > The answer is No.
OK then. x y z c b a Partial products = cx + by + az x y z b a c (circular shift) Partial products = bx + ay + cz x y z a c b Partial products = ax + cy + bz Linear convolution sum = cx + by + az + bx + ay + cz + ax + cy + bz
> The impression I'm got is it's indeed shorter and I > suspect 'faster'.
Faster, but not the same result. Sometimes you want one, sometimes the other.
> I'm slowly trying to get acclimated with the > various terminologies. That said, most literature I peruse refers to > the input signal multiplied by an impulse response. The impulse > response muddles things a little since from my perspective - given two > sequences which is the so called impulse response?
Convolution can be represented in the abstract, but we usually do it for a purpose. A common purpose is making a filter, called "transversal" because of the way a sample eventually transverses the length of the filter, or more usually, "FIR" for "finite impulse response". The fixed coefficients of the filter are its discrete-time impulse response. You can understand that better if you accept a unity-value sample as a digital impulse and think of the filter's response as a single impulse transverses it. The output of any structure or circuit when excited by an impulse is its impulse response by definition. The output of an FIR filter excited by an impulse is simply the value of its coefficients in sequence.
> Admittidely, I still struggle with ( software background ) with this > idea of an impulse response since in my view I'm not understanding how > it's derived. Meaning, if I give you a signal - for practical purposes > - a sequence. So now we have x(n). Where does 'h ( n )' come from? > Lot of stuff to get my head around right now.
The impulse response is h(n); i.e. h(0), h(1), ... h(N - 1), where N is the length of the impulse response. Impulse response and frequency response are Fourier-transform pairs. 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;
forums_mp@hotmail.com wrote:
> Jerry Avins wrote: > >> Linear convolution sum = cz + cy + bz + cx + by + az + bx + ay + ax > Excellent. Sometimes I wish the various literatures / text would start > off real simple for some of us.
I can't praise Rick's book too highly on that count, but it's not cheap. http://www.powells.com/s?kw=understanding+digital+signal&x=0&y=0 A very good free-on-line book is at http://www.dspguide.com/
>> Can you do the circular convolution yourself? It is shorter. > Now I'm off to knock myself out on this one.
I did it for you before I saw this message. Should I be sorry? 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;
"Jerry Avins" <jya@ieee.org> wrote in message