-------- Original Message -------- Subject: Re: Re: [speechcoding] Fast convolution Date: 25 Feb 2005 03:31:46 -0000 From: "venkat ramanan" <> Reply-To: "venkat ramanan" <> To: "Jeff Brower" < hai Thanks for reply. I have a difficulty in taking fft. I have to take a 40 point fft. (all the inputs are always real only). So i padded 24 zeros and make in 2 power and take 64 point fft for both impulse response and the input. and then multiplied the both and take inverse transform. But the result is not much accurate. (i am using fixed point arithmetic). Can anybody suggest a very good way for implementing a 40-point FFT? (I have some material for mixed radix fft and that not clear). Venkat Mistakes are not end of the world but repeating them is |
[Fwd: Re: Re: Fast convolution]
Started by ●February 24, 2005
Reply by ●February 25, 20052005-02-25
Venkat,
To add on to this from Booshan's mail and Jeff's comments,
here are some points to consider.
You mentioned you are doing a 40 point FFT. Please note that any type of
fast convolution has some disadvantages.
They are as follows:
(i) Increased Memory locations on your DSP RAM to do the block
processing, example : Y(w) = H(w)X(w)
(ii) There is also inherent processing delay. You need to store the Frame
and make sure its full before you do the frequency domain multiplication as
compared to time domain convolution which is sample by sample.
With regards to computational savings as Booshan pointed out, with fast
convolution
its O(4*([3N/2 lg(base2)N + N)]) while normal time domain convolution will
use up 2N - 1 assuming equal length sequences of length N.
Fast Convolution is ONLY faster if the following inequality is
satisfied:
6Nlog(base2) N + 4N < N^2
In your case N@, please do the computation above and see if the equality is
satisfied. If not fast convolution is not for your end application as its not
going to help in terms of computational savings. However since N is a power of
2, you need to append zeroes and the nearest Nd.
Even for Fast Hartley there has to be an inequality to be satisfied before
its efficiencies that make it "Fast" are realized.
By the way are you from PSG Tech in Coimbatore? :) One of my good friends
is from there. Keep up the good work. Valka Valarka.
Hope this Helps.
Sincerely,
Shree Jaisimha
In God We Trust.
Jeff Brower <j...@signalogic.com> wrote:
Shree Jaisimha
|