 Open Access
 Authors : Mohammed I. Daabo
 Paper ID : IJERTV12IS060154
 Volume & Issue : Volume 12, Issue 06 (June 2023)
 Published (First Online): 04072023
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Efficient Overflow Detection and Correction in RNS Addition using Partial Reverse Conversion: Exploring the Moduli Set {22n11, 2n, 2n 1}
Mohammed I. Daabo
Department of Computer Science, School of Computing and Information Sciences,
C. K. Tedam University of Technology and Applied Sciences, Ghana
ABSTRACTThis research paper presents a comprehensive algorithm for detecting and correcting overflow in Residue Number System (RNS) architecture. The underlying principle of the proposed algorithm relies on the Chinese Reminder Theorem, that enables the detection of overflow in RNS addition of two operands. Additionally, the scheme utilizes partial reverse conversion to identify overflow accurately and deliver errorfree results. Subsequently, the algorithm is implemented using the moduli set {22n11, 2n, 2n 1}. To demonstrate the effectiveness of this proposed scheme, a comparison profile is conducted and evaluated on the delay and area requirements. In all, the scheme showcases superior performance in terms of both AD2(resources) and delay(speed), surpassing the capabilities of existing scheme. It is however observed that the new technique will impose high computational complexity (Area) Keywords: Residue Number System, reverse conversion, Chinese Reminder Theorem, Overflow, operands.

INTRODUCTION
Residue number system (rns) is an integer number system that utilizes remainders called residues to represent numbers. It supports parallelism, carryfree and borrowfree arithmetic and ensure single step multiplication without partial products. These unique characteristics make RNS particularly suitable for applications in the field of Digital Signal Processing (DSP), digital filtering, convolutions, correlations, Discrete Fourier Transforms (DFT), Fast Fourier Transforms (FFT) and Direct Digital Frequency Synthesis (DDFS) [5], [6]. However, for a successful application of RNS, overflow detection and correction must be easier and faster to perform so as not to limit the full usage of RNS in general purpose computing. In Weighted Number System (WNS), overflow can be efficiently handled by rounding, truncating or saturating arithmetic. Overflow detection in RNS involves more complex and timeconsuming procedures. RNS is determined by a set S, of N integers that are pairwise relatively
prime. That is = {, } where for ,
=1… and , and gcd means the greatest common divisor [1]. Every integer in [0,1] can be uniquely represented with Ntuple where, (1, 2,,) and = ( mod
); for =1 . The set S and the number are called the moduli set and residue of X modulo respectively. In order to calculate the
number X from its residues, we can apply the CRT which relates X
and its RNS representation by:
(1) Where ;
with and being the multiplicative
inverse of . Overflow in computing refers to storing data that is larger than its designated memory location. Overflow is described in RNS as a condition in which a number falls outside the valid range of a specific RNS. A valid RNS number [4] is well represented by a number from the set [0. Ml]. Take, for example, the sum of the decimal numbers 90 and 25, which equals 115. The outcome of performing this addition in RNS with the moduli set {3, 5, 7} with dynamic range of 105 is . However, the number is the decimal equivalent of 10. This is because the sum of 90 and 25, which is 115, is outside the legitimate range, therefore introducing an overflow in the sum. The traditional overflow detection technique utilizes either the Chinese Remainder Theorem (CRT) [4] or the Mixed Radix Conversion (MRC) techniques.
In recent time, researchers have made considerable efforts to design efficient overflow detection schemes which are dependent on full reverse conversion [11]. Some proposed RNS overflow detection algorithms that are based on operands examination [4] and other costly and time consuming procedures such as base extension, use of redundant RNS, group number approach and sign detections as in [8] and [7] The scheme in [4] is demonstrated to be better than those in [2] and [8] in terms of both area and delay. This research paper introduces a proposed scheme for detecting and correcting overflow in the Residue Number System (RNS) architecture. The proposed scheme employs partial reverse conversion, utilizing the Chinese Reminder Theorem (CRT) technique.

PROPOSED ALGORITHM
The proposed algorithm using CRT is presented in details in this section. The presented scheme detects overflow and corrects it.

Algorithm for the Proposed Scheme
The algorithm for the proposed method is as follows: [9]

Accept X and Y

Determine and y according to [7]

Determine E and according to [10] and [11]

Overflow occurs only under one of the following conditions:

If the MSB of E i.e. E4n = 1

If E41 down to E0 is 1

If E41 down to E1 is 1 and = 1


The correct result is computing Z according to (10)

, ,
(2)
Lemma 1 :For the given moduli set, we have
(3)
Property 2: The residue of a negative residue number (v) in modulo (2n 1) is the ones complement of v, where 0 v < 2n 1. Equation (7) can further be simplified as follows:
The proof of (3) (5) is demonstrated in (10)
Lemma 2:
(4)
(5)
(14)
Let (15)
(16)
(17)
Using CRT in (1) the binary number can be written as:
Subtracting x2 from both sides of the above expression and dividing by 2n, the binary number is obtained as:
(18)
It is necessary to note that means the bit of .
Evaluation of 1
Where
(6)
The residue can be represented as follows:
(19)
The residue can be represented in 4n bits as follows:
(7)
From (6), let X and Y be two RNS numbers such that their sum is Z. From (6) it implies that:
We evaluate the two parts of 1 separately using property 1
Where and
Let
Lemma 3:
(8)
(9)
, (10)
(11)
=
=
By adding the two above expressions we have the final value of 1
as 1
=
Given any two (2) RNS numbers = (1, 2, 3) and = (1, 2, 3),
overflow occurs if and only if
E (12)
Proof
Assume (12) holds true; then for (10)
Z
Which is outside the legitimate range, i.e. [0, M1], hence overflow will occur
Furthermore, if (13) holds true then (10) can be rewritten as Z = 2n ( + 1) (13)
Z = 2n ( Z = M
Which is also outside the legitimate range, therefore overflow will
occur. Hence the proof. From equation (10), Z will be the correct
result of summing and whether overflow occurs or not in the given moduli set, but will be out of the range in [0, 1] if either
(12) or (13) holds; therefore, E should be added to the DR to be [0,
+E1] in order to legitimize Z.


HARDWARE IMPLEMENTATION
In order to reduce the hardware complexity, we use the following properties to simplify equation (7).
Property 1: The multiplication of a residue number v by 2P in modulo (2n 1) is carried out by P bit circular left shift, where P is a natural number.
which is a 4n bits residue number. (20) Evaluation of 2
The residue can be represented as follows;
(21)
The residue can be represented in 4n bits as follows;
By applying property 1:
And finally by applyng property 2 we get:
= (22)
Where means the complement of
Evaluation of 3 and 4
The residue can be represented as follows;
(23)
The residue can be represented in 4 bits as follows:
By applying property 1:
Again, =
And finally by applying property 2 we get:
(24)
(25)
Another multiplexer (MUX 2) is used to set as zero if the most significant bit (MSB) of R is 0, or as one (1) if the MSB of R is 1. This configuration is illustrated in figure 2, representing the overflow detection unit.
The CSAs 1 and 2 require an area of 4nA each, while CPAs 1 and 2 also require 4nA each. Therefore, the total area required to obtain is 16nA. Consequently, for two numbers X and Y, the total area requirement is 32nA. CPA 3 requires an area of (4n+1)A, and CPA 4 requires (n+1)A. Hence, the area requirement for the overflow detection component is (5n+2)A.
Therefore, the overall area requirement of the overflow detection
scheme is (37n+2)A.
In order to evaluate the sum Z, we further simplify equation (10)
(26)
= (27)
(28)
Therefore,
(29)
Implementation of equations (26) – (29) gives the correct result of Z whether overflow occurs or no
Figure 1: Block diagram of the partial reverse converter

PROPOSED ARCHITECTURE
The output of the partial reverse converter is determined using equation (14), where the parameters are defined in equations (15) to (18). The values corresponding to numbers X and Y, denoted as and respectively, are computed using CSAs 1 and 2, along with regular 4nbit CPAs 1 and 2. The results from these CPAs are passed to a multiplexer (MUX 1), which selects either CPA 1 or CPA 2 based on the carry out of CSA 1.
The value corresponds to the decimal number X, and corresponds to the decimal number Y. They are added using a regular (4n+1)bit CPA 3 to obtain E. Simultaneously, x_2 and y_2 are computed using a regular (n+1)bit CPA 4 to obtain R.
In terms of delay, each CSA (CSAs 1 and 2) introduces a delay of
, while each CPA (CPAs 1 and 2) imposes a delay of 4n. Since they operate in parallel, for two numbers, the total delay
becomes 8n. Thus, the delay for computing is (8n+2). The CPA pair 3 and 4 together impose a delay of (4n+1)D for the
overflow detection unit. Therefore, the required delay for the
proposed scheme is (12n+3)D.
The correction unit utilizes a regular (5n+1)bit CPA 5. It requires an
area of (5n+1)A and has a delay of (5n+1)D.
The schematic diagrams for the proposed scheme is provided below.
Figure 2: Overflow Detection

NUMERICAL ILLUSTRATIONS
In this section, some numerical examples with the proposed scheme are presented.
From the moduli set {22n11, 2n, 2n 1}, when n , we have {7, 4, 3}.
Given two (2) numbers and , we then check for overflow in the sum of and using moduli set {7, 4, 3}.
{22n1 1, 2n, 2n – 1}, where 1 = 22n1 1, 2 = 2n and 3 = 2 1 we
have =
= , ,
Therefore
RNS to decimal conversion of
will result in the decimal
number 12432. Whilst the sum of the decimal numbers 825 and 500 is 1337. Clearly, this is a sign that overflow has occurred.
To check this RNS overflow, the following proposed algorithm is used.
Given that:
Since the MSB of E is 1, the scheme will detect that overflow has occurred.
From the moduli set {22n11, 2n, 2n 1}, when n =3 , we have {31, 8, 7}
Given two (2) numbers and , we then check for overflow in the sum of and using moduli set . Thus
Therefore,
RNS to decimal conversion of
will result in the decimal number 1225844 which is the correct result of 7285 + 16380.
Figure 4: Area graphs
Figure 5: Graph of AD2

PERFORMANCE EVALUATION
This section presents and analyzes the architectural performance of the proposed scheme in terms of Area, Delay and AD2.. The results is compared with the proposal presented in [4]. From Table 1, the proposed method has less delay and AD2 than [4] but presented a large architectural size (Area). It can be noted that as n increases, the proposed scheme becomes faster, necessitating less delay as shown in Figure 3. It is however observed in Figure 4 that there is a higher hardware complexity associated with the suggested technique and this can be attributed to the broader dynamic range of the moduli set chosen. The AD2 comparison in Figure 5 shows that the suggested method will consume fewer resources than the scheme proposed in [4].
Figure 3: Delay graphs

CONCLUSION
This study focused on addressing the issue of overflow detection during addition operation in Residue Number System (RNS). This phenomenon has been one of the limiting factors that prevents RNS from being utilize in generalpurpose computing. The research paper proposed a comprehensive algorithm for detecting overflow and applied it to the moduli set {22n11, 2n, 2n 1}. Notably, these algorithm does not require a complete residuetobinary conversion process. The proposed scheme ensures the accurate computation of the sum of two numbers, regardless of whether an overflow occurs or not. Moreover, the chosen moduli set offers a wider dynamic range, making the scheme more effective and efficient in terms of Delay and AD2 but fall short in Area compared to the proposal in [4].

REFERENCES
No.4, pp. 295299
[2] D. Younes and P. Steffan (2013). Universal approaches for overflow and sign detection in residue number system based on {2n 1, 2n, 2n +1}. The Eighth International Conference on Systems (ICONS 2013), pp. 77 84. [3] E. K. Bankas and K. A. Gbolagade (2013). A New Efficient FPGA Design of Residuetobinary Converter. International Journal of VLSI design & Communication Systems (VLSICS) Vol.4, No.6. [4] H. Siewobr and K. A. Gbolagade (2014). RNS Overflow Detection by Operands Examination. International Journal of Computer Applications (0975 8887), Vol 85, No. 18 . [5] K. A. Gbolagade (2013) . An Efficient MRC based RNS to Binary Converter for the {22n1, 2n, 22n+11} Moduli Set. International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) Volume 2, Issue 4. [6] K.A. Gbolagade, R. Chaves, L. Sousa, and S.D. Cotofana (2010). An improved reverse converter for the {22n+1 1,2n, 2n 1} moduli set. IEEE International Symposium on Circuits and Systems (ISCAS 2010), pp. 21032106.
[7] L. Theodore Houk (1989).Residue Addition Overflow Detection Processor. Boing Company, Seatle, Wash. Appl. No.:414276. [8] M. Rouhifar, M. Hosseinzadeh, S. Bahanfar and M. Teshnehlab (2011).Fast Overflow Detection in Moduli Set. International Journal of Computer Science Issues, Vol. (8/3), pp. 407414. [9] P. A. Agbedemnab and E.K. Bankas(2015). A Novel RNS Overflow Detection and Correction Algorithm for the Moduli Set{2n1,2n,2n+1}. International Journal of Computer Applications (975 8887) [10] P. A. Mohan (2007). Reverse Converters for a New Moduli Set {22n – 1, 2n, 22n + 1}. Circuit Systems Signal Processing, 26: 215. [11] Salifu, A. (2021). New Reverse Conversion for FourModuli Set and FiveModuli Set. Journal of Computer and Communications, 9, 5766.Table 1. Area, Delay and AD2 Comparison
SCHEME 
[4] 
PROPOSED 

n 
Delay1 (22n+12) 
Area1 (11n+6) 
AD2(1) (5324n3+81712n2+4752n+864) 
Delay2 (12n+3) 
Area2 (37n+2) 
AD2(2) (5328n3+2952n2+477n+18) 

2 
56 
28 
379808 
27 
76 
17036 

3 
78 
39 
894276 
39 
113 
42381 

4 
100 
50 
1668000 
51 
150 
83206 

5 
122 
61 
2732924 
63 
187 
142703 

6 
144 
72 
4120992 
75 
224 
224064 

7 
166 
83 
5864148 
87 
261 
330481 

8 
188 
94 
7994336 
99 
298 
465146 

9 
210 
105 
10543500 
111 
335 
631251 

10 
232 
116 
13543584 
123 
372 
831988 

11 
254 
127 
17026532 
135 
409 
1070549 

12 
276 
138 
21024288 
147 
446 
1350126 

13 
298 
149 
25568796 
159 
483 
1673911 