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 realtime 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 N^{2} multiplications (N is the number of signal samples), the FFT needs only 0.5*N*log_{2}(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 Npoint DFT into two N/2point
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 