TY - GEN
T1 - Area optimization algorithms in high-speed digital FIR filter synthesis
AU - Aksoy, Levent
AU - Gunes, Ece Olcay
PY - 2008
Y1 - 2008
N2 - In the last decade, efficient algorithms have been proposed for the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., the multiple constant multiplications (MCM) problem. However, in these algorithms, an addition/subtraction operation is assumed to be a two-input operation that is generally implemented with ripple carry adders increasing the delay of the computation. On the other hand, carry-save adders (CSAs) are commonly used for high-speed implementation of multi-operand additions. The previously proposed algorithms designed for the optimization of the number of CSA blocks obtain good results, but they have been heuristics and cannot guarantee the minimum solution. In this work, we introduce an exact common subexpression elimination (CSE) algorithm that finds the minimum number of CSA blocks in the implementation of MCM. Furthermore, we present an approximate algorithm based on the exact CSE algorithm that can also handle general number representation of constants. It is shown by the experimental results that the algorithms introduced in this paper obtain competitive and better results than the previously proposed heuristics.
AB - In the last decade, efficient algorithms have been proposed for the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., the multiple constant multiplications (MCM) problem. However, in these algorithms, an addition/subtraction operation is assumed to be a two-input operation that is generally implemented with ripple carry adders increasing the delay of the computation. On the other hand, carry-save adders (CSAs) are commonly used for high-speed implementation of multi-operand additions. The previously proposed algorithms designed for the optimization of the number of CSA blocks obtain good results, but they have been heuristics and cannot guarantee the minimum solution. In this work, we introduce an exact common subexpression elimination (CSE) algorithm that finds the minimum number of CSA blocks in the implementation of MCM. Furthermore, we present an approximate algorithm based on the exact CSE algorithm that can also handle general number representation of constants. It is shown by the experimental results that the algorithms introduced in this paper obtain competitive and better results than the previously proposed heuristics.
KW - Area optimization
KW - Carry-save adders
KW - High-speed filter design
KW - Multiple constant multiplications
KW - Subexpression sharing
UR - http://www.scopus.com/inward/record.url?scp=59249083639&partnerID=8YFLogxK
U2 - 10.1145/1404371.1404396
DO - 10.1145/1404371.1404396
M3 - Conference contribution
AN - SCOPUS:59249083639
SN - 9781605582313
T3 - Proceedings - SBCCI 2008: 21st Symposium on Integrated Circuits and Systems Design
SP - 64
EP - 69
BT - Proceedings - SBCCI 2008
T2 - 21st Symposium on Integrated Circuits and Systems Design, SBCCI 2008
Y2 - 1 September 2008 through 4 September 2008
ER -