Fundamentals of Statistics contains material of various lectures and courses of H. Lohninger on statistics, data analysis and chemometrics......click here for more. |
Home Bivariate Data Time Series Fourier Transformation Fast Fourier Transform | |
See also: Fourier transformation | |
Fast Fourier TransformThe 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
publications.
|
|
Home Bivariate Data Time Series Fourier Transformation Fast Fourier Transform |