The week's pick
Reseach Article
Optimising the New Chinese Remainder Theorem 1 for the Moduli Set
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 148 - Number 4 |
| Year of Publication: 2016 |
| Authors: John Bosco Aristotle K. Ansuura, Ismail Rashid Fadulilahi |
10.5120/ijca2016906811
|
John Bosco Aristotle K. Ansuura, Ismail Rashid Fadulilahi . Optimising the New Chinese Remainder Theorem 1 for the Moduli Set. International Journal of Computer Applications. 148, 4 ( Aug 2016), 1-7. DOI=10.5120/ijca2016906811
Abstract
This paper seeks to improve the performance of the New Chinese Remainder Theorem (CRT) using the new moduli set {2^(2n+2)+3,2^(2n+1)+1,2^2n+1,2}. This optimization is very important in order to minimize the cost of hardware implementation and to improve the reverse conversion speed. The major factor responsible for this high hardware cost and high reverse conversion time is the presence of multipliers in the hardware implementation of the reverse converters. This paper proposes the moduli set {2^(2n+2)+3,2^(2n+1)+1,2^2n+1,2}, which is applicable for applications requiring larger dynamic range. The moduli set must be relatively prime integers. The computation of multiplicative inverses can be eliminated. We employ the proposed moduli set to optimize the New CRT-I. This scheme can result in less memory and adder based reverse converters, which is shown to be better than known existing similar state of the art scheme.
References
- Cao B., Chang C., Sirkanthan T (1998) A residue-to-binary converter for a new five-moduli set, IEEE Transactions on Circuits and Systems, 35 (11).
- Conway R. and Nelson J. (2004) Improved RNS FIR Filter Architectures, IEEE Transactions On Circuits and Systems II, Vol. 51, No. 1, pp. 26-28.
- Daabo M.I and Gbolagade K.A.Overflow Detection Scheme in RNS Multiplication Before Forward Conversion Journal of computing, Volume 4, Issue 12, pp. 13-16, December 2012 ISSN (Online) 2151-9617
- Daabo M.I and Gbolagade K.A. RNS Overflow Detection Scheme for the Moduli Set {M-1, M}.Journal of computing, Vol. 4, Issue 8 pp.39-44, August 2012 ISSN (Online) 2151-9617.
- Gbolagade K.A and Cotofana S.D. 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, November 2008.
- Gbolagade K.A and Cotofana S.D.Residue-to-decimal converters for moduli set with common factors. 52nd IEEE International Midwest Symposium on Circuits and Systems (MINSCAS, 2009), PP.624-627, 2009.
- Narayanaswamy N. (2010). Optimization of New Chinese Remainder Theorems using special moduli sets.
- Narayanaswamy N., Skavantzos A., Stouraitis T. (2010). Optimal Modulus Sets for Efficient Residue-to-Binary Conversion Using the New Chinese Remainder Theorems. Accepted in 17th IEEE International Conference on Electronics, Circuits, and Systems, Athens.
- Number systems, IEEE Trans. on CAS -I, Vol. 41, No. 12, pp. 927-
- Omondi A and Premkumar B (2007).Residue Number System- Theory and Implementation (Volume 2)
- Szabo, N.S and Tanaka, R.I. (1967). Residue Arithmetic and Its Applications to Computer Technology. McGraw-Hill, New York.
- Umar A. F (2011) Data conversion in Residue Number System, Department of Electrical and Computer Engineering Mc Gill University Montreal.
- Wang, Y., Song, X., Aboulhamid, M., Shen, H. (2002). Adder based residue to binary number converters for (2n-1, 2n, 2n+1), IEEE Transactions on Signal Processing, vol.50, no.7, pp.1772-1779.
- I. R. Fadulilahi, E. K. Bankas, J. B. A. K. Ansuura (2015). Efficient Algorithm for RNS Implementation of RSA. International Journal of Computer Applications 11/2015; Vol.127, No.5, pp.14-19.
Index Terms
Keywords