Accumulation of Round-Off Error in Fast Fourier Transforms
- 1 October 1970
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 17 (4), 637-654
- https://doi.org/10.1145/321607.321613
Abstract
The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier coefficients with a substantial time saving over conventional methods. The finite word length used in the computer causes an error in computing the Fourier coefficients. This paper derives explicit expressions for the mean square error in the FFT when floating-point arithmetics are used. Upper and lower bounds for the total relative mean square error are given. The theoretical results are in good agreement with the actual error observed by taking the FFT of data sequences.Keywords
This publication has 4 references indexed in Scilit:
- Error analysis of digital filters realized with floating-point arithmeticProceedings of the IEEE, 1969
- Binary Fraunhofer Holograms, Generated by ComputerApplied Optics, 1967
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- Discussion of "On errors introduced by combined sampling and quantization"IEEE Transactions on Automatic Control, 1963