A simple fixed-point error bound for the fast Fourier transform

Error bounds for the computation of the fast Fourier transform in fixed-point arithmetic are derived for any arithmetic number base and for any prime factorization of the data array length. The intended application is for signal processing with minicomputers. Errors arising from inaccurate sine coefficients and from limited arithmetic precision are considered. The arithmetic error depends essentially on shifts of the data array that may be required to avoid overflow of the computer word. Our closest bound requires knowledge of where shifts occur and is best computed in parallel with the Fourier transform. For the case that such program modification is not feasible, we derive an error bound for a posteriori calculation and an a priori error estimate. Our bounds are for the maximum error because little is gained at the expense of considerably greater complexity for probabilistic error bounds.