|LEVEL 0| |HOMEPAGE|

GLOSSARY OF TERMS USED IN TIME SERIES ANALYSIS OF CARDIOVASCULAR DATA

|LEVEL 0| |HOMEPAGE|

Family of computationally efficient algorithms for the calculation of the discrete-time Fourier transform

These algorithms can be applied to evaluate the discrete-time Fourier transform (DFT) of N equispaced samples of a time-series, when N is a highly composite number, generally an integer power of 2. The number of operations required to calculate the straightforward DFT is proportional to N², while those required to calculate the FFT is proportional to log₂N when N is an integer power of 2, and this allows dramatic savings in computational efforts for large N.

When N is not an integer power of 2, or when it is desirable to increase the basic resolution of the FFT, the lenght of the time series can be artificially increased by adding zero-value samples. This method is called zero-padding.

Challis RE, Kitney RI (1991) Biomedical signal processing (in four parts). Part 2 The frequency transform and their inter-relationships. Med. & Biol. Eng. & Comput. 29, 1-17

Links:
FFT by D.Cross (contains source codes in C/C++, Visual Basic, Turbo Pascal and ADA languages)
Fast Fourier Transform by S. Kifowit (contains several FFT algorithms in FORTRAN)
Eric Weisstein's World of Mathematics: FFT