Reply by Martin Eisenberg●November 13, 20022002-11-13
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
Reply by Amaresh patil●November 13, 20022002-11-13
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.
>
>
>
>
>
>
__________________________________________________
Reply by akash damodar sureka●November 13, 20022002-11-13
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.
Reply by Sameer Kibey●November 12, 20022002-11-12
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
>
Reply by Martin Eisenberg●November 7, 20022002-11-07
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>
Reply by Haymo Kutschbach●November 7, 20022002-11-07
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
Reply by Shankar Shashi●November 7, 20022002-11-07
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
Reply by Martin Eisenberg●November 7, 20022002-11-07
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
Reply by navaneetha krishnan●November 6, 20022002-11-06
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
__________________________________________________
Reply by davi...@wavecom.fr●November 6, 20022002-11-06
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