Multiplierless synthesis of multiple constant multiplications using common subexpression sharing with genetic algorithm

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 relationship and propose an improvement search space for optimization that combines 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.