Subexpression sharing in filters using canonic signed digit multipliers
Author:
- 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
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 15 references indexed in Scilit:
- Efficient substitution of multiple constant multiplications by shifts and additions using iterative pairwise matching1994
- 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-up1993
- An architectural transformation program for optimization of digital systems by multi-level decomposition1993
- A compound primitive operator approach to the realisation of video sub-band filter banks1993
- 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 design1991
- Behavioral to structural translation in a bit-serial silicon compilerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988