The errors in FFT estimation

摘要

The discrete Fourier transform (DFT) as implemented by the fast Fourier transform (FFT) can be used to approximate values for the continuous Fourier transform (CFT), which is perhaps the main reason why the FFT is in such widespread use. Although it is well known that the FFT values are only approximations for the required CFT values, the exact nature of the approximation errors has never been well understood. Certain authors have stated that the errors must be treated on a function by function basis, some have given empirical rules for bounding them, and others have tried to give a graphical basis for how the errors come about. In this paper we develop exact formulae for the errors for a class of functions (called canonical). These formulae are also shown to hold asymptotically for a much wider class of functions (noncanonical), and between them these two classes cover essentially all functions whose CFTs one may wish to estimate using the FFT.