Accumulation of Round-Off Error in Fast Fourier Transforms

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.

REFERENCES

• 1: BINGHAM, C., GODFREY, M. D., AND TUKEY, J.W. Modern techniques of power spectrum estimation. IEEE Trans. A U-15 (June 1967), 56-66.
• 2: COCHRAN, W.T.,ETAL. WhatisthefastFouriertransform?Proc.IEEE55,10(Oct. 1967), 1644-1673.
• 3: COOLEY, J. W., AND TUKEY, J.W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 (April 1965), 297-301.
• 4: FLANAOAN, J.L. Spectrum analysis in speech coding. IEEE Trans. AU-15 (June 1967), 66--69.
• 5: FORSYTHE, G., AN D MOLER, C.B. Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, N. J., 1967.
• 6: GENTLEMAN, W. W., AND SANDE, G. Fast Fourier transform for fun and profit. Prec. AFIPS 1966 Fall Joint Comput. Conf., Vol. 29, Spartan Books, New York, pp. 563-578.
• 7: HELMS, H. D. Fast Fourier transform method of computing difference equations and simulating filters. IEEE Trans. A U-15 (June 1967), 85--90.
• 8: KATZENELSON, J. On errors introduced by combined sampling and quantization. IRE Trans. AC-7 (April 1962), 58--68.
• 9: LIu, B., AND KANEKO, T. Error analysis of digital filters realized with floating-point arithmetic. Proc. IEEE 57 (Oct. 1969), 1735-1747.
• 10: LOHMANN, A. W., AND PARIS, D.P. Binary Fraunhofer holograms generated by computer. Appl. Optics 6 (1967) 1739-1748.
• 11: WATTS, D. J., AND K~TZENELSON, J. Discussion of: On errors introduced by combined sampling and quantization, Vol. AC-7. IEEE Trans. AC-8 (April 1963), 187-188.
• 12: WEINSTEIN, C.J. Roundoff noise in floating point fast Fourier transform computation. IEEE Trans. A U-17 (Sept. 1969), 209-215.
• 13: WEINSTEIS, C., AND OPPENHEIM, A.V. A comparison of rounding noise in floating point and fixed point digital filter realization. Proc. IEEE 57, 6 (June 1969), 1181-1183.
• 14: WELCH, P.D. A fixed-point fast Fourier transform error analysis. IEEE Trans. AU-17 (June 1969), 151-157.
• 15: James H. Wilkinson, Rounding Errors in Algebraic Processes, Dover Publications, Incorporated, 1994

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Error analysis

General Terms:
Algorithms, Measurement, Performance, Reliability, Theory