A new algorithm for elimination of common subexpressions

The problem of an efficient hardware implementation of multiplications with one or more constants is encountered in many different digital signal-proc essing areas, such as image processing or digital filter optimization. In a more general form, this is a problem of common subexpression elimination, and as such it also occurs in compiler optimization and many high-level syn thesis tasks. An efficient solution of this problem can yield significant i mprovements in important design parameters like implementation area or powe r consumption. In this paper, a new solution of the multiple constant multi plication problem based on the common subexpression elimination technique i s presented. The performance of our method is demonstrated primarily on a f inite-duration impulse response filter design. The idea is to implement a s et of constant multiplications as a set of add-shift operations and to opti mize these with respect to the common subexpressions afterwards. We show th at the number of add/subtract operations can be reduced significantly this way. The applicability of the presented algorithm to the different high-lev el synthesis tasks is also indicated. Benchmarks demonstrating the algorith m's efficiency are included as well.