Please help with Circular Convolution!

Hi everyone, 

I'm currently a student studying electrical engineering at University so
I'm new to both these forums and the subject of DSP in general. 

I would just like to ask how can I compute the circular convolution of the
two sequences: {x(n)} = {4,3,2,1} and {h(n)} = {5,6,7}

I know how to compute the linear convolution, but I am stuck as to how to
do the circular convolution..

Could someone please guide me through this problem step by step?

Any help would be much appreciated,
Thanks,

Sunil Kumar

"Mani007" <thugulystic@hotmail.com> wrote in message 
news:o9Sdna5dipL8aD3VnZ2dnUVZ_uKdnZ2d@giganews.com...
> Hi everyone,
>
> I'm currently a student studying electrical engineering at University so
> I'm new to both these forums and the subject of DSP in general.
>
> I would just like to ask how can I compute the circular convolution of the
> two sequences: {x(n)} = {4,3,2,1} and {h(n)} = {5,6,7}
>
> I know how to compute the linear convolution, but I am stuck as to how to
> do the circular convolution..
>
> Could someone please guide me through this problem step by step?
>
> Any help would be much appreciated,
> Thanks,
>
> Sunil Kumar
>

You can look at entry #24 in my 'how to' page below for a Matab and 
Mathematica examples

http://12000.org/my_notes/mma_matlab_control/howto.htm

Nasser

On Aug 11, 10:28 pm, "Mani007" <thugulys...@hotmail.com> wrote:
> Hi everyone,
>
> I'm currently a student studying electrical engineering at University so
> I'm new to both these forums and the subject of DSP in general.
>
> I would just like to ask how can I compute the circular convolution of the
> two sequences: {x(n)} = {4,3,2,1} and {h(n)} = {5,6,7}

immediately a confusion in  your stated problem is that x[n] and h[n]
are different lengths.  if it were linear convolution, there would be
no confusion because we assume that both x[n] and h[n] are zero-padded
on both sides to n=infinity.  the result will be of non-zero length of
4+3-1 = 6.

but if it were circular convolution, the two input sequences must be
of the same length (assumed periodically extended instead of zero
padded) and the output is of the same length (and periodic).

> I know how to compute the linear convolution, but I am stuck as to how to
> do the circular convolution..

circular convolution is what happens naturally when you DFT (or FFT)
two equal-length sequences, pointwise multiply those results together,
and inverse DFT the product sequence.

r b-j

"robert bristow-johnson" <rbj@audioimagination.com> wrote in message 
news:da25d6f3-8862-4f4e-857f-99c7109d4f00@a1g2000hsb.googlegroups.com...

>.....if it were linear convolution, there would be
> no confusion because we assume that both x[n] and h[n] are zero-padded
> on both sides to n=infinity.

Hmmmm... now why would we assume *that*?  the padding I mean.

I would simply compute the convolution of two finite-length sequences and 
come up directly with a sequence of length M + N -1 and that would be it.

Naturally, my assumption is that the sequences as given are zero everywhere 
else but I don't need to pad them in order to compute the convolution. 
Semantics I guess.  That is, to me padding is an operation with observable 
results.  But convolution of two finite-length sequences is finite and 
that's how I treat it.

Circular convolution is just as neatly envisioned in the time domain on a 
periodic sequence of finite-length periods.  In order for the convolution to 
not overlap, one needs to choose a period that's adequate for the result - 
namely >= M + N -1.

Fred 

On Aug 12, 8:17 pm, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "robert bristow-johnson" <r...@audioimagination.com> wrote in message
>
> news:da25d6f3-8862-4f4e-857f-99c7109d4f00@a1g2000hsb.googlegroups.com...
>
> >.....if it were linear convolution, there would be
> > no confusion because we assume that both x[n] and h[n] are zero-padded
> > on both sides to n=infinity.
>
> Hmmmm... now why would we assume *that*?  the padding I mean.
>
> I would simply compute the convolution of two finite-length sequences and
> come up directly with a sequence of length M + N -1 and that would be it.
>
> Naturally, my assumption is that the sequences as given are zero everywhere
> else

how is that different from my assumption?  call it assuming "that the
sequences as given are zero everywhere else" or "padding with zeroes",
but ain't it the same beginning and end?  we start with some finite-
lengthed sequence that is not defined outside of its original
definition and we have a general convolution equation as:

            +inf
    y[n] = SUM{ h[m] x[n-m] }
           m=-inf

how do we get from one place to the other?  we assume what x[n] and
h[m] are outside of their definitions to make the above equation make
sense.  you assume they're zero everywhere else and i do the same.
but i call it "zero-padding".

> but I don't need to pad them in order to compute the convolution.
> Semantics I guess.

yup.

>  That is, to me padding is an operation with observable results.

sometimes it is an explicit operation.

>  But convolution of two finite-length sequences is finite and
> that's how I treat it.

i treat the finite-length case as a degenerate of the general case
with +/-inf in the limits.

> Circular convolution is just as neatly envisioned in the time domain on a
> periodic sequence of finite-length periods.

that's true.  i consider that circular convolution is often not what
is desired, but what you get when you use the DFT.  but you can do it
or envision it as a time-domain operation if you periodically extend
the data going in.

>  In order for the convolution to
> not overlap, one needs to choose a period that's adequate for the result -
> namely >= M + N -1.

i still cannot understand a consistent and commutative mathematical
definition for circular convolution without both input sequences being
identical length (and assumed periodically extended).

r b-j

robert bristow-johnson wrote:
> 
> On Aug 12, 8:17 pm, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
> wrote:
> > "robert bristow-johnson" <r...@audioimagination.com> wrote in message
> >
> > news:da25d6f3-8862-4f4e-857f-99c7109d4f00@a1g2000hsb.googlegroups.com...
> >
> > >.....if it were linear convolution, there would be
> > > no confusion because we assume that both x[n] and h[n] are zero-padded
> > > on both sides to n=infinity.
> >
> > Hmmmm... now why would we assume *that*?  the padding I mean.
> >
> > I would simply compute the convolution of two finite-length sequences and
> > come up directly with a sequence of length M + N -1 and that would be it.
> >
> > Naturally, my assumption is that the sequences as given are zero everywhere
> > else
> 
> how is that different from my assumption?  call it assuming "that the
> sequences as given are zero everywhere else" or "padding with zeroes",
> but ain't it the same beginning and end?  we start with some finite-
> lengthed sequence that is not defined outside of its original
> definition and we have a general convolution equation as:
> 
>             +inf
>     y[n] = SUM{ h[m] x[n-m] }
>            m=-inf
> 
> how do we get from one place to the other?  we assume what x[n] and
> h[m] are outside of their definitions to make the above equation make
> sense.  you assume they're zero everywhere else and i do the same.
> but i call it "zero-padding".

Why would the OP to extend h(m) beyond its natural length to make his
implementation work? Would anyone ever extend h[m] in an actual direct
implementation of convolution? (direct means not using DFT) 



> i still cannot understand a consistent and commutative mathematical
> definition for circular convolution without both input sequences being
> identical length (and assumed periodically extended).
>

	Technically yes both sequences must be infinite to simplify the task
of defining the spectrum and if you make the extended values zeroes
that also makes it easier.  But in reality x[n] and h[m] aren't ever
infinite and usually nobody would make either sequence longer than it
needs to be to get the job done. The OP was asking about how to do a
actual implementation.  


	Adding zeroes to extend x[n] is a choice. There are other possible
values that can be used to extend x[n] - for instance - mirroring or
repeating the existing values in x[n]. If you extend x[n] by repeating
the existing pattern of x[n] then that would be implementing what is
called circular convolution. 
	So that is the answer to the OP's question just use the same
algorithm he already has but extend x[n] by repeating as far as you
need to. One can guess that his implementation of linear convolution
involved extending x[n] with zeroes, but we don't know since he didn't
say.

	 If his notation follows normal conventions h[m] doesn't need any
extension with extra values for actual implementation. If convolution
is circular then it is by convention that x[n] is extended by
repeating the existing values as far as needed. That means h[m] could
be any length including longer than x[n]. 

-jim


----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= - Total Privacy via Encryption =---

On Aug 13, 1:54&#4294967295;pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
>
> &#4294967295; &#4294967295; &#4294967295; &#4294967295; Adding zeroes to extend x[n] is a choice. There are other possible
> values that can be used to extend x[n] - for instance - mirroring or
> repeating the existing values in x[n]. If you extend x[n] by repeating
> the existing pattern of x[n] then that would be implementing what is
> called circular convolution.

But that operation has no particularly meaningful interpretation (at
least in an LTI framework) as far as I'm aware.  Zero-padding to a
commensurate length before CC (circular convolution) can be
interpreted as a filtering operation - i.e. multiplying the frequency-
domain representations of the two signals (interpolated
appropriately).  Repeating the signal is much more arbitrary; if the
length of x isn't an integer multiple of the length of h, you'll get
edge effects; if it is a multiple, you'll get an effect equivalent to
zero-stuffing the frequency response of h before multiplication.

I suppose that that could be useful in certain circumstances, but as a
general rule, I don't think it's how CC is commonly used; I've never
seen a description of CC that describes anything other than zero-
extension.


--
Oli

Oli Charlesworth wrote:
> 
> On Aug 13, 1:54 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> >
> >         Adding zeroes to extend x[n] is a choice. There are other possible
> > values that can be used to extend x[n] - for instance - mirroring or
> > repeating the existing values in x[n]. If you extend x[n] by repeating
> > the existing pattern of x[n] then that would be implementing what is
> > called circular convolution.
> 
> But that operation has no particularly meaningful interpretation (at
> least in an LTI framework) as far as I'm aware.  Zero-padding to a
> commensurate length before CC (circular convolution) can be
> interpreted as a filtering operation - i.e. multiplying the frequency-
> domain representations of the two signals (interpolated
> appropriately).  

Zero padding of the h[] sequence has no affect on the output if you
are not using DFT.


>Repeating the signal is much more arbitrary; if the
> length of x isn't an integer multiple of the length of h, you'll get
> edge effects; if it is a multiple, you'll get an effect equivalent to
> zero-stuffing the frequency response of h before multiplication.

So you are saying that the only implementation for circular
convolution that works is to do it via DFT?


> 
> I suppose that that could be useful in certain circumstances, but as a
> general rule, I don't think it's how CC is commonly used; I've never
> seen a description of CC that describes anything other than zero-
> extension.

by "description" do you mean of theory or the do you mean the
description of the actual implementation.

-jim


> 
> --
> Oli


----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= - Total Privacy via Encryption =---

On Aug 13, 6:16&#4294967295;pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> Oli Charlesworth wrote:
>
> > On Aug 13, 1:54 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
>
> > > &#4294967295; &#4294967295; &#4294967295; &#4294967295; Adding zeroes to extend x[n] is a choice. There are other possible
> > > values that can be used to extend x[n] - for instance - mirroring or
> > > repeating the existing values in x[n]. If you extend x[n] by repeating
> > > the existing pattern of x[n] then that would be implementing what is
> > > called circular convolution.
>
> > But that operation has no particularly meaningful interpretation (at
> > least in an LTI framework) as far as I'm aware. &#4294967295;Zero-padding to a
> > commensurate length before CC (circular convolution) can be
> > interpreted as a filtering operation - i.e. multiplying the frequency-
> > domain representations of the two signals (interpolated
> > appropriately). &#4294967295;
>
> Zero padding of the h[] sequence has no affect on the output if you
> are not using DFT.
>
> >Repeating the signal is much more arbitrary; if the
> > length of x isn't an integer multiple of the length of h, you'll get
> > edge effects; if it is a multiple, you'll get an effect equivalent to
> > zero-stuffing the frequency response of h before multiplication.
>
> So you are saying that the only implementation for circular
> convolution that works is to do it via DFT?

No, not at all.  But in DSP, the techniques used are typically in a
scenario where a frequency-domain interpretation is equally
appropriate.  Performing a circular convolution as you suggested would
be mathematically equivalent to doing what I described via the
frequency domain, which almost certainly isn't what the OP wants.

>
> > I suppose that that could be useful in certain circumstances, but as a
> > general rule, I don't think it's how CC is commonly used; I've never
> > seen a description of CC that describes anything other than zero-
> > extension.
>
> by "description" do you mean of theory or the do you mean the
> description of the actual implementation.

Theory, I guess.  But typically in a context that leads straight onto
an application.


--
Oli

Oli Charlesworth wrote:

> >
> > So you are saying that the only implementation for circular
> > convolution that works is to do it via DFT?
> 
> No, not at all.  But in DSP, the techniques used are typically in a
> scenario where a frequency-domain interpretation is equally
> appropriate.  Performing a circular convolution as you suggested would
> be mathematically equivalent to doing what I described via the
> frequency domain, which almost certainly isn't what the OP wants.

Oh. I thought it was what he wanted. neber mind.  

-jim

> 
> >
> > > I suppose that that could be useful in certain circumstances, but as a
> > > general rule, I don't think it's how CC is commonly used; I've never
> > > seen a description of CC that describes anything other than zero-
> > > extension.
> >
> > by "description" do you mean of theory or the do you mean the
> > description of the actual implementation.
> 
> Theory, I guess.  But typically in a context that leads straight onto
> an application.
> 
> --
> Oli


----== Posted via Pronews.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.pronews.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= - Total Privacy via Encryption =---