Synthesis of saturation arithmetic architectures

ABSTRACT

This paper describes a synthesis technique for automating the design of linear Digital Signal Processing (DSP) systems such as digital filters. The proposed methodology makes optimized use of saturation arithmetic to produce a small design implemented directly in hardware. An analytical technique is proposed to estimate the saturation error resulting from a particular implementation, and an optimization procedure is introduced to aim for the smallest implementation satisfying user-specified bounds on saturation and roundoff error. Results are presented illustrating significant speedup and area reduction compared with standard DSP design techniques: up to 22% improvement in area and 28% improvement in speed have been obtained on Field Programmable Gate Array (FPGA) implementations.

REFERENCES

• 1: Altera Corporation. 1998. Altera Databook. San Jose: Altera Corporation.
• 2: Benedetti, A. and Perona, P. 2000. Bit-width optimization for configurable DSPs by multi-interval analysis. In Proceedings of the 34th Asilomar Conference on Signals, Systems and Computers.
• 3: Chung, K.-L. 1974. A Course in Probability Theory. Academic Press, New York.
• 4: R. Cmar , L. Rijnders , P. Schaumont , S. Vernalde , I. Bolsens, A methodology and design environment for DSP ASIC fixed point refinement, Proceedings of the conference on Design, automation and test in Europe, p.56-es, January 1999, Munich, Germany [doi>10.1145/307418.307503]
• 5: Constantinides, G. A. 2001. High Level Synthesis and Word Length Optimization of Digital Signal Processing Systems. Ph.D. thesis, University of London.
• 6: George A. Constantinides, Perturbation Analysis for Word-length Optimization, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.81, April 09-11, 2003
• 7: George A. Constantinides , Peter Y. K. Cheung , Wayne Luk, The Multiple Wordlength Paradigm, Proceedings of the the 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.51-60, April 29-May 02, 2001 [doi>10.1109/FCCM.2001.46]
• 8: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 9: Milos Ercegovac , Darko Kirovski , Miodrag Potkonjak, Low-power behavioral synthesis optimization using multiple precision arithmetic, Proceedings of the 36th ACM/IEEE conference on Design automation, p.568-573, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310000]
• 10: FREETEL. 1993. Esprit project 6166: FREETEL database.
• 11: Johnson, K. K. and Sandberg, I. W. 1995. A separation theorem for finite precision digital filters. IEEE Trans. Circuits and Syst. I 42, 9 (September), 541--545.
• 12: Kim, S., Kum, K., and Sung, W. 1998. Fixed-point optimization utility for C and C++ based digital signal processing programs. IEEE Trans. Circuits Syst. II 45, 11 (November), 1455--1464.
• 13: Kum, K.-I. and Sung, W. 2001. Combined word-length optimization and high-level synthesis of digital signal processing systems. IEEE Trans. Comput. Aided Design 20, 8 (August), 921--930.
• 14: M. P. Leong , M. Y. Yeung , C. K. Yeung , C. W. Fu , P. A. Heng , P. H. W. Leong, Automatic Floating to Fixed Point Translation and its Application to Post-Rendering 3D Warping, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.240, April 21-23, 1999
• 15: Liu, B. 1971. Effect of finite word length on the accuracy of digital filters---a review. IEEE Trans. Circuit Theory CT-18, 6, 670--677.
• 16: Sanjit K. Mitra, Digital Signal Processing: A Computer Based Approach, McGraw-Hill, Inc., New York, NY, 1997
• 17: Oppenheim, A. V. and Weinstein, C. J. 1972. Effects of finite register length in digital filtering and the fast fourier transform. IEEE Proceedings 60, 8, 957--976.
• 18: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 19: Markus Willems , Volker Bürsgens , Holger Keding , Thorsten Grötker , Heinrich Meyr, System level fixed-point design based on an interpolative approach, Proceedings of the 34th annual conference on Design automation, p.293-298, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266105]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

General Terms:
Algorithms, Design, Performance

Keywords:
Signal processing, saturation arithmetic, synthesis