Both sides of the tables are used, and the size must indeed be a power of 2.
The FFT is the "Fast" Fourier Transform because it uses a "butterfly"
algorithm to reduce the work of multiplying a time signal by a VERY LARGE
linear operator matrix (containing time signal length x frequency signal
length elements, hence the power of 2) to get a frequency signal, by knowing
which elements of the matrix would have the same frequency factors. This
reduces one very large matrix-vector dot product to a much smaller set of
2x2 dot products. Any text on DSP or Fourier analysis is likely to have a
nice picture of the butterfly.
-----Original Message-----
From: Niels Gorisse [mailto:niels@bonneville.nl]
Sent: Tuesday, November 30, 1999 8:45 PM
To: saol-dev@media.mit.edu
Subject: fft/ifft
Hi,
I've been playing with the fft/ifft a while, and I noticed that only half
of the tables (re and im) are being used. (For example, with a fft-size of
512, only the first 256 of the re and im tables are used.) I understand it,
but I don't see why the table size must then be the same as the fft/ifft
size. Shouldn't it be more logic to require half the fft-size as the
table-sizes?
Also, must the fft-size be a power of two? In the reference implementation
it gives a runtime error if it is not a power of two, but on the other hand
there are functions provided for if fftsize is not a power of two.
Thanks,
Niels Gorisse
Bonneville
This archive was generated by hypermail 2b29 : Wed May 10 2000 - 12:15:48 EDT