Research Article
A Novel RNS Overflow Detection and Correction Algorithm for the Moduli Set {2^n-1,2^n,2^n+1}
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 110 - Issue 16 |
| Published: January 2015 |
| Authors: P. A. Agbedemnab, E.K. Bankas |
10.5120/19403-0925
|
P. A. Agbedemnab, E.K. Bankas . A Novel RNS Overflow Detection and Correction Algorithm for the Moduli Set {2^n-1,2^n,2^n+1}. International Journal of Computer Applications. 110, 16 (January 2015), 30-34. DOI=10.5120/19403-0925
@article{ 10.5120/19403-0925,
author = { P. A. Agbedemnab,E.K. Bankas },
title = { A Novel RNS Overflow Detection and Correction Algorithm for the Moduli Set {2^n-1,2^n,2^n+1} },
journal = { International Journal of Computer Applications },
year = { 2015 },
volume = { 110 },
number = { 16 },
pages = { 30-34 },
doi = { 10.5120/19403-0925 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A P. A. Agbedemnab
%A E.K. Bankas
%T A Novel RNS Overflow Detection and Correction Algorithm for the Moduli Set {2^n-1,2^n,2^n+1}%T
%J International Journal of Computer Applications
%V 110
%N 16
%P 30-34
%R 10.5120/19403-0925
%I Foundation of Computer Science (FCS), NY, USA
Abstract
In this paper, an efficient scheme for detecting and correcting overflow during addition in Residue Number System (RNS) is presented. The approach which is novel to the moduli set {2^n-1,2^n,2^n+1} is based on the Chinese Remainder Theorem and demonstrates theoretically to be a very fast scheme compared to similar state of the art schemes. The proposed method is able to detect overflow in RNS addition without full reverse conversion; Additionally, the scheme also prevents the representation of wrong numbers as a result of overflow, thus the scheme gives the accurate result without errors whether overflow occurs or not. A comparison, which proves the efficiency of the proposed scheme, in terms of delay and area requirements is also presented.
References
- Omondi and B. Premkumar. Residue Number Systems: Theory and Implementation. Imperial College Press. UK 2007.
- K. A. Gbolagade. An Efficient MRC based RNS-to-Binary Converter for the {2^2n-1,2^n,2^(2n+1)-1} Moduli Set. International Journal of Advanced Research in Computer Engineering & Technology (IJARCET)Volume 2, Issue 4, April 2013.
- K. A. Gbolagade, R. Chaves, L. Sousa, and S. D. Cotofana. An improved reverse converter for the 2^(2n+1)-1,2^n,2^n-1 moduli set. IEEE International Symposium on Circuits and Systems (ISCAS 2010) , pp. 2103-2106, Paris, France, June,2010.
- D. Younes and P. Steffan. Universal approaches for overflow and sign detection in residue number system based on {2^n-1,2^n,2^n+1}. The Eighth International Conference on Systems (ICONS 2013), pp. 77 – 84, 2013.
- M. Rouhifar, M. Hosseinzadeh, S. Bahanfar and M. Teshnehlab. Fast Overflow Detection in Moduli set {2^n-1,2^n,2^n+1}. International Journal of Computer Science Issues, Vol (8/3), pp 407-414, May 2011.
- H. Siewobr and K. A. Gbolagade. RNS Overflow Detection by Operands Examination. International Journal of Computer Applications (0975 – 8887), Vol 85, No. 18, January, 2014.
- M. Hosseinzadeh, A. S. Molahosseini and K. Navi. A parallel Implementation of the Reverse Converter for the moduli set {2^n-1,2^n,2^(n-1)-1}. World Academy of Science, Engineering and Technology, Vol. 55, pp. 494-498. 2009.
- A. S. Molahosseini, K. Navi. New Arithmetic residue to binary Converters. International Journal of Computer Sciences and Engineering Systems, Vol. 1, No. 4, pp. 295-299 Oct. , 2007.
- E. K. Bankas and K. A. Gbolagade. A New Efficient FPGA Design of Residue-To-Binary Converter. International Journal of VLSI design & Communication Systems (VLSICS), Vol 4, No. 6, December, 2013.
Index Terms
Keywords