I. Background and Motivation
MANY applications in digital signal processing and control, such as linear-time-invariant filters/controllers, involve the computation of a large number of multiplications of one variable by a set of constants. To be efficiently handled, the implementation must be multiplierless, i.e., using exclusively additions, subtractions, and left shifts. This problem is called single/multiple constant multiplication (SCM/MCM). Its computational complexity still seems to be unknown. However, because the solution space to explore is so huge, one has to use heuristics. Due to the importance of this issue, a large number of heuristics have been proposed. They are classified in the following four categories.
Digit-recoding algorithms, such as the canonical signed digit (CSD) representation [1], Booth recoding [2], and Dimitrov's double-base number system (DBNS) recoding [3].
Common subexpression elimination (CSE) using pattern matching performed after an initial digit recoding. Typical examples are the works of Hartley [4], Lefèvre [5], and Boullis [6].
Directed acyclic graph (DAG)-based algorithms. This category includes the work of Bernstein [7], MAG [8], [9], and Hcub [10].
Mixed algorithms combining CSE and a DAG, such as the recent optimal algorithm BIGE [11].