An alternative carry-save arithmetic for new generation field programmable gate arrays

In this work, a double carry-save addition operation is proposed, which is efficiently synthesized for 6-input LUT-based field programmable gate arrays (FPGAs). The proposed arithmetic operation is based on redundant number representation and provides carry propagation-free addition. Using the proposed arithmetic operation, a compact and fast multiply and accumulate unit is designed. To our knowledge, the proposed design provides the fastest multiply-add operation for 6-input LUT-based FPGA systems. A finite impulse response filter implementation is given to show the performance of the proposed structure. The proposed implementation provides a dramatic performance increase, which is at least 2 times faster than conventional binary multiply-add implementations.

PDF

___

[1] Xilinx Inc. Xilinx Virtex-5 Family Overview. San Jose, CA, USA: Xilinx, 2009.
[2] Altera Corporation. Altera Stratix II Device Handbook. San Jose, CA, USA: Altera Corporation, 2009.
[3] Parhami B. Generalized signed-digit number systems: a unifying framework for redundant number representations. IEEE T Comput 1990; 39: 8998.
[4] Ercegovac M, Lang T. Digital Arithmetic. San Francisco, CA, USA: Morgan Kauffman, 2004.
[5] Phatak DS, Goff T, Koren I. Constant-time addition and simultaneous format conversion based on redundant binary representations. IEEE T Comput 2001; 50: 12671278.
[6] Noll TG. Carry-save architectures for high-speed digital signal processing. J VLSI Signal Proc 1991; 3: 121140.
[7] Altera Corporation. Advanced Synthesis Cookbook: A Design Guide for Stratix II, Stratix III, and Stratix IV Devices. San Jose, CA, USA: Altera Corporation, 2009.
[8] Samueli H. An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients. IEEE T Circuits Syst 1989; 39: 16551668.
[9] Yurdakul, A, D¨undar G. Fast and efficient algorithm for the multiplierless realisation of linear DSP transforms. IEE PCirc Dev Syst 2008; 149: 205211.
[10] Aktan M, Yurdakul, A, D¨undar G. An algorithm for the design of low-power hardware efficient FIR filters. IEEE T Circuits Syst 2008; 55: 15361545.
[11] Hartley R. Subexpression sharing in filters using canonic signed digit multipliers. IEEE Trans CircuitsII 1996; 43: 677688.
[12] Parhi K. VLSI Digital Signal Processing Systems: Design and Implementation. 1st ed. New York, NY, USA: Wiley, 1999.
[13] Ortiz M, Quiles F, Hormigo J, Jaime FJ, Villalba J, Zapata EL. Efficient implementations of carry-save adders in FPGAs. In: IEEE International Conference on Application-Specific Systems, Architectures and Processors; 79 July 2009; Boston, MA, USA. New York, NY, USA: IEEE. pp. 207210.
[14] Kamp W, BainbridgeSmith A. Multiply accumulate unit optimised for fast dot-product evaluation. In: ICFPT 2007 International Conference on Field-Programmable Technology; 1214 December 2007; Kitakyushu, Japan. New York, NY, USA: IEEE. pp. 349352.
[15] Parandeh-Afshar H, Brisk HP, Ienne P. Improving synthesis of compressor trees on FPGAs via integer linear programming. In: DATE 2008 Design, Automation, and Test in Europe Conference; 1014 March 2008; Munich,Germany. New York, NY, USA: IEEE. pp. 12561261.
[16] Kamp W, Bainbridge-Smith A, Hayes M. Efficient implementation of fast redundant number adders for long wordlengths in FPGAs. In: FPT 2009 International Conference on Field-Programmable Technology; 911 December 2009; Sydney, Australia. New York, NY, USA: IEEE. pp. 239246.
[17] Cardarilli GC, Pontarelli S, Re M, Salsano A. On the use of signed digit arithmetic for the new 6-inputs LUT based FPGAs. In: IEEE International Conference on Electronics, Circuits, and Systems; 31 August3 September 2008; St Julians, Malta. New York, NY, USA: IEEE. pp. 602605.
[18] Koren I. Computer Arithmetic Algorithms. Natick, MA, USA: AK Peters, 2002.
[19] Parhami, B. Computer Arithmetic: Algorithms and Hardware Designs. 2nd ed. Oxford, UK: Oxford University Press, 2008.
[20] Gonz´alez AF, Mazumder P. Redundant arithmetic, algorithms and implementations. Integration 2000; 30: 1353.
[21] Mitra S. Digital Signal Processing: a Computer-Based Approach. 2nd ed. New York, NY, USA: McGraw-Hill, 2001.
[22] Weste N, Harris D. CMOS VLSI Design: A Circuits and Systems Perspective. 4th ed. Boston, MA, USA: AddisonWesley, 2010.