circular convolution

Hello friends,

I have trouble in understand the concept and the application of circular
convolution.  Wonder if someone can help me out a bit please!

I came across this statement from a text "... circular convolution of 2
sequences is found by performing the linear convolution and aliasing the
result...."

In eqn format, the text defined circular convolution as 
y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
where R(n)=1 if  0<=n<N
and zero elsewhere

How does the aliasing part come in?
Note:  I do understand that graphically, circular convolution can represented by
the sum of the product of two concentric circles that represent h(n) and x(n)
with one of the ring rotating.  Does this rotational action a hint about
aliasing or I am just a stupid martian learning dsp.

In regular filtering, say a filter frequency response is found to be h(n).  Then
to apply this filter to an input signal x(n), we perform linear convolution,
i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
but for speed, we probably do the above in freq domain if x(n) is considerably
long (windowing and all that).  Then what is the application of circular
convolution?

Thanks in advance.
John
	

Hey John,

 As a DSP student, personally, to see Circular Conv. as "time-domian aliasing" is a bit confusing and unneccessary, so I just forgot the idea (I know its got to do with the inevitable overlap in each processed block of the signal). What's important is that to perform linear conv. with circular conv. the signals must be time-limited to avoid time-domain aliasing.

Circular conv is best used when applied through efficient DFT algorithms. Its interesting that linear conv. can be applied "faster" through DFT multiplication, which is circular convolution. ...and even faster with FFTs &/or STFTs....

Later, br />
----- Original Message -----
From: "John Lai"
Date: Mon, 4 Nov 2002 23:55:21 -0500
To:
Subject: [audiodsp] circular convolution

Hello friends,

I have trouble in understand the concept and the application of circular convolution.  Wonder if someone can help me out a bit please!

I came across this statement from a text "... circular convolution of 2 sequences is found by performing the linear convolution and aliasing the result...."

In eqn format, the text defined circular convolution as
y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
where R(n)=1 if  0<=n and zero elsewhere

How does the aliasing part come in?
Note:  I do understand that graphically, circular convolution can represented by the sum of the product of two concentric circles that represent h(n) and x(n) with one of the ring rotating.  Does this rotational action a hint about aliasing or I am just a stupid martian learning dsp.

In regular filtering, say a filter frequency response is found to be h(n).  Then to apply this filter to an input signal x(n), we perform linear convolution,
i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
but for speed, we probably do the above in freq domain if x(n) is considerably long (windowing and all that).  Then what is the application of circular convolution?

Thanks in advance.
John
_____________________________________
Note: If you do a simple "reply" with your email client, only the author of this message will receive your answer.  You need to do a "reply all" if you want your answer to be distributed to the entire group.

_____________________________________
About this discussion group:

To Join:  a...@yahoogroups.com

To Post:  a...@yahoogroups.com

To Leave: a...@yahoogroups.com

Archives: http://groups.yahoo.com/group/audiodsp

Other DSP-Related Groups: http://www.dsprelated.com


">Yahoo! Terms of Service.

junk ALERT!!!
If you've received this message it means you receive too much junk. Please
block this sender or may regret it the rest of your days.

_______________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com

Single ready to mingle? lavalife.com: Where singles click. Free to Search!

Hi,

Multiplying two FFTs can sometimes be less expansive than performing 
convolution (especially when you are already working in the frequency 
domain).
However, consider that performing an FFT is the same as performing the 
dicrete Fourier transform of the same signal, but periodized in the time 
domain (and so discretized in the spectral domain).
Then multiplying two FFTs, you've got, back to time domain, the 
convolution between to periodized signals, and not between the signal on 
which you wanted to perform convolution. To avoid it, you have to perform 
the FFT of the signal padded in time domain with enough zeroes so that 
circular convolution and linear convolution give the same results.
	regards

David
	D <bacardi@baca...>
06/11/02 01:59
	        To:     "John Lai" <john.lai@john...>, audiodsp@audi...
        cc: 
        Subject:        Re: [audiodsp] circular convolution

Hey John,
 As a DSP student, personally, to see Circular Conv. as "time-domian 
aliasing" is a bit confusing and unneccessary, so I just forgot the idea 
(I know its got to do with the inevitable overlap in each processed block 
of the signal). What's important is that to perform linear conv. with 
circular conv. the signals must be time-limited to avoid time-domain 
aliasing.
Circular conv is best used when applied through efficient DFT algorithms. 
Its interesting that linear conv. can be applied "faster" through DFT 
multiplication, which is circular convolution. ...and even faster with 
FFTs &/or STFTs....
Later, 
----- Original Message -----
From: "John Lai" 
Date: Mon, 4 Nov 2002 23:55:21 -0500
To: 
Subject: [audiodsp] circular convolution

Hello friends,

I have trouble in understand the concept and the application of circular 
convolution.  Wonder if someone can help me out a bit please!

I came across this statement from a text "... circular convolution of 2 
sequences is found by performing the linear convolution and aliasing the 
result...."

In eqn format, the text defined circular convolution as 
y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
where R(n)=1 if  0<=n and zero elsewhere

How does the aliasing part come in?
Note:  I do understand that graphically, circular convolution can 
represented by the sum of the product of two concentric circles that 
represent h(n) and x(n) with one of the ring rotating.  Does this 
rotational acti! on a hint about aliasing or I am just a stupid martian 
learning dsp.

In regular filtering, say a filter frequency response is found to be h(n). 
 Then to apply this filter to an input signal x(n), we perform linear 
convolution,
i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
but for speed, we probably do the above in freq domain if x(n) is 
considerably long (windowing and all that).  Then what is the application 
of circular convolution?

Thanks in advance.
John
	_____________________________________
Note: If you do a simple "reply" with your email client, only the
author 
of this message will receive your answer.  You need to do a "reply
all" if 
you want your answer to be distributed to the entire group.

_____________________________________
About this discussion group:

To Join:  audiodsp-subscribe@audi...

To Post:  audiodsp@audi...

To Leave: audiodsp-uns! ubscribe@ubsc...

Archives: http://groups.yahoo.com/group/audiodsp

Other DSP-Related Groups: http://www.dsprelated.com
	 
junk ALERT!!!
If you've received this message it means you receive too much junk. Please 
block this sender or may regret it the rest of your days.
-- 
_______________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com

Single & ready to mingle? lavalife.com: Where singles click. Free to Search!


_____________________________________
Note: If you do a simple "reply" with your email client, only the
author 
of this message will receive your answer.  You need to do a "reply
all" if 
you want your answer to be distributed to the entire group.

_____________________________________
About this discussion group:

To Join:  audiodsp-subscribe@audi...

To Post:  audiodsp@audi...

To Leave: audiodsp-unsubscribe@audi...

Archives: http://groups.yahoo.com/group/audiodsp

Other DSP-Related Groups: http://www.dsprelated.com
	
	

Hi,

 Oppenheim & Schafer's DTSP book has a good
explanation about DFT, circular convolution and time
domain aliasing. The text is in the chapter where he
introduces DFT. 

Its all because DFT assumes the signal is periodic
where as in practice we apply it to all kinds of
signals.

Regards
Navan

--- John Lai <john.lai@john...> wrote:
> Hello friends,
> 
> I have trouble in understand the concept and the
> application of circular convolution.  Wonder if
> someone can help me out a bit please!
> 
> I came across this statement from a text "...
> circular convolution of 2 sequences is found by
> performing the linear convolution and aliasing the
> result...."
> 
> In eqn format, the text defined circular convolution
> as 
> y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
> where R(n)=1 if  0<=n<N
> and zero elsewhere
> 
> How does the aliasing part come in?
> Note:  I do understand that graphically, circular
> convolution can represented by the sum of the
> product of two concentric circles that represent
> h(n) and x(n) with one of the ring rotating.  Does
> this rotational action a hint about aliasing or I am
> just a stupid martian learning dsp.
> 
> In regular filtering, say a filter frequency
> response is found to be h(n).  Then to apply this
> filter to an input signal x(n), we perform linear
> convolution,
> i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
> but for speed, we probably do the above in freq
> domain if x(n) is considerably long (windowing and
> all that).  Then what is the application of circular
> convolution?
> 
> Thanks in advance.
> John
	__________________________________________________

	

Hello,

there's an explanation and nice depiction of circular convolution in
Numerical Recipes, Ch. 13.1.
http://www.library.cornell.edu/nr/bookcpdf.html
	Martin

From: "navaneetha krishnan" <epowerx@epow...>
> Hi,
>
>  Oppenheim & Schafer's DTSP book has a good
> explanation about DFT, circular convolution and time
> domain aliasing. The text is in the chapter where he
> introduces DFT.
>
> Its all because DFT assumes the signal is periodic
> where as in practice we apply it to all kinds of
> signals.
>
> Regards
> Navan
>
> --- John Lai <john.lai@john...> wrote:
> > Hello friends,
> >
> > I have trouble in understand the concept and the
> > application of circular convolution.  Wonder if
> > someone can help me out a bit please!
> >
> > I came across this statement from a text "...
> > circular convolution of 2 sequences is found by
> > performing the linear convolution and aliasing the
> > result...."
> >
> > In eqn format, the text defined circular convolution
> > as
> > y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
> > where R(n)=1 if  0<=n<N
> > and zero elsewhere
> >
> > How does the aliasing part come in?
> > Note:  I do understand that graphically, circular
> > convolution can represented by the sum of the
> > product of two concentric circles that represent
> > h(n) and x(n) with one of the ring rotating.  Does
> > this rotational action a hint about aliasing or I am
> > just a stupid martian learning dsp.
> >
> > In regular filtering, say a filter frequency
> > response is found to be h(n).  Then to apply this
> > filter to an input signal x(n), we perform linear
> > convolution,
> > i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
> > but for speed, we probably do the above in freq
> > domain if x(n) is considerably long (windowing and
> > all that).  Then what is the application of circular
> > convolution?
> >
> > Thanks in advance.
> > John
	

hi, 
"Scientists and Engineers guide to DSP" by stephen smith gives the
best description about circular convolution.
-shashi
 navaneetha krishnan <epowerx@epow...> wrote:Hi,

Oppenheim & Schafer's DTSP book has a good
explanation about DFT, circular convolution and time
domain aliasing. The text is in the chapter where he
introduces DFT. 

Its all because DFT assumes the signal is periodic
where as in practice we apply it to all kinds of
signals.

Regards
Navan

--- John Lai <john.lai@john...> wrote:
> Hello friends,
> 
> I have trouble in understand the concept and the
> application of circular convolution.  Wonder if
> someone can help me out a bit please!
> 
> I came across this statement from a text "...
> circular convolution of 2 sequences is found by
> performing the linear convolution and aliasing the
> result...."
> 
> In eqn format, the text defined circular convolution
> as 
> y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
> where R(n)=1 if  0<=n<N
> and zero elsewhere
> 
> How does the aliasing part come in?
> Note:  I do understand that graphically, circular
> convolution can represented by the sum of the
> product of two concentric circles that represent
> h(n) and x(n) with one of the ring rotating.  Does
> this rotational action a hint about aliasing or I am
> just a stupid martian learning dsp.
> 
> In regular filtering, say a filter frequency
> response is found to be h(n).  Then to apply this
> filter to an input signal x(n), we perform linear
> convolution,
> i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
> but for speed, we probably do the above in freq
> domain if x(n) is considerably long (windowing and
> all that).  Then what is the application of circular
> convolution?
> 
> Thanks in advance.
> John
	__________________________________________________

	_____________________________________
Note: If you do a simple "reply" with your email client, only the
author of this message will receive your answer.  You need to do a "reply
all" if you want your answer to be distributed to the entire group.

_____________________________________
About this discussion group:

To Join:  audiodsp-subscribe@audi...

To Post:  audiodsp@audi...

To Leave: audiodsp-unsubscribe@audi...

Archives: http://groups.yahoo.com/group/audiodsp

Other DSP-Related Groups: http://www.dsprelated.com
	
	Shashi Shankar.H
	

Hello John,

my advise is to take a look at the excellent book of Steven W. 
Smith "The Scientist and Engineer's Guide to Digital Signal 
Processing". It is very understandable and free for downloading too (of
course you can 
also buy one, if you like ;) !!
You can find it at www.dspguide.com 
There is a chapter about (circular) convolution which breaks the whole 
thing down to some expressive pictures....

Haymo 

"John Lai" <john.lai@john...> schrieb am 05.11.02 14:04:26:
> Hello friends,
> 
> I have trouble in understand the concept and the application of circular
convolution.  Wonder if someone can help me out a bit please!
> 
> I came across this statement from a text "... circular convolution of
2 sequences is found by performing the linear convolution and aliasing the
result...."
> 
> In eqn format, the text defined circular convolution as 
> y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
> where R(n)=1 if  0<=n<N
> and zero elsewhere
> 
> How does the aliasing part come in?
> Note:  I do understand that graphically, circular convolution can
represented by the sum of the product of two concentric circles that represent
h(n) and x(n) with one of the ring rotating.  Does this rotational action a hint
about aliasing or I am just a stupid martian learning dsp.
> 
> In regular filtering, say a filter frequency response is found to be h(n). 
Then to apply this filter to an input signal x(n), we perform linear
convolution,
> i.e. y(n) = h(n)*x(n)=summation(k=0,N-1) h(k)x(n-k)
> but for speed, we probably do the above in freq domain if x(n) is
considerably long (windowing and all that).  Then what is the application of
circular convolution?
> 
> Thanks in advance.
> John
> 
> 
> 
> _____________________________________
> Note: If you do a simple "reply" with your email client, only the
author of this message will receive your answer.  You need to do a "reply
all" if you want your answer to be distributed to the entire group.
> 
> _____________________________________
> About this discussion group:
> 
> To Join:  audiodsp-subscribe@audi...
> 
> To Post:  audiodsp@audi...
> 
> To Leave: audiodsp-unsubscribe@audi...
> 
> Archives: http://groups.yahoo.com/group/audiodsp
> 
> Other DSP-Related Groups: http://www.dsprelated.com
>  
> 
> ">http://docs.yahoo.com/info/terms/ 
> 
>
	________________________________________________________________
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! 
Beim WEB.DE Lottoservice: http://tippen2.web.de/?x
	

From: "Shankar Shashi" <shashishankar_h@shas...>
> hi, 
> "Scientists and Engineers guide to DSP" by stephen
> smith gives the best description about circular convolution.

And it's also on the net at http://www.dspguide.com/pdfbook.htm.
	Martin

<snip>
	

Hello John

here is my feedback on the circular convolution query... may or may not be
of help, but i am sending it anyway.

Imagine that you want to filter a sequence x[n] and h[n] is the impulse
response of the filter under consideration. ( both h[n] and x[n] are
discrete time sequences).One way of doing this is use of  linear
convolution.As we know convolution in time domain is equivalent to product
of the spectra in frequency domain. So obviously another method of filtering
is to multiply the spectrum of the input sequence and frequency response of
the filter. The inverse transform of the product will give the filtered
output sequence.

Unfortunately the spectrum of a discrete time signal is "continuous"
and not
discrete.So if you want to store the spectra of these two (so that you can
take the product), you need to discretize them first.  This is achieved by
"sampling" the spectrum and as is known, sampling the spectrum is
nothing
but taking the DFT (of the time domain sequence).

So you have the DFTs of x[n] and h[n] and now you can perform the filtering
in frequency domain. But here is the hitch! What you get in the time domain
after this filtering need not be same as the result of linear convolution...
and your answer may be incorrect. This is logical since you have taken the
product of "sampled" spectra and not the actual, continuous ones .This
possibly incorrect result in time domain can be infact be described by the
"circular" convolution operation.

So the bottomline is : the product of two DFTs in freq domain is equivalent
to circular convolution in time domain.

Now lets see how "aliasing" comes in the picture wrt circular
convolution.
originally ur input sequence is say, an aperiodic signal of length L. when u
sample its spectrum u essentially multiply the spectrum with a set of
impulses. Since the transform of train of impulse is again a train of
impulses (and since convolution of an impulse with a signal gives the same
signal), the time domain counterpart turns out to be periodic. If the period
is not sufficiently large, aliasing shall result. Lets say you take N
samples of the spectrum (better said : N point DFT)...  the condition to
avoid aliasing is N >= L , as DSP literature will tell you.

So the key is that if you want to exactly recover your original signal from
its periodic extension, pad it with enough zeros so that N>=L and then take
the N point DFT, process it and then take the N point IDFT .If you do this
for both x[n] and h[n] (ie zero padding ) and then take the product of DFTs,
after IDFT your result (in time domain : circular convo's output) will be
the same as that of linear convolution. And this is what u want... not the
"aliased" output. For some reason if you don't want the right
result, you
don't pad the sequences with zeros , take DFT etc and ultimately obtain the
"aliased" result. This could have also been obtained by taking (1)
circular
convo of the two sequences and (2) linear convo of the two followed by
aliasing the result.

I hope that explains the statement "... circular convolution of 2 sequences
is found by performing the linear convolution and aliasing the result...."

Note that the use of FFT algorithms makes DFT method of filtering superior
to the normal linear convo... and to analyse the effect in time domain, we
need to study circular convo. As far as practical application of circular
convolution is concerned, i could not find anything significant. (Why use
convolution when u have FFT at ur diposal?) Any comments on this?

Best regards,
Sameer Kibey.

----- Original Message -----
From: John Lai <john.lai@john...>
To: <audiodsp@audi...>
Sent: Tuesday, November 05, 2002 10:25 AM
Subject: [audiodsp] circular convolution
	> Hello friends,
>
> I have trouble in understand the concept and the application of circular
convolution.  Wonder if someone can help me out a bit please!
>
> I came across this statement from a text "... circular convolution of
2
sequences is found by performing the linear convolution and aliasing the
result...."
>
> In eqn format, the text defined circular convolution as
> y(n)=[summation(k=0,N-1) h(k)x(n-k)]R(n)
> where R(n)=1 if  0<=n<N
> and zero elsewhere
>
> How does the aliasing part come in?
> Note:  I do understand that graphically, circular convolution can
represented by the sum of the product of two concentric circles that
represent h(n) and x(n) with one of the ring rotating.  Does this rotational
action a hint about aliasing or I am just a stupid martian learning dsp.
>
> In regular filtering, say a filter frequency response is found to be h(n).
Then to apply this filter to an input signal x(n), we perform linear
convolution,
> i.e. y(n) = h(n)*x(n)=summation(k=0,N-1)
h(k)x(n-k)
> but for speed, we probably do the above in freq domain if x(n) is
considerably long (windowing and all that).  Then what is the application
of
circular convolution?
>
> Thanks in advance.
> John
>
	

Hi Sameer,
    Here is the comment on ur question on:
    why do we use convolution when we have FFT at our disposal??

    well, what i think are the following points:

1) FFT requires complex multiplications, so may DSPs don't support 
direct complex multiplications or other complex instructions. 
whereas convolution needs just a "mac" instruction which is 
supported by many dsps and there are lot many algos to optimize 
it.

2)Converting time domain to frequecny domain may lose the 
precision in fix point while doing FFT calculations which may not 
be desirable for certain applications.

3)Certain applications requires a constant delay which can be 
produced by convolution but not by FFT.

  So we don't go for FFT always, thats what i guess.

   If any comments, u r always welcome.

akash.