A Difference Based Adder Graph Heuristic for Multiple Constant Multiplication Problems

Abstract

Multiple constant multiplication (MCM), i.e., realizing a number of constant multiplications using a minimum number of adders and subtracters, has been an active research area for the last decade. An adder graph type algorithm for solving the MCM problem is introduced with a novel heuristic inspired by difference methods. It is shown that the results is as good or better as previous state of the art under most conditions. Furthermore, the proposed algorithm does not rely on look-up tables.