IEEE Transactions on Circuits and Systems II Analog and Digital Signal Processing · 1996 · 590 citations · 15 references
Natural SciencesComputer EngineeringComputer ScienceNumber TheoryOptimizationTheory Of ComputationArithmetic FunctionsDigital Signal ProcessingCommon Subexpression EliminationMultiplier DesignMultipliers
Constant multiplication is typically implemented with shift‑and‑add operations, and using Canonical Signed Digit (CSD) representation minimizes the number of additions; in operator networks such as FIR filters, sharing common subexpressions can reduce the total operator count by up to 50%. This paper investigates how optimizing CSD multiplier design by sharing subexpressions can lower addition counts. The study explores optimization techniques for CSD multipliers, focusing on subexpression sharing within networks of operators. Mathematical analysis shows that sharing the two most common subexpressions can yield a 33 % reduction in the number of additions.
A common way of implementing constant multiplication is by a series of shift and add operations. As is well known, if the multiplier is represented in Canonical Signed Digit (CSD) form, then the number of additions (or subtractions) used will be a minimum. This paper examines methods for optimizing the design of CSD multipliers, and in particular the gains that can be made by sharing subexpressions. In the case where several multipliers are present in a network of operators, for instance in an FIR filter, the savings achieved by identifying common subexpressions can be as much as 50% of the total number of operators. The asymptotic frequency of the most common subexpression is analyzed mathematically, and it is shown that sharing the two most common subexpressions can be expected to lead to a 33% saving of the number of additions.
15
R. Yarlagadda · IEEE Transactions on Acoustics Speech and Signal Processing · 1976 · 1.7K citations
Fast prototyping of datapath-intensive architectures
Jan M. Rabaey, Chi-min Chu, Phu Hoang et al. · IEEE Design & Test of Computers · 1991 · 305 citations