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
received earlier today.

Thanks in advance

```
```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
news:24Odnbuy4NlDIY3YnZ2dnUVZ_v6dnZ2d@rcn.net...
> forums_mp@hotmail.com wrote:
>
> I can't praise Rick's book too highly on that count, .....

Most denizens of comp.dsp (including, of course, Jerry
Avins) have very high regard for Rick's book, and I fully
understand (and agree) with what Jerry intended the reader
to infer from his comment.  That being said, I have always
wondered what the literal meaning of the phrase

"can't praise .. too highly on that count..."

is.  To my tin ear, it sounds like saying that a moderate
(or even a faint) praise is quite adequate on that count,
which is surely not the meaning intended.  Ah well, I
suspect that the phrase is well-fixed in the idiom by now.

--Dilip Sarwate

```
```Dilip V. Sarwate wrote:
> "Jerry Avins" <jya@ieee.org> wrote in message
> news:24Odnbuy4NlDIY3YnZ2dnUVZ_v6dnZ2d@rcn.net...
>> forums_mp@hotmail.com wrote:
>>
>> I can't praise Rick's book too highly on that count, .....
>
> Most denizens of comp.dsp (including, of course, Jerry
> Avins) have very high regard for Rick's book, and I fully
> understand (and agree) with what Jerry intended the reader
> to infer from his comment.  That being said, I have always
> wondered what the literal meaning of the phrase
>
>        "can't praise .. too highly on that count..."
>
> is.  To my tin ear, it sounds like saying that a moderate
> (or even a faint) praise is quite adequate on that count,
> which is surely not the meaning intended.  Ah well, I
> suspect that the phrase is well-fixed in the idiom by now.

"I can't praise ... too highly" can indeed be construed too ways. It is
an ambiguity sometimes employed by those forced to describe someone
they'd rather not. I'm not required to say anything about Rick's on
anyone else's book, so it means, "No reasonable amount of praise could
be too much" rather than "I'm unable to praise it very much."

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 skrev:
> >
> > 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.

The general idea behind radar and active sonar systems, is that
you send out a signal -- and thus have knowledge about what that
signal looks like, since you control the transmitter -- and search
for a copy of that same signal in the recieved data stream.

In the usual terminology x[n] represents a measured signal
while h[n] is some system response that you have designed.

Since you know what signal you transmitted, you have some
idea about what you will recieve. Consequently, you can design
a system response h[n] that helps you detect the transmitted
signal in your measured data stream.

Once you have designed a h[n] and measured a x[n], you
convolve (not multiply) the two in order to estimate whatever
parameters are interesting to you.

I have dliberately been a bit roundabout in the description
here, since the choise of h[n] might depend on the exact
details of what you try to measure. Different measurement
objectives -- as well as different experimental environments
or scenarios -- might call for different processing schemes.

Rune

```
```Jerry Avins skrev:
> Dilip V. Sarwate wrote:
> > "Jerry Avins" <jya@ieee.org> wrote in message
> > news:24Odnbuy4NlDIY3YnZ2dnUVZ_v6dnZ2d@rcn.net...
> >> forums_mp@hotmail.com wrote:
> >>
> >> I can't praise Rick's book too highly on that count, .....
> >
> > Most denizens of comp.dsp (including, of course, Jerry
> > Avins) have very high regard for Rick's book, and I fully
> > understand (and agree) with what Jerry intended the reader
> > to infer from his comment.  That being said, I have always
> > wondered what the literal meaning of the phrase
> >
> >        "can't praise .. too highly on that count..."
> >
> > is.  To my tin ear, it sounds like saying that a moderate
> > (or even a faint) praise is quite adequate on that count,
> > which is surely not the meaning intended.  Ah well, I
> > suspect that the phrase is well-fixed in the idiom by now.
>
> "I can't praise ... too highly" can indeed be construed too ways. It is
> an ambiguity sometimes employed by those forced to describe someone
> they'd rather not. I'm not required to say anything about Rick's on
> anyone else's book, so it means, "No reasonable amount of praise could
> be too much" rather than "I'm unable to praise it very much."

It took a long time before I understood what "invaluable" and
"inarguably" meant...

Rune

```