skip to main content
10.1145/1120725.1120953acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

Reducing hardware complexity of linear DSP systems by iteratively eliminating two-term common subexpressions

Published: 18 January 2005 Publication History

Abstract

This paper presents a novel technique to reduce the number of operations in Multiplierless implementations of linear DSP transforms, by iteratively eliminating two-term common subexpressions. Our method uses a polynomial transformation of linear systems that enables us to eliminate common subexpressions consisting of multiple variables. Our algorithm is fast and produces the least number of additions/subtractions compared to all known techniques. The synthesized examples show significant reductions in the area and power consumption.

References

[1]
M. Puschel, B. Singer, J. Xiong, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, and R. W. Johnson, "SPIRAL: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms," Journal of High Performance Computing and Applications, 2004.
[2]
H. De Man, J. Rabaey, J. Vanhoof, G. Goossens, P. Six, and L. Claesen, "CATHEDRAL-II-a computer-aided synthesis system for digital signal processing VLSI systems," Computer-Aided Engineering Journal, vol. 5, pp. 55--66, 1988.
[3]
M. Potkonjak, M. B. Srivastava, and A. P. Chandrakasan, "Multiple Constant Multiplications: Efficient and Versatile Framework and Algorithms for Exploring Common Subexpression Elimination," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1996.
[4]
H. T. Nguyen and A. Chattejee, "Number-splitting with shift-and-add decomposition for power and hardware optimization in linear DSP synthesis," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 8, pp. 419--424, 2000.
[5]
R. Pasko, P. Schaumont, V. Derudder, V. Vernalde, and D. Durackova, "A new algorithm for elimination of common subexpressions," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1999.
[6]
H. Safiri, M. Ahmadi, G. A. Jullien, and W. C. Miller, "A New Algorithm for the Elimination of Common Subexpressions in Hardware Implementation of Digital Filters by Using Genetic Programming," Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), Boston, MA, 2000.
[7]
M. Mehendale, S. D. Sherlekar, and G. Venkatesh, "Synthesis of multiplier-less FIR filters with minimum number of additions," Proceedings of the ICCAD, 1995.
[8]
I.-C. Park and H.-J. Kang, "Digital filter synthesis based on an algorithm to generate all minimal signed digit representations," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 21, pp. 1525--1529, 2002.
[9]
A. Hosangadi, F. Fallah, and R. Kastner, "Common Subexpression Elimination Involving Multiple Variables for Linear DSP Synthesis," Proceedings of the IEEE International Conference on Application-Specific Architectures and Processors (to appear), Galveston, TX, 2004.
[10]
T. Wiegand, G. J. Sullivan, G. Bjntegaard, and A. Luthra, "Overview of the H.264/AVC video coding standard," Circuits and Systems for Video Technology, IEEE Transactions on, vol. 13, pp. 560--576, 2003.
[11]
H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, "Low-complexity transform and quantization in H.264/AVC," Circuits and Systems for Video Technology, IEEE Transactions on, vol. 13, pp. 598--603, 2003.
[12]
K. Hwang, Computer Arithmetic: Principle, Architecture and Design: Wiley, 1979.
[13]
J. Rajski and J. Vasudevamurthy, "The testability-preserving concurrent decomposition and factorization of Boolean expressions," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 11, pp. 778--793, 1992.
[14]
J. Vasudevamurthy and J. Rajski, "A method for concurrent decomposition and factorization of Boolean expressions," Proceedings of the Computer-Aided Design, 1990. ICCAD-90. Digest of Technical Papers., 1990 IEEE International Conference on, 1990.

Cited By

View all
  • (2024)Multiplierless Design of High-Speed Very Large Constant Multiplications2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC58780.2024.10473954(957-962)Online publication date: 22-Jan-2024
  • (2022)Multiplierless Design of Very Large Constant Multiplications in CryptographyIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2022.319166269:11(4503-4507)Online publication date: Nov-2022
  • (2014)A Tutorial on Multiplierless Design of FIR FiltersCircuits, Systems, and Signal Processing10.1007/s00034-013-9727-833:6(1689-1719)Online publication date: 1-Jun-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
January 2005
1495 pages
ISBN:0780387376
DOI:10.1145/1120725
  • General Chair:
  • Ting-Ao Tang
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 January 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

ASPDAC05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Multiplierless Design of High-Speed Very Large Constant Multiplications2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC58780.2024.10473954(957-962)Online publication date: 22-Jan-2024
  • (2022)Multiplierless Design of Very Large Constant Multiplications in CryptographyIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2022.319166269:11(4503-4507)Online publication date: Nov-2022
  • (2014)A Tutorial on Multiplierless Design of FIR FiltersCircuits, Systems, and Signal Processing10.1007/s00034-013-9727-833:6(1689-1719)Online publication date: 1-Jun-2014
  • (2012)Optimization Algorithms for the Multiplierless Realization of Linear TransformsACM Transactions on Design Automation of Electronic Systems10.1145/2071356.207135917:1(1-27)Online publication date: 1-Jan-2012
  • (2012)Multiplierless Design of Linear DSP TransformsVLSI-SoC: Advanced Research for Systems on Chip10.1007/978-3-642-32770-4_5(73-93)Online publication date: 2012
  • (2010)Layout aware optimization of high speed fixed coefficient FIR filters for FPGAsInternational Journal of Reconfigurable Computing10.1155/2010/6976252010(1-17)Online publication date: 1-Jan-2010
  • (2009)FIR filter design methodology for hardware optimized implementationIEEE Transactions on Consumer Electronics10.1109/TCE.2009.527804155:3(1669-1673)Online publication date: 1-Aug-2009
  • (2006)Optimizing high speed arithmetic circuits using three-term extractionProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131838(1294-1299)Online publication date: 6-Mar-2006
  • (2006)ASSUMEs: Heuristic Algorithms for Optimization of Area and Delay in Digital Filter Synthesis2006 13th IEEE International Conference on Electronics, Circuits and Systems10.1109/ICECS.2006.379897(748-751)Online publication date: Dec-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media