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