🚀 go-pugleaf

Hi, everybody!

I am trying to implement an algorithm for computing the FFT with an
arbitrary number of samples, i.e., not necessarly equal to a power of
two.

I am using the algorithm proposed by Brigham in his book "The Fast
Fourier Transform". The algorithm appears, for those who have the book,
in page 195, equations 12-47 to 12-49.

Basicly, one transforms the formula 

X(n_) = Sum[x[k] W^(nk), {k, 0, N-1}]

into

X(n_) = W^(n^2/2) Sum[y[k] h[n-k], {k, 0, N-1}]

where N is the number of samples, W = Exp[-I 2 Pi/N], 
y[k_] = W^(k^2/2) x[k] and h[k_] = W^(-k^2/2).

One then extends y[k] and h[k] with sufficient zeros so the number of
samples becomes a power of 2. Now one uses the convolution theorem,
i.e., the the trasform of the convolution is the product of the
transform.

Well, in the paper, the things seems right, but inb practice they just
don't work. And, after verifying the code a milion times, I am pretty
sure the problem is with the algorithm (or with a very pretty and stupid
error I am doing, who knows?).

Appreciate any help.

Thank you!

Regards,
Carlos Antunes.
-- 
Carlos Antunes @ INESC - Instituto de Engenharia de Sistemas e Computadores
E-mail to cma@inesc.pt