Please help with Circular Convolution!

Started by Mani007 August 11, 2008
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&#2013266080;pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> > &#2013266080; &#2013266080; &#2013266080; &#2013266080; 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&#2013266080;pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote:
> Oli Charlesworth wrote: > > > On Aug 13, 1:54 pm, jim <"sjedgingN0sp"@m...@mwt.net> wrote: > > > > &#2013266080; &#2013266080; &#2013266080; &#2013266080; 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. &#2013266080;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). &#2013266080; > > 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 =---