Open Access

Novel Binary Signed-Digit Addition Algorithm for FPGA Implementation

Division of Mechanical Science and Technology, Faculty of Science and Technology, Gunma University, Kiryu, Gunma 376-8515, Japan

E-mail Address: ytanaka@gunma-u.ac.jp

Corresponding author.

Search for more papers by this author

Yuuki Suzuki

Graduate School of Science and Technology, Gunma University, Kiryu, Gunma 376-8515, Japan

Search for more papers by this author

, and

Shugang Wei

Division of Mechanical Science and Technology, Faculty of Science and Technology, Gunma University, Kiryu, Gunma 376-8515, Japan

E-mail Address: wei@gunma-u.ac.jp

Search for more papers by this author

https://doi.org/10.1142/S0218126620501364Cited by:4 (Source: Crossref)

Abstract

Signed-digit (SD) number representation systems have been studied for high-speed arithmetic. One important property of the SD number system is the possibility of performing addition without long carry chain. However, many numbers of logic elements are required when the number representation system and such an adder are realized on a logic circuit. In this study, we propose a new adder on the binary SD number system. The proposed adder uses more circuit area than the conventional SD adders when those adders are realized on ASIC. However, the proposed adder uses 20% less number of logic elements than the conventional SD adder when those adders are realized on a field-programmable gate array (FPGA) which is made up of 4-input 1-output LUT such as Intel Cyclone IV FPGA.

This paper was recommended by Regional Editor Piero Malcovati.

Keywords:

References

1. M. Ernst, S. Klupsch, O. Hauck and S. A. Huss , Rapid prototyping for hardware accelerated elliptic curve public-key cryptosystems, Proc. 12th Int. Workshop Rapid System Prototyping (RSP 2001) (Monterey, California, June 2001), pp. 24–29. Google Scholar
2. K. Banovic, M. A. S. Khalid and E. Abdel-Raheem , Fpga-based rapid prototyping of digital signal processing systems, in 48th Midwest Symp. Circuits and Systems, 2005 (Conviongton, Kentucky, 1 August 2005), pp. 647–650. Google Scholar
3. D. Crookes, K. Benkrid, A. Bouridane, K. Alotaibi and A. Benkrid , Design and implementation of a high level programming environment for fpga-based image processing, IEE Proc. Vision, Image Signal Process. 147 (2000) 377–384. Crossref, Web of Science, Google Scholar
4. K. Benkrid, D. Crookes, J. Smith and A. Benkrid , High level programming for fpga based image and video processing using hardware skeletons, The 9th Annual IEEE Symp. Field-Programmable Custom Computing Machines (FCCM’01) (Rohnert Park, California, March 2001), pp. 219–226. Google Scholar
5. R. Tessier and W. Burleson , Reconfigurable computing for digital signal processing: A survey, J. VLSI Signal Process. Syst. Signal, Image Video Technology 28 (2001) 7–27. Crossref, Web of Science, Google Scholar
6. A. Elhossini, S. Areibi and R. Dony , An fpga implementation of the lms adaptive filter for audio processing, 2006 IEEE Int. Conf. Reconfigurable Computing and FPGA’s (ReConFig 2006) (San Luis Potosi, September 2006), pp. 1–8. Google Scholar
7. A. Avizienis , Signed-digit numbe representations for fast parallel arithmetic, IRE Trans. Electron. Comput. EC-10 (1961) 389–400. Crossref, Google Scholar
8. B. Parhami , Carry-free addition of recoded binary signed-digit numbers, IEEE Trans. Comput. 37 (1988) 1470–1476. Crossref, Web of Science, Google Scholar
9. B. Parhami , Generalized signed-digit number systems: A unifying framework for redundant number representations, IEEE Trans. Comput. 39 (1990) 89–98. Crossref, Web of Science, Google Scholar
10. A. K. Cherri , Optical carry-free addition and borrow-free subtraction based on redundant signed-digit numbers, Proc. IEEE 1993 National Aerospace Electronics Conf. (NAECON 1993), Vol. 2 (Dayton, Ohio, May 1993), pp. 1094–1099. Google Scholar
11. J. Moskal, E. Oruklu and J. Saniie , Design and synthesis of a carry-free signed-digit decimal adder, 2007 IEEE Int. Symp. Circuits and Systems (New Orleans, Louisiana, May 2007), pp. 1089–1092. Google Scholar
12. M. Zhang, A study of residue arithmetic algorithms using redundant binary number representations, PhD thesis, Gunma University (2013). Google Scholar
13. Y. M. Seddiq and H. Altwaijry , An implementation of a 2d fir filter using the signed-digit number system, 2011 Saudi Int. Electronics, Communications and Photonics Conf. (SIECPC) (Riyad, April 2011), pp. 1–4. Google Scholar
14. S. Timarchi, P. Ghayour and A. Shahbahrami , A novel high-speed low-power binary signed-digit adder, The 16th CSI Int. Symp. Computer Architecture and Digital Systems (CADS 2012) (Shiraz, Far, May 2012), pp. 70–74. Google Scholar
15. S. Dubey, R. Rani, S. Kumari and N. Sharma , Vlsi implementation of fast addition using quaternary signed digit number system, 2013 IEEE Int. Conf. Emerging Trends in Computing, Communication and Nanotechnology (ICECCN) (Tirunelveli, March 2013), pp. 654–659. Google Scholar
16. A. N. Bankar and S. Hajare , Design of arithmetic circuit using quaternary signed digit number system, 2014 Int. Conf. Communication and Signal Processing (Melmaruvathur, India, April 2014), pp. 793–797. Google Scholar
17. R. Kaur and T. Singh , Design of 32-point mixed radix fft processor using csd multiplier, 2016 Fourth Int. Conf. Parallel, Distributed and Grid Computing (PDGC) (Waknaghat, India, Dec 2016), pp. 538–543. Google Scholar
18. G. Sreelakshmi, M. Salman, K. Fatima and B. K. Madhavi , Efficient vedic signed digit decimal adder, 2018 4th Int. Conf. Devices, Circuits and Systems (ICDCS) (Coimbatore, India, March 2018), pp. 212–218. Google Scholar
19. K. Wiatr and E. Jamro , Constant coefficient multiplication in fpga structures, Proc. 26th Euromicro Conf. (EUROMICRO 2000), Informatics: Inventing the Future, Vol. 1 (Maastricht, Netherlands, September 2000), pp. 252–259. Crossref, Google Scholar
20. M. A. Soderstrand , Csd multipliers for fpga dsp applications, Proc. 2003 Int. Symp. Circuits and Systems, 2003. (ISCAS ’03) (Bangkok, 5 May 2003), pp. V–V. Google Scholar
21. M. Benhamid and M. Othman , Fpga implementation of a canonical signed digit multiplier-less based fft processor for wireless communication applications, 2006 IEEE Int. Conf. Semiconductor Electronics (Kuala Lumpur, October 2006), pp. 641–645. Google Scholar
22. G. C. Cardarilli, S. Pontarelli, M. Re and A. Salsano , On the use of signed digit arithmetic for the new 6-inputs lut based fpgas, 2008 15th IEEE Int. Conf. Electronics, Circuits and Systems (St. Julien’s, August 2008), pp. 602–605. Google Scholar
23. W. Kamp, A. Bainbridge-Smith and M. Hayes , Efficient implementation of fast redundant number adders for long word-lengths in fpgas, 2009 Int. Conf. Field-Programmable Technology (Sydney, NSW, December 2009), pp. 239–246. Google Scholar
24. R. Rani, L. K. Singh and N. Sharma , Fpga implementation of fast adders using quaternary signed digit number system, 2009 Int. Conf. Emerging Trends in Electronic and Photonic Devices Systems (Varanasi, December 2009), pp. 132–135. Google Scholar
25. K. Schneider and A. Willenbücher , A new algorithm for carry-free addition of binary signed-digit numbers, 2014 IEEE 22nd Annual Int. Symp. Field-Programmable Custom Computing Machines (Boston, Massachusetts, May 2014), pp. 44–51. Google Scholar
26. R. Thakur, S. Jain and M. Sood , Fpga implementation of unsigned multiplier circuit based on quaternary signed digit number system, 2017 4th Int. Conf. Signal Processing, Computing and Control (ISPCC) (Solan, Sepember 2017), pp. 637–641. Google Scholar
27. Altera Corporation, Cyclone IV Device Handbook (2016), https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/cyclone-iv/cyclone4-handbook.pdf. Google Scholar

Vol. 29, No. 09

Metrics

Downloaded 770 times

History

Received 1 April 2019

Accepted 15 September 2019

Published: 1 November 2019

Information

This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC BY) License. which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Novel Binary Signed-Digit Addition Algorithm for FPGA Implementation

Abstract

Recommended