Board index » delphi » Re: Sourcecode 2D-FFT

Re: Sourcecode 2D-FFT


2006-11-14 11:43:55 AM
delphi200
Nils Haeck writes:
Quote
Actually I looked it up and I used the one by Singleton, 1968:
faculty.prairiestate.edu/skifowit/fft/fft2.txt

In fact that is *earlier* than Glassmann wrote his article (1970's)..
interesting :)
Yes, Singleton had one of the earliest general mixed-radix
implementations, although I am not sure whether it was *the* earliest.
Certainly, Cooley and Tukey already described the non-power-of-two case
in their 1965 paper (although they only implemented code for powers of
2), and in fact the general mixed-radix decomposition was even
described by Gauss around 1805 (his very first FFT was for N=12).
The occasional attribution of mixed-radix FFTs to Glassman seems to be
a mistake, as far as I can tell.
Regards,
Steven G. Johnson
 
 

Re: Sourcecode 2D-FFT

Nils Haeck writes:
Quote
The shit hits the fan though if you try to do series with lengths of e.g.
1023, or any large prime, since it can not be split up into factors, and thus
it resorts to a very lengthy operation of the standard discrete fourier
transform.
Actually, there are O(N log N) FFT algorithms even for prime N,
although the constant factors are several times worse than for nearby
composite sizes. Google for Rader's FFT algorithm and Bluestein's FFT
algorithm.
(Our FFTW library, www.fftw.org, supports multidimensional FFTs of
arbitrary sizes, including primes, exploiting SSE, of both real and
complex data. It is in C, but of course it is possible to call a C
.DLL file from Delphi: see the instructions at
fftw.org/install/windows.html)
Quote
Btw, the complex FFT can help for sound, because in complex 1D FFT you
transform a real and imaginary part of a complex number. You can fill the
left channel in the real part, the right channel in the imag part, and then
for the price of 1 you can do stereo FFT :)
Note that you then have to disentangle the output (this is described in
e.g. Numerical Recipes) with an extra pass over the data. Especially
for the case of a 2d FFT, it is likely to be more efficient to use an
FFT specialized for real data.
Regards,
Steven G. Johnson