Custom-optimized multiplierless implementations of DSP algorithms

Linear DSP kernels such as transforms and filters are com-prised exclusively of additions and multiplications by con-stants. These multiplications may be realized as networks of additions and wired shifts in hardware. The cost of such a “multiplierless ” implementation is determined by the num-ber of additions, which in turn depends on the value and precision of these constants. For a given transform or filter, the set of constants and their required precision is affected by algorithmic and implementation choices and hence pro-vides a degree of freedom for optimization. In this paper we present an automated method to generate, for a given linear transform, a minimum addition multiplierless implementa-tion that satisfies a given quality constraint. The method combines automatic algorithm selection to improve numer-ical robustness and automatic search methods to minimize constant precisions in a chosen algorithm. We present ex-periments that show the trade-offs between cost and qual-ity, including custom optimizations of the transforms used in JPEG image and MP3 audio decoders