Fixed-point error bound for convolution by polynomial transforms, with application to FIR filtering

Polynomial transforms do not require multiplication for their computation, and are found to be efficient in computing one dimensional convolutions. They significantly save the number of arithmetic operations as compared to the FFT technique. However, for a fair comparison, it is necessary to take into account the round off and scaling errors that are introduced while performing convolution using these transforms. In this paper a fixed-point error bound will be derived for one dimensional convolution, with application to FIR filtering. The number of datapoints is assumed to be a power of two and a radix-2 structure is used for computing the polynomial transform. Comparisons of the error performance will be made with the corresponding radix-2 FFT technique.