circular convolution again

Hello!

I have some more comments... Akash's points on the comparison between FFT
and convolution are indeed agreeable. But I guess the original query by John
was abt the use of 'circular' convolution and not linear convolution.
Now, if u are going to use convolution for ur application, it will always be
linear convolution, isn't it? u can go for circular convolution as well,
but
then u need to do the zero padding. This, i feel, is like taking the longer
route and should not be preferred. (atleast i have never seen circular convo
being used for linear filtering.)
so coming back to the same q, where exactly is circular convolution used? is
anyone aware of a possible application? or is it that this concept is just
restricted to books?

one more thing.... according to Amaresh's mail, FFT is less expensive for
the special case of input data being a complex signal.
i think signals of significance in practice are generally "real" and
not
complex (eg speech, audio). any examples of complex signals that occur in
real life?

Thanks and regards,
Sameer.
	----- Original Message -----
From: Amaresh patil <amaresh_p@amar...>
To: akash damodar sureka <akashsureka@akas...>; Sameer Kibey
<sameer@same...>
Cc: <audiodsp@audi...>
Sent: Wednesday, November 13, 2002 8:49 PM
Subject: Re: Re: [audiodsp] circular convolution
	> 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.
> >
	

Hello!

I have some more comments... Akash's points on
the comparison between FFT
and convolution are indeed agreeable. But I
guess the original query by John
was abt the use of 'circular'
convolution and not linear convolution.
Now, if u are going to use
convolution for ur application, it will always be
linear convolution,
isn't it? u can go for circular convolution as well, but
then u need
to do the zero padding. This, i feel, is like taking the longer
route and
should not be preferred. (atleast i have never seen circular convo
being
used for linear filtering.)
so coming back to the same q, where exactly is
circular convolution used? is
anyone aware of a possible application? or is
it that this concept is just
restricted to books?

one more
thing.... according to Amaresh's mail, FFT is less expensive for
the
special case of input data being a complex signal.
i think signals of
significance in practice are gener
ally "real" and not
complex (eg speech, audio). any examples of complex
signals that occur in
real life?

Thanks and regards,
Sameer.----- Original Message -----
From: Amaresh patil
<a...@yahoo.com>
To: akash damodar sureka
<a...@rediffmail.com>; Sameer Kibey
<s...@tataelxsi.co.in>
Cc: <a...@yahoogroups.com>
Sent: Wednesday, November 13, 2002 8:49
PM
Subject: Re: Re: [audiodsp] circular convolution

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+49
K = 200K of mac operations!!!!!!!!!!!

It is going to be very
efficient if u r computing.

Amaresh
--- akash damodar sureka
<a...@rediffmail.com>
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.

------------------------ Yahoo! Groups Sponsor
---------------------~-->
Get 128 Bit SSL Encryption!
http://us.click.yahoo.com/JjlUgA/vN2EAA/xGHJAA/26EolB/TM
---------------------------------~->

_____________________________________
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://docs.yahoo.com/info/terms/" target="_blank" rel="nofollow">http://www.dsprelated.com">http://docs.yahoo.com/info/terms/

From: "Sameer Kibey" <sameer@same...>
> Hello!

Hi :)

> I have some more comments... Akash's points
on the comparison
> between FFT and convolution are indeed agreeable. But I guess
> the original query by John was abt the use of 'circular'
convolution
> and not linear convolution.
> Now, if u are going to use convolution for ur application, it will
> always be linear convolution, isn't it? u can go for circular
> convolution as well, but then u need to do the zero padding. This,
> i feel, is like taking the longer route and should not be preferred.
> (atleast i have never seen circular convo being used for linear
> filtering.)

I don't think that FFT filtering is all that uncommon, and that *is*
circular convolution. The point is that we *emulate* linear
convolution by zero padding. This may look construed, but it's worth
the effort for long sequences because of the different computation
cost behaviour of time-domain convolution and FFT.

> so coming back to the same q, where exactly is
circular convolution
> used? is anyone aware of a possible application? or is it that this
> concept is just restricted to books?

Circular convolution is just the nature of the FFT multiplication
method. Normally, we need to work around it as it's not what we want.
But it could have a use in itself: remember that the DFT/FFT really
only gives accurate results when fed a whole number of periods. For
non-periodic input, or "one-period-and-a-bit", it's an
approximation
because the transform still treats the data as periodic.

So, suppose we want to convolve two periodic (and thus formally
infinite) sequences. Here, it doesn't matter if the output is affected
by one single period wrapping around in time, or by the previous
period of the actual signal. They are the same. So we can perform the
convolution by:

--transforming exactly one period of each input
--multiplying the bins
--transforming the product back

The end result is one period of the (also formally infinite)
convolution of the two inputs. Note, though, that this is only valid
if one sequence's period is an integer multiple of the other's so we
can have the DFT bins correspond to the same actual frequency (by
transforming multiple periods of the shorter one)!

> one more thing.... according to Amaresh's
mail, FFT is less
> expensive for the special case of input data being a complex
> signal.

Whether the data are real or complex doesn't really matter. It only
changes above which length the FFT is faster than direct convolution.

> i think signals of significance in practice are
generally "real" and
> not complex (eg speech, audio). any examples of complex
> signals that occur in real life?

The existence of actual complex signals in nature has been the topic
of
much debate on comp.dsp in the past.
	Martin

> Thanks and regards,
> Sameer.
>
>
> ----- Original Message -----
> From: Amaresh patil <amaresh_p@amar...>
> To: akash damodar sureka <akashsureka@akas...>; Sameer Kibey
> <sameer@same...>
> Cc: <audiodsp@audi...>
> Sent: Wednesday, November 13, 2002 8:49 PM
> Subject: Re: Re: [audiodsp] circular convolution
>
>
> > 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.
	

Dr. Ramdas Kumaresan-

> more often than not
...
> multipled by the
> cosine and sine (at carrier frequency)  and low pass filtered 
...

At least as often there is no carrier frequency involved.  In some cases the
downshift is handled in hardware external to the signal processing device.

Jeff Brower
DSP sw/hw engineer
Signalogic
	> Hi guys/gals,
> 
> I do read the material written by this group members but usually do not
respond
> since I am not directly involved in audio signal processing. However
Sameer's
> comments/questions in the last paragraph instigated me to  point out the
following.
> 
> I agree that all signals observed in nature (speech/image etc) or man made
(radar,
> sonar
> communications) are real valued signals. But  before signal processing is
done on
> them,
> more often than not, the signals are converted to complex valued  signals
by the
> process of
> complex (in-phase/quadrature) demodulation. That is, the signal is
multipled by the
> cosine and sine (at carrier frequency)  and low pass filtered to obtain
their
> complex envelopes which is then processed to extract
> any information from them. This preserves all the baseband info contained
in the
> original bandpass signal.
> In general, to understand real signals one has to understand complex
signals first,
> albeit it sounds quirky.
> Infact you can not solve even quadratic equations in real variables with
out
> introducing
> complex numbers.
> 
> R.Kumaresan
> Professor of Electrical Engineering
> Kelley Hall
> University of Rhode Island
> Kingston, RI 02881
> 
> Sameer Kibey wrote:
> 
> > Hello!
> > I have some more comments... Akash's points on the comparison
between FFT
> > and convolution are indeed agreeable. But I guess the original query
by John
> > was abt the use of 'circular' convolution and not linear
convolution.
> > Now, if u are going to use convolution for ur application, it will
always be
> > linear convolution, isn't it? u can go for circular convolution
as well, but
> > then u need to do the zero padding. This, i feel, is like taking the
longer
> > route and should not be preferred. (atleast i have never seen circular
convo
> > being used for linear filtering.)
> > so coming back to the same q, where exactly is circular convolution
used? is
> > anyone aware of a possible application? or is it that this concept is
just
> > restricted to books?
> > one more thing.... according to Amaresh's mail, FFT is less
expensive for
> > the special case of input data being a complex signal.
> > i think signals of significance in practice are gener
> > ally "real" and not
> > complex (eg speech, audio). any examples of complex signals that occur
in
> > real life?
> > Thanks and regards,
> > Sameer.
> > ----- Original Message -----
> > From: Amaresh patil <amaresh_p@amar...>
> > To: akash damodar sureka <akashsureka@akas...>; Sameer Kibey
> > <sameer@same...>
> > Cc: <audiodsp@audi...>
> > Sent: Wednesday, November 13, 2002 8:49 PM
> > Subject: Re: Re: [audiodsp] circular convolution
> >
> >> 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+49
> >> K = 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.
> >> >
> > _____________________________________
> > 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/
> >
> 
> _____________________________________
> 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
> 
> 

Sameer,

I have studied circular convolution extensively, and used it in
subband coding of images. You may wish to look at a paper I
presented at IASTED SIP'97. Unfortunately I don't have access to
the conference CD or the hard drive with my original work. The
title is "On Circular Convolution and Visual Artifacts".

Regards,

Chatonda

--- Sameer Kibey <sameer@same...> wrote:

> Now, if u are going to use convolution for ur
application, it will
> always be
> linear convolution, isn't it? u can go for circular convolution as
> well, but
> then u need to do the zero padding. This, i feel, is like taking the
> longer
> route and should not be preferred. (atleast i have never seen
> circular convo
> being used for linear filtering.)
> so coming back to the same q, where exactly is circular convolution
> used? is
> anyone aware of a possible application? or is it that this concept is
> just
> restricted to books?
> 
> one more thing.... according to Amaresh's mail, FFT is less expensive
> for
> the special case of input data being a complex signal.
> i think signals of significance in practice are generally "real"
and
> not
> complex (eg speech, audio). any examples of complex signals that
> occur in
> real life?
> 
> Thanks and regards,
> Sameer.
> 
> 
> ----- Original Message -----
> From: Amaresh patil <amaresh_p@amar...>
> To: akash damodar sureka <akashsureka@akas...>; Sameer Kibey
> <sameer@same...>
> Cc: <audiodsp@audi...>
> Sent: Wednesday, November 13, 2002 8:49 PM
> Subject: Re: Re: [audiodsp] circular convolution
> 
> 
> > 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.
> > >
> 
> 
>
	====	__________________________________________________