AAC | ADPCM | Convolution | DAFx | FFT | IIR | Mixer | MP3 | MPEG | MPEG-4

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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 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
_____________________________________



Your use of Yahoo! Groups is subject to the 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!

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	_____________________________________

	Your use of Yahoo! Groups is subject to the 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! 

_____________________________________

	Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.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
	__________________________________________________
Do you Yahoo!?
U2 on LAUNCH - Exclusive greatest hits videos
http://launch.yahoo.com/u2
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
	__________________________________________________
Do you Yahoo!?
U2 on LAUNCH - Exclusive greatest hits videos
http://launch.yahoo.com/u2
	_____________________________________

	Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
	Shashi Shankar.H
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
> 
> 
> 
> _____________________________________
> 
>  
> 
>  
> 
>
	________________________________________________________________
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! 
Beim WEB.DE Lottoservice: http://tippen2.web.de/?x=13
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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>
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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
>
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

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.
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hi Akash,

  I can add some spice to ongoing discusion on the
circular convolution. Sameer had explained neatly
concept need of circular convolution.  

 For the first point. If  input data is complex (x(n))
Then convolution also need complex multiplication. Bu
secondly FFT is  less expensive compared to
convolution even though input data is real or complex
for longer sequence.

    Say : u want compute convolution of sequence of
length 4K of x(n) and h(n).
 The total No of multiplication needed for convolution
is  4K^2 which is approximately 16.7M + mac operations
 If u compute convolution in frequency domain consume
less MIPS.

 FFT computation of the X(n) if length 4K is 49 K
   FFT computation of the h(n) is 49 K
Then 4K multiplication  
 inverse FFT computation of the X(n) if length 4K is
49 K
  inverse FFT computation of the h(n) is 49 K so whole
computation 

 49k+49+4K+49K+49K = 200K of mac operations!!!!!!!!!!!

It is going to be very efficient if u r computing.
	Amaresh
	--- akash damodar sureka <akashsureka@akas...>
wrote:
> 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.
> 
> 
> 
> 
> 
>
	__________________________________________________
Do you Yahoo!?
U2 on LAUNCH - Exclusive greatest hits videos
http://launch.yahoo.com/u2
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )

Hello Amaresh,

From: "Amaresh patil" <amaresh_p@amar...>
[snip]
>     Say : u want compute convolution of sequence of
> length 4K of x(n) and h(n).
[snap]

I wonder what kind of impulse response *that* is?
	Martin
	

(You need to be a member of audiodsp -- send a blank email to audiodsp-subscribe@yahoogroups.com )