Use of minimum-adder multiplier blocks in FIR digital filters

The computational complexity of VLSI digital filters using fixed point binary multiplier coefficients is normally dominated by the number of adders used in the implementation of the multipliers. It has been shown that using multiplier blocks to exploit redundancy across the coefficients results in significant reductions in complexity over methods using canonic signed-digit (CSD) representation, which in turn are less complex than standard binary representation. Three new algorithms for the design of multiplier blocks are described: an efficient modification to an existing algorithm, a new algorithm giving better results, and a hybrid of these two which trades off performance against computation time. Significant savings in filter implementation cost over existing techniques result in all three cases. For a given wordlength, it was found that a threshold set size exists above which the multiplier block is extremely likely to be optimal. In this region, design computation time is substantially reduced