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

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.

Authors:

• Hossein Khademolhosseini
• Mehdi Hosseinzadeh

Keywords:

• Binary to RNS converter
• Carry save adder
• Computer arithmetic
• Residue number system.

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.