Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We propose a new algorithm that maximizes he sharing of partial terms in Multiple Cons an Multiplication (MCM) operations under a general number representation for the coefficients. MCM operations are required by many algorithms in digital signal processing and have been the subject of extensive research. By making no assumptions as to the number representation, the algorithm described in his paper is able to perform a better search for the optimal sharing of partial terms than previous methods based on MSD or CSD representations. We have applied our algorithm for the hardware minimization of FIR filers.The results show that we can ob ain solutions that require between 20% to 50% less hardware when compared agains he solutions using he MSD representation.

REFERENCES

• 1: Huy T. Nguyen , Abhijit Chatterjee, Number-splitting with shift-and-add decomposition for power and hardware optimization in linear DSP synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.4, p.419-424, Aug. 2000 [doi>10.1109/92.863621]
• 2: E. da Costa, P. Flores, and J. Monteiro. Maximal Sharing of Partial Terms in MCM under Minimal Signed Digit Representation.In European Conference on Circuits Theory and Design pages 468--473, 2005.
• 3: Mahesh Mehendale , S. D. Sherlekar , G. Venkatesh, Techniques for low power realization for FIR filters, Proceedings of the 1995 Asia and South Pacific Design Automation Conference, p.72-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224952]
• 4: H. Samueli. An Improved Search Algorithm for he Design of Multiplierless FIR Filters with Power-of-Two Coefficients. In IEEE Transactions on Circuits and Systems pages 1044--1047, 1989.
• 5: A. Nannarelli, M. Re, and G. Cardarilli. Tradeoffs be ween residue number system and raditional FIR Filters. In IEEE International Symposium on Circuits and Systems May 2001.
• 6: Miodrag Potkonjak , Mani B. Srivastava , Anantha Chandrakasan, Efficient substitution of multiple constant multiplications by shifts and additions using iterative pairwise matching, Proceedings of the 31st annual Design Automation Conference, p.189-194, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196343]
• 7: R. Hartley. Subexpression sharing in filters using canonic signed digit multipliers. IEEE Transactions on Circuits and Systems II.43 (10): 677--688, 1996.
• 8: R. Pasko, P. Schaumon , V. Derudder, S. Vernalde, and D. Durackova. A New Algorithm for Elimination of Common Subexpressions. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.18: 58--68, January 1999.
• 9: A. Dempster and M. Macleod. Use of Minimum-Adder Multiplier Blocks in FIR Digital Filters. IEEE Trans. on CAS-II 42 (9): 596--577, September 1995.
• 10: In-Cheol Park , Hyeong-Ju Kang, Digital filter synthesis based on minimal signed digit representation, Proceedings of the 38th annual Design Automation Conference, p.468-473, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378564]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.2 Performance Analysis and Design Aids**

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

General Terms:
Algorithms, Design, Performance

Keywords:
common subexpression elimination (CSE), digital filter design, minimal signed digit (MSD), multiple constant multiplication (MCM)