Optimizing imprecise fixed-point arithmetic circuits specified by Taylor Series through arithmetic transform

ABSTRACT

We consider synthesis of arithmetic DSP circuits with finite precision fixed-point operations. The aim is to choose the lowest cost implementation that matches a real-valued specification within the allowed imprecision. Starting from Taylor Series or real-valued polynomials, we demonstrate first a method to obtain satisfying implementations that uses intermediate Arithmetic Transform polynomials as an analytical apparatus suitable to precision analysis for both the quantization (bit-width) and approximation sources of imprecision. We then derive the precision optimization algorithm that explores multiple precision parameters in a branch-and-bound search.

REFERENCES

• 1: Altaf Abdul Gaffar , Oskar Mencer , Wayne Luk , Peter Y. K. Cheung, Unifying Bit-Width Optimisation for Fixed-Point and Floating-Point Designs, Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.79-88, April 20-23, 2004
• 2: S. Kim and W. Sung, "Fixed-point error analysis and word length optimization of 8 x 8 IDCT," IEEE Trans. Circuits Syst. Video Tech., Vol. 8, No. 8, Dec. 1998, pp. 935--940.
• 3: K. Kum and W. Sung, "Combined word-length optimization and highlevel synthesis of digital signal processing systems," IEEE Trans. CAD Vol. 20, No. 8, Aug. 2001, pp. 921--930.
• 4: Changchun Shi , Robert W. Brodersen, Automated fixed-point data-type optimization tool for signal processing and communication systems, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996700]
• 5: 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]
• 6: Authors, "Paper Title Withheld for blind review", Published in Journal of (name of publication withheld for blind review).
• 7: A. Nayak , M. Haldar , A. Choudhary , P. Banerjee, Precision and error analysis of MATLAB applications during automated hardware synthesis for FPGAs, Proceedings of the conference on Design, automation and test in Europe, p.722-728, March 2001, Munich, Germany
• 8: G. Constantinides, P. Cheung, and W. Luk, "Wordlength optimization for linear digital signal processing," IEEE Trans. on CAD vol. 22, no. 10, pp. 1432--1442, Oct. 2003.
• 9: D.-U. Lee, A. Gaffar, R. C. C. Cheung, O. Mencer, W. Luk, and G. Constantinides, "Accuracy-Guaranteed Bit-Width Optimization", IEEE Trans. CAD, Vol. 25, No. 10, Oct. 2006, pp. 1990--2000.
• 10: James Smith , Giovanni De Micheli, Polynomial circuit models for component matching in high-level synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.783-800, 12/1/2001 [doi>10.1109/92.974892]
• 11: Pang, Yu; Radecka, Katarzyna; Zilic, Zeljko; "Arithmetic Transforms of Imprecise Datapaths by Taylor Series Conversion", Electronics, Circuits and Systems, 2006. ICECS '06. 13th IEEE International Conference on 10--13 Dec. 2006 Page(s):696--699
• 12: L. de Figueiredo and J. Stolfi, "Self-validated numerical methods and applications," in Brazilian Mathematics Colloquium Monograph. Rio de Janeiro, Brazil: IMPA, 1997.
• 13: Accuracy Sensitive Word--Length Selection for Algorithm Optimization, Proceedings of the International Conference on Computer Design, p.54, October 05-05, 1998
• 14: 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]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
DSP circuit synthesis, Taylor Series, error analysis, optimization