Improved Modulo 2n +1 Adder Design

Authors: Somayeh Timarchi, Keivan Navi

Abstract:

Efficient modulo 2n+1 adders are important for several applications including residue number system, digital signal processors and cryptography algorithms. In this paper we present a novel modulo 2n+1 addition algorithm for a recently represented number system. The proposed approach is introduced for the reduction of the power dissipated. In a conventional modulo 2n+1 adder, all operands have (n+1)-bit length. To avoid using (n+1)-bit circuits, the diminished-1 and carry save diminished-1 number systems can be effectively used in applications. In the paper, we also derive two new architectures for designing modulo 2n+1 adder, based on n-bit ripple-carry adder. The first architecture is a faster design whereas the second one uses less hardware. In the proposed method, the special treatment required for zero operands in Diminished-1 number system is removed. In the fastest modulo 2n+1 adders in normal binary system, there are 3-operand adders. This problem is also resolved in this paper. The proposed architectures are compared with some efficient adders based on ripple-carry adder and highspeed adder. It is shown that the hardware overhead and power consumption will be reduced. As well as power reduction, in some cases, power-delay product will be also reduced.

Keywords: Modulo 2n+1 arithmetic, residue number system, low power, ripple-carry adders.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083569

References:

[1] H. Garner, "The residue number system," IRE Trans. Electronic Computer, vol. EC-8, pp.140-147, Jun.1959.
[2] N. Szabo and R. Tanaka, "Residue arithmetic and its applications to computer technology," New York, LCCCN: 66-15186, McGraw-Hill Book Company, 1967.
[3] R. Conway and J. Nelson, "Improved RNS FIR Filter Architectures", IEEE Trans. On Circuits and Systems-II: Express Briefs, vol. 51, no. 1, Jan. 2004.
[4] P. G. Fernandez, et al., "A RNS-Based Matrix-Vector-Multiply FCT Architecture for DCT Computation," Proc. 43th IEEE Midwest Symposium on Circuits and Systems, pp. 350-353, 2000.
[5] L. Yang and L. Hanzo, "Redundant Residue Number System Based ERROR Correction Codes", IEEE VTS 54th on Vehicular Technology Conference, vol. 3, pp. 1472 - 1476, 7-11 Oct. 2001.
[6] J. Ramirez, et al., "Fast RNS FPL-Based Communications Receiver Design and Implementation," Proc. 12th Int-l Conf. Field Programmable Logic, pp. 472-481, 2002.
[7] R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Comm. ACM, vol. 21, no. 2, pp. 120-126, Feb. 1978.
[8] J. Bajard, and L. Imbert, "A Full RNS Implementation of RSA," IEEE Transactions on Computers, vol. 53, no. 6, pp. 769-774, Jun 2004.
[9] A. S. Molahosseini, K. Navi, O. Hashemipour, A. Jalali, "An efficient architecture for designing reverse converters based on a general threemoduli set", Journal of Systems Architecture, no. 54, pp. 929-934, 2008.
[10] M. Hosseinzade, S. Timarchi, and K. Navi, "Multi Level Residue Number ber System with Moduli Set of (2n ,2n -1,2n-1 -1) ", 12th International CSI Computer Conference, 20-22 Feb. 2007.
[11] A. Hariri, K. Navi, and R. Rastegar, "A New High Dynamic Range Moduli Set with Efficient Reverse Converter", Elsevier Journal of Computers & Mathematics with Applications, vol. 55, Issue 4, pp. 660- 668, Feb. 2008.
[12] M. Hosseinzadeh, K. Navi and S. Timarchi, "Design of Current Mode Circuits of Residue Number Systems", 14th Iranian Conference of Electrical Engineering (ICEE-2006), 16-18 May 2006.
[13] M. Hosseinzadeh, A. Sabbagh, K. Navi, "A Fully Parallel Reverse Converter", International Journal of Electrical, Computer, and Systems Engineering, vol. 1, no. 3, 2007.
[14] A. S. Molahosseini, and K. Navi, "New arithmetic Residue to Binary converters", IJCSES International Journal of Computer Sciences and Engineering Systems, vol. 1, no.4, pp. 295-299, October 2007.
[15] C. Efstathiou, H. T. Vergos and D. Nikolos, "Fast Parallel-Prefix 2n+1 Adder", IEEE Trans. On Computers, vol. 53, no. 9, Sep. 2004.
[16] L. M. Leibowitz, "A Simplified Binary Arithmetic for the Fermat Number Transform," IEEE Trans. Acoustics, Speech, Signal Processing, vol. 24, pp. 356-359, 1976.
[17] H.T. Vergos, et al., "Diminished-1 Modulo 2n+1 Adder Design," IEEE Trans. Computers, vol. 51, pp. 1389-1399, 2002.
[18] R. Zimmermann, "Efficient VLSI Implementation of Modulo (2n┬▒1) Addition and Multiplication," Proc. 14th IEEE Symp. Computer Arithmetic, pp. 158-167, Apr. 1999.
[19] S. Timarchi, O. Kavehei, and K. Navi, "Low Power Modulo 2n+1 Adder Based on Carry Save Diminished-1 Number System," American Journal of Applied Sciences 5 (4), pp. 312-319, 2008.
[20] S. Timarchi and K. Navi, "A Novel Modulo 2n+1 Adder Scheme", 12th International CSI Computer Conference, 20-22 Feb. 2007.
[21] M. Bayoumi and G. Jullien, "A VLSI Implementation of Residue Adders," IEEE Trans. Circuits Systems, vol. 34, pp. 284-288, 1987.
[22] A. A. Hiasat, "High-Speed and Reduced Area Modular Adder Structures for RNS," IEEE Trans. Computers, pp. 84-89, 2002.
[23] M. Hosseinzadeh, K. Navi, and S. Timarchi, "New Design of RNS High Speed Multi Operand Adder," 14th Iranian Conference of Electrical Engineering, 16-18 May 2006.
[24] S. Timarchi, K. Navi, and M. Hosseinzade, "New Design of RNS Subtractor for modulo 2n+1," 2nd IEEE International Conference on Information & Communication Technologies: From Theory to Application, 24-28 Apr. 2006.
[25] B. Parhami, "RNS Representation with Redundant Residues", Proc. of the 35th Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, CA, pp. 1651-1655, 4-7 Nov. 2001.
[26] C. Efstathiou, H. T. Vergos, and D. Nikolos, "Handling Zero in Diminished-1 Modulo 2n+1 Adders," International Journal of Electronics, vol. 90, no. 2, pp. 133-144, Feb. 2003.