Global optimization of common subexpressions for multiplierless synthesis of multiple constant multiplications

Abstract

In the context of multiple constant multiplication (MCM) design, we propose a novel common 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 examples we demonstrate, the proposed solution space further reduces the number of adders/subtractors in the MCM synthesis.