Global Optimization of Common Subexpressions for Multiplierless Synthesis of Multiple Constant Multiplications

Abstract — In the context of multiple constant mul-tiplication (MCM) design, we propose a novel com-mon subexpression elimination (CSE) algorithm that models the optimal synthesis of coefficients into a 0-1 mixed-integer linear programming (MILP) problem. A time delay constraint is included for synthesis. We also propose coefficient decompositions that combine all minimal signed digit (MSD) representations and the shifted sum (difference) of coefficients. In the ex-amples we demonstrate, the proposed solution space further reduces the number of adders/subtractors in the MCM synthesis. I