A common subexpression sharing approach for multiplierless synthesis of multiple constant multiplications

Abstract

In the context of multiple constant multiplications (MCM) design, we propose a novel common-subexpression-elimination (CSE) algorithm that models synthesis of coefficients into an estimated cost function. Although the proposed algorithm generally does not guarantee an optimum solution, it is capable of finding the minimum/minima of the function in practically sized problems. In our design examples that have known optimal solutions, syntheses of coefficients using the proposed method match the optimal results in a defined search space. We also discover the relationhsip and propose an improvement search space for optimization that combine all minimal-signed-digit (MSD) representations as well as the shifted sum (difference) of coefficients to explore the hidden relationship. In some cases, the proposed feasible solution space further reduces the number of adders/subtractors in the synthesis of MCM from all MSD representations.