|You are working with the text-only light edition of "H.Lohninger: Teach/Me Data Analysis, Springer-Verlag, Berlin-New York-Tokyo, 1999. ISBN 3-540-14743-8". Click here for further information.|
|See also: Fourier transformation|
The major drawback of the discrete Fourier transform (DFT) is its slowness. DFT is so slow that a real-time Fourier transform is unrealistic, except for very powerful computers. The discovery of the Fast Fourier Transform (FFT) algorithms by Cooley and Tuckey  changed this. While the DFT requires about N2 multiplications (N is the number of signal samples), the FFT needs only 0.5*N*log2(N) steps. This results, for example, in an improvement of a factor of 200 in calculation time for 1024 data points.
Note that the FFT is just a faster way to perform the DFT. So the FFT is not an approximation - it delivers the same results with the same precision as the DFT.
The basic idea behind the FFT is to split an N-point DFT into two N/2-point
DFTs. This is possible because of the periodicity of the complex exponential
function. The idea of splitting a transform into two smaller ones can be
carried on until only two data points are left (given that we started at
an integer power of 2). More details on the algorithm can be found in numerous
|||J.W. Cooley, J.W. Tukey
An algorithm for the machine calculation of complex Fourier series
Math. of Computation 19 (1965) 297-301
Last Update: 2004-Jul-03