Overflow Detection in Residue Number System, Moduli Set {2n-1,2n,2n+1}

Subject Areas : Computer Architecture and Digital Systems

Babak Tavakoli ¹ , Mehdi Hosseinzadeh ² , Somayeh Jassbi ³

1 - Islamic Azad University, Science and Research Branch
2 - Islamic Azad University, Science and Research Branch
3 - Islamic Azad University, Science and Research Branch

Received: 2015-11-23 Accepted : 2015-12-12 Published : 2016-02-01

Keywords: Overflow Detection, Computer Arithmetic, Residue Number System,

Abstract :

Residue Number System (RNS) is a non-weighted number system for integer number arithmetic, which is based on the residues of a number to a certain set of numbers called module set. The main characteristics and advantage of residue number system is reducing carry propagation in calculations. The elimination of carry propagation leads to the possibility of maximizing parallel processing and reducing the delay. Residue number system is mostly fitted for calculations involving addition and multiplication. But some calculations and operations such as division, comparison between numbers, sign determination and overflow detection is complicated. In this paper a method for overflow detection is proposed for the special moduli set {2n-1,2n,2n+1} . This moduli set is favorable because of the ease of calculations in forward and reverse conversions. The proposed method is based on grouping the dynamic range into groups by using the New Chinese Theorem and exploiting the properties of residue differences. Each operand of addition is mapped into a group, then the sum of these groups is compared with the indicator and the overflow is detected. The proposed method can detect overflow with less delay comparing to previous methods.

References:

[1] Omondi A., Premkumar B., RESIDUE NUMBER SYSTEMS, Theory and Implementation, ImperialCollege Press, 2007.
[2] N. S. Szabo and R. I. Tanaka, Residue Arithmetic and Its Application to Computer Technology, New York: McGraw- Hill, 1967.
[3] Parhami B., Computer arithmetic Algorithms and hardware designs, Oxford University Press, 2000.
[4] Miller D.D., Analysis of the residue class core function of Akushskii, Burcev, and Park. In: G. Jullien, Ed., RNS Arithmetic: Modern Applications in Digital Signal Processing. IEEE Press 1986.
[5] Zimmermann R., Efficient VLSI implementation of modulo 2n+-1 addition and multiplication. Proc. 14th IEEE Symp. Computer Arithm. , Adelaide, Australia, 1999, pp. 158–167
[6] Zarei B., Askarzadeh M., Derakhshanfard N.,Hosseinzadeh M., A High-speed Residue Number Comparator For the 3-Moduli Set {2n-1, 2n+1, 2n+3}.Proceedings of International Symposium on Signals, Systems and Electronics (ISSSE2010),2010
[7] DEBNATH R.C., PUCKNELL D.A.,ON MULTIPLICATIVE OVERFLOW DETECTION IN RESIDUE NUMBER SYSTEM,Department of Electrical Engineering University of Adelaide, 1977
[8] Askarzadeh M.,Hosseinzadeh M., Keivan Navi K.,A New approach to Overflow detection in moduli set {2n-3, 2n-1, 2n+1, 2n+3},Second International Conference on Computer and Electrical Engineering,2009
[9] Rouhifar M.,Hosseinzadeh M.,Bahanfar S.,Teshnehlab M.,Fast Overflow Detection in Moduli Set {2n – 1, 2n, 2n + 1},IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 3, No. 1, May 2011
[10] Shaoqiang B., Groos W.J.,Efficient Residue Comparison Algorithm for General Moduli Sets,IEEE International Circuits and Systems, 2005, (2): 1601-1604.
[11] Gholami E., Farshidi R., Hosseinzadeh M., Navi K.,High speed residue number system comparison for the moduli set {2n-1, 2n, 2n+1},Journal of Communication and Computer, ISSN 1548-7709, USA,2009.
[12] TAI L.C.,CHEN C.F., Overflow Detection In a Redundant Residue Number System,IEE PROCEEDINGS, Vol. 131, Pi. E, No. 3, MAY 1984
[13] Wang Y., Song X., Abdolhamid M., Shen H., Adder based residue to binary converters for {2n-1, 2n, 2n+1}, 2002, pp. 1772-1779