J. O. Coleman

Cascaded Coefficient Number Systems Lead to FIR Filters of Striking Computational Efficiency
J. O. Coleman
Multiplierless FIR filters (or other fixed linear combiners) are built as add/subtract networks operating on bit-shifted input data. Classically, the computational structure required is determined by simply expressing the coefficients in canonical-signed-digit (CSD) form. In this paper, expressing coefficients in a higher-radix number system instead results in a computational structure for a partial solution, one that reduces a large linear-combination problem to a smaller one. A well-chosen sequence of such number systems then leads to a cascade of these problem-reducing networks that together solve the original problem with remarkable overall computational efficiency, especially for larger filters. An example FIR filter with a real chirp impulse response 3000 samples in length (a matched filter for a pulse-compression radar) was easily realized with -95 dB rms approximation error using less than two add or subtract operations per coefficient. This is a reduction of approximately 60% relative to the usual CSD method.
PDF (97K),
Accepted for presentation to the The 2001 Int'l IEEE Conf. on Electronics, Circuits, and Systems (ICECS '01), Malta, September 2001.
May 2001.