Subexpression sharing in filters using canonic signed digit multipliers
- 1 October 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing
- Vol. 43 (10) , 677-688
- https://doi.org/10.1109/82.539000
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- A silicon compiler for high-speed CMOS multirate FIR digital filtersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Efficient substitution of multiple constant multiplications by shifts and additions using iterative pairwise matchingPublished by Association for Computing Machinery (ACM) ,1994
- Optimizing pipelined networks of associative and commutative operatorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- Critical path minimization using retiming and algebraic speed-upPublished by Association for Computing Machinery (ACM) ,1993
- A compound primitive operator approach to the realisation of video sub-band filter banksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- FIRGEN: a computer-aided design system for high performance FIR filter integrated circuitsIEEE Transactions on Signal Processing, 1991
- Fast prototyping of datapath-intensive architecturesIEEE Design & Test of Computers, 1991
- Primitive operator digital filtersIEE Proceedings G Circuits, Devices and Systems, 1991
- Optimization of canonic signed digit multipliers for filter designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Behavioral to structural translation in a bit-serial silicon compilerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988