A Robust Redundant Residue Representation in Residue Number System with Moduli Set(rn-2,rn-1,rn)

Authors: Hossein Khademolhosseini, Mehdi Hosseinzadeh

Abstract:

The residue number system (RNS), due to its properties, is used in applications in which high performance computation is needed. The carry free nature, which makes the arithmetic, carry bounded as well as the paralleling facility is the reason of its capability of high speed rendering. Since carry is not propagated between the moduli in this system, the performance is only restricted by the speed of the operations in each modulus. In this paper a novel method of number representation by use of redundancy is suggested in which {rn- 2,rn-1,rn} is the reference moduli set where r=2k+1 and k =1, 2,3,.. This method achieves fast computations and conversions and makes the circuits of them much simpler.

Keywords: Binary to RNS converter, Carry save adder, Computer arithmetic, Residue number system.

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

References:

[1] Barsi, F.; Maestrini, P.; , "Error Detection and Correction by Product Codes in Residue Number Systems," Computers, IEEE Transactions on , vol.C-23, no.9, pp. 915- 924, Sept. 1974.
[2] Di Claudio, E.D.; Piazza, F.; Orlandi, G.; , "Fast combinatorial RNS processors for DSP applications," Computers, IEEE Transactions on , vol.44, no.5, pp.624-633, May 1995.
[3] Banerjee, S.; Sinha, A.; , "A reconfigurable Digital Signal Processor using residue number system," Information Sciences Signal Processing and their Applications (ISSPA), 2010 10th International Conference on , vol., no., pp.405-408, 10-13 May 2010.
[4] Wei Wang; Swamy, M.N.S.; Ahmad, M.O.; , "RNS application for digital image processing," System-on-Chip for Real-Time Applications, 2004.Proceedings. 4th IEEE International Workshop on, vol., no., pp. 77- 80, 19-21 July 2004.
[5] Taleshmekaeil, D.K.; Mousavi, A.; , "The use of Residue Number System for improving the Digital Image Processing," Signal Processing (ICSP), 2010 IEEE 10th International Conference on , vol., no., pp.775-780, 24-28 Oct. 2010.
[6] Mirshekari, Ali; Mosleh, Mohammad; , "Hardware implementation of a fast FIR filter with residue number system," Industrial Mechatronics and Automation (ICIMA), 2010 2nd International Conference on , vol.2, no., pp.312-315, 30-31 May 2010.
[7] Shahana, T.K.; James, R.K.; Jose, B.R.; Jacob, K.P.; Sasi, S.; , "Performance analysis of FIR digital filter design: RNS versus traditional," Communications and Information Technologies, 2007. ISCIT '07. International Symposium on , vol., no., pp.1-5, 17-19 Oct. 2007.
[8] Taylor, F. J.; Papadourakis, G.; Skavantzos, A.; Stouraitis, A.; , "A Radix-4 FFT Using Complex RNSArithmetic," Computers, IEEE Transactions on , vol.C-34, no.6, pp.573-576, June 1985.
[9] Ben-Dau Tseng; Jullien, G.A.; Miller, W.C.; , "Implementation of FFT Structures Using the Residue Number System," Computers, IEEE Transactions on , vol.C-28, no.11, pp.831-845, Nov. 1979.
[10] Panella, M.; Martinelli, G.; , "RNS quasi-chaotic generator for selfcorrecting secure communication," Electronics Letters , vol.37, no.5, pp.325-327, 1 Mar 2001.
[11] Parhami, B.; , "RNS representations with redundant residues," Signals, Systems and Computers, 2001. Conference Record of the Thirty-Fifth Asilomar Conference on , vol.2, no., pp.1651-1655 vol.2, 2001.
[12] Garner, Harvey L.; , "The Residue Number System," Electronic Computers, IRE Transactions on , vol.EC-8, no.2, pp.140-147, June 1959.
[13] Molahosseini, A.S.; Navi, K.; Dadkhah, C.; Kavehei, O.; Timarchi, S.; , "Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n−1, 2n, 2n+1, 22n + 1−1} and {2n−1, 2n+1, 22n, 22n+1} Based on New CRTs," Circuits and Systems I: Regular Papers, IEEE Transactions on, vol.57, no.4, pp.823- 835, April 2010.
[14] Mohan, P.V.A.; , "RNS-To-Binary Converter for a New Three-Moduli Set {2n+1−1,2n,2n−1}," Circuits and Systems II: Express Briefs, IEEE Transactions on , vol.54, no.9, pp.775-779, Sept. 2007.
[15] Cao, B.; Chang, C.-H.; Srikanthan, T.; , "A Residue-to-Binary Converter for a New Five-Moduli Set," Circuits and Systems I: Regular Papers, IEEE Transactions on , vol.54, no.5, pp.1041-1049, May 2007.
[16] Khademolhosseini, H.; Roohi, A.; , "A new redundant method on representing numbers with moduli set {3n, 3n−1, 3n−2}," Computer, Communication and Electrical Technology (ICCCET), 2011 International Conference on , vol., no., pp.163-166, 18-19 March 2011.
[17] Atkins, D.E.; , "Introduction to the Role of Redundancy in Computer Arithmetic," Computer , vol.8, no.6, pp.74-77, June 1975.
[18] Hosseinzadeh, M.; Navi, K.; Gorgin, S.; , "A New Moduli Set for Residue Number System: {rn−2, rn−1, rn}," Electrical Engineering, 2007. ICEE '07. International Conference on , vol., no., pp.1-6, 11-12 April 2007.
[19] Abdallah, M.; Skavantzos, A.; , "On MultiModuli residue number systems with moduli of forms ra, rb-1, rc+1," Circuits and Systems I: Regular Papers, IEEE Transactions on , vol.52, no.7, pp. 1253- 1266, July 2005.