{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T19:57:40Z","timestamp":1649102260221},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1970,10]]},"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.<\/jats:p>","DOI":"10.1145\/321607.321613","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"637-654","source":"Crossref","is-referenced-by-count":64,"title":["Accumulation of Round-Off Error in Fast Fourier Transforms"],"prefix":"10.1145","volume":"17","author":[{"given":"Toyohisa","family":"Kaneko","sequence":"first","affiliation":[{"name":"IBM, Thomas J. Watson Research Center, Yorktown Heights, New York and Princeton University, Department of Electrical Engineering, Princeton, New Jersey"}]},{"given":"Bede","family":"Liu","sequence":"additional","affiliation":[{"name":"Princeton University, Department of Electrical Engineering, Princeton, New Jersey"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"56","article-title":"Modern techniques of power spectrum estimation","author":"BINGHAM C.","year":"1967","journal-title":"IEEE Trans. A U-15"},{"key":"e_1_2_1_2_2","unstructured":"COCHRAN W.T. ETAL. WhatisthefastFouriertransform?Proc.IEEE55 10(Oct. 1967) 1644-1673. COCHRAN W.T. ETAL. WhatisthefastFouriertransform?Proc.IEEE55 10(Oct. 1967) 1644-1673."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1090\/S0025-5718-1965-0178586-1","article-title":"An algorithm for the machine calculation of complex Fourier series","volume":"19","author":"COOLEY J. W.","year":"1965","journal-title":"Math. Comput."},{"key":"e_1_2_1_4_2","first-page":"66","article-title":"Spectrum analysis in speech coding","author":"FLANAOAN J.L","year":"1967","journal-title":"IEEE Trans. AU-15"},{"key":"e_1_2_1_5_2","unstructured":"FORSYTHE G. AN D MOLER C.B. Computer Solution of Linear Algebraic Systems. Prentice-Hall Englewood Cliffs N. J. 1967. FORSYTHE G. AN D MOLER C.B. Computer Solution of Linear Algebraic Systems. Prentice-Hall Englewood Cliffs N. J. 1967."},{"key":"e_1_2_1_6_2","first-page":"563","volume-title":"Prec. AFIPS 1966 Fall Joint Comput. Conf.","volume":"29","author":"GENTLEMAN W. W."},{"key":"e_1_2_1_7_2","first-page":"85","article-title":"Fast Fourier transform method of computing difference equations and simulating filters","author":"HELMS H. D","year":"1967","journal-title":"IEEE Trans. A U-15"},{"key":"e_1_2_1_8_2","first-page":"58","article-title":"On errors introduced by combined sampling and quantization","author":"KATZENELSON J","year":"1962","journal-title":"IRE Trans. AC-7"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","first-page":"1735","DOI":"10.1109\/PROC.1969.7388","article-title":"Error analysis of digital filters realized with floating-point arithmetic","volume":"57","author":"LI","year":"1969","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"1739","DOI":"10.1364\/AO.6.001739","article-title":"Binary Fraunhofer holograms generated by computer","volume":"6","author":"LOHMANN A. W.","year":"1967","journal-title":"Appl. Optics"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1109\/TAC.1963.1105533","article-title":"On errors introduced by combined sampling and quantization, Vol. AC-7","author":"WATTS D. J.","year":"1963","journal-title":"IEEE Trans. AC-8"},{"key":"e_1_2_1_12_2","first-page":"209","article-title":"Roundoff noise in floating point fast Fourier transform computation","author":"WEINSTEIN C.J","year":"1969","journal-title":"IEEE Trans. A U-17"},{"key":"e_1_2_1_13_2","first-page":"6","article-title":"A comparison of rounding noise in floating point and fixed point digital filter realization","volume":"57","author":"WEINSTEIS C.","year":"1969","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_14_2","first-page":"151","article-title":"A fixed-point fast Fourier transform error analysis","author":"WELCH P.D","year":"1969","journal-title":"IEEE Trans. AU-17"},{"key":"e_1_2_1_15_2","unstructured":"WILKINSON J. H. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs N. J. 1963. WILKINSON J. H. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs N. J. 1963."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321607.321613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T19:29:37Z","timestamp":1614713377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321607.321613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1970,10]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1970,10]]}},"alternative-id":["10.1145\/321607.321613"],"URL":"http:\/\/dx.doi.org\/10.1145\/321607.321613","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1970,10]]}}}