A HIERARCHICAL-CLUSTERING METHOD FOR THE MULTIPLE CONSTANT MULTIPLICATION PROBLEM

In this paper, we propose an efficient solution for the Multiple Const ant Multiplication (MCM) problem. The method uses hierarchical cluster ing to exploit common subexpressions among constants and reduces the n umber of shifts, additions, and subtractions. The algorithm defines ap propriate weights, which indicate operation priority, and selects comm on subexpressions, resulting in a minimum number of local operations. It can also be extended to various high-level synthesis tasks such as arbitrary linear transforms. Experimental results for several error-co rrecting codes, digital filters and Discrete Cosine Transforms (DCTs) have shown the effectiveness of our method.