Effects of finite register length in digital filtering and the fast Fourier transform
- 1 January 1972
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 60 (8), 957-976
- https://doi.org/10.1109/proc.1972.8820
Abstract
When digital signal processing operations are implemented on a computer or with special-purpose hardware, errors and constraints due to finite word length are unavoidable. The main categories of finite register length effects are errors due to A/D conversion, errors due to roundoffs in the arithmetic, constraints on signal levels imposed by the need to prevent overflow, and quantization of system coefficients. The effects of finite register length on implementations of linear recursive difference equation digital filters, and the fast Fourier transform (FFT), are discussed in some detail. For these algorithms, the differing quantization effects of fixed point, floating point, and block floating point arithmetic are examined and compared. The paper is intended primarily as a tutorial review of a subject which has received considerable attention over the past few years. The groundwork is set through a discussion of the relationship between the binary representation of numbers and truncation or rounding, and a formulation of a statistical model for arithmetic roundoff. The analyses presented here are intended to illustrate techniques of working with particular models. Results of previous work are discussed and summarized when appropriate. Some examples are presented to indicate how the results developed for simple digital filters and the FFT can be applied to the analysis of more complicated systems which use these algorithms as building blocks.Keywords
This publication has 44 references indexed in Scilit:
- Instability thresholds in digital filters due to coefficient roundingIEEE Transactions on Audio and Electroacoustics, 1970
- Accumulation of Round-Off Error in Fast Fourier TransformsJournal of the ACM, 1970
- Roundoff noise in floating point fast Fourier transform computationIEEE Transactions on Audio and Electroacoustics, 1969
- A bound on the output of a circular convolution with application to digital filteringIEEE Transactions on Audio and Electroacoustics, 1969
- A holding technique to reduce number of bits in digital transfer functionsIEEE Transactions on Audio and Electroacoustics, 1968
- The analysis of round-off and truncation errors in a hybrid control systemIEEE Transactions on Automatic Control, 1967
- On errors introduced by combined sampling and quantizationIRE Transactions on Automatic Control, 1962
- The Influence of Coefficients on the Zeros of PolynomialsJournal of the London Mathematical Society, 1961
- The Effect of Parameters on the Roots of an Equation SystemThe Computer Journal, 1961
- Error analysis of floating-point computationNumerische Mathematik, 1960