Abstract

Reverse Conversion and Overflow Detection are some of the limiting factors that affect the full implementation of RNS-Based processors in general purpose computing. In this paper, a novel Reverse Converter with overflow detection scheme has been proposed. The Algorithm utilizes the Remainder Theorem and has the property that for any given moduli set { m_(1 ) 〖,m〗_(2 ) 〖,m〗_3 } , the residue number ( x_1 〖,x〗_2 〖,x〗_3 ) can be converted into their decimal equivalent X using m_1 α+x_1, |m_1 α+x_1 |_(m_2 )= x_2 and |m_1 α+x_1 |_(m_3 )= x_3 for α = 0, 1, 2, 3, …. The Algorithm detects overflow in RNS operations if m_1 α+x_1≥M. The Algorithm was fully implemented on both moduli sets with common factors and moduli sets with non-coprime factors. Theoretical analysis and simulated results showed that the architecture is built with lesser hardware and has low delay.

References

• Skanvantzos, A. and Wang, Y. 1999 Implementation issues of the two-level residue number system with pair of conjugate moduli”. IEEE Transactions on Signal Processing. Vol.47, No.3, March 1999.
• Koc, C.K. 1991. An Inproved Algorithm for Mixed-Radix Conversion of Residue Numbers. Computers and Maths. Applic., Vol.22, no.8, pp.63-71.
• Papocheristou, C.R. 1977 Characteristic Measures of Switching Function. Inform. Sci., vol.13, pp.51-75.
• Taylor, F.J 1984. Residue Arithmetic: A tutorial with examples. IEEE Computer Magazine, vol.17, pp.50-62..
• Yassine, H.M. 1992. Matrix mixed-radix conversion for RNS arithmetic architecture. 34th Midwest Symposium on Circuits and Systems, pp.273-278.
• Igarashi. 1979. An Improved Lower Bound on the Maximum Number of Prime Inplicants. Trans. IECE, Japan, vol. E-62, pp.389-394.
• Gbolagade, K.A and Cotofana, S.D. 2008 MRC Technique for RNS to Decimal Conversion for the moduli set {2n+2, 2n+1, 2n}”. 16th Annual Workshop on Circuits, Systems and Signal Processing, pp.318-321, Veldhoven, The Netherlands.
• Gbolagade, K.A. 2010. Effective Reverse Conversion in Residue Number System Processors. PhD Thesis, Delft University of Technology The Netherlands, PP. 15.
• Gbolagade, K.A and Cotofana, S.D. 2009. Residue-to-decimal converters for moduli set with common factors”. 52nd IEEE International Midwest Symposium on Circuits and Systems (MINSCAS, 2009), PP.624-627.
• Abdallah, M. and Skavantzos, A. 1997 (On the binary quadratic residue number system with non-coprime moduli”. IEEE Transactions on Signal Processing, Vol.45,No.8.
• Sheu, M., Lin, S., Chen, C. and Yang, S. 2004. An Efficient VLSI Design for Residue to Binary Converter for General Balance Moduli (2n-3, 2n-+1, 2n-1, 2n+3)”. IEEE Transactions on Circuits and Systems- II. Express Briefs, Vol.51, no.3.
• Soderstand, M.A., Jenkins, W.K., Jullien G.A and Taylor, F.J. 1986 Residue Number System Arithmetic: Modern Application in Digital Signal Processing”. IEEE press, New York, 1986.
• Daabo, M.I and Gbolagade, K.A. 2012 RNS Overflow Detection Scheme for the Moduli Set {M-1, M}. Journal of computing, Vol. 4, Issue 8 pp.39-44. ISSN (Online) 2151-9617.
• M.I. Daabo and Gbolagade, K.A 2012 Overflow Detection Scheme in RNS Multiplication Before Forward Conversion. Journal of computing, Volume 4, Issue 12, pp. 13-16 ISSN (Online) 2151-9617.
• Chakraborti, N.B., Soundararajan, S and Reddy, A.L.N. 1986 An Implementation of Mixed Radix Conversion for Residue Number Application, IEEE Transactions on Computers, Vol. c-35, no. 8.
• Szabo, N.S. and Tanaka, R.I. 1967 Arithmetic and Its Application to Computer Technology. New York: McGraw-Hill.
• Ananda. P.V., Mohan, 2002 Residue Number system: Algorithms and Architecture. Kluwer Academic New York.
• Stouratitis, T. and V. Paliouras, V. “ Considering the Alternatives in Low-Power Design”. IEEE
• Chren, W.A Jr. 1990 A new Residue Number System Division Algorithms”. Comput.Math. Appl., Vol.19, no.7, pp.13-29.