Wireless communication has become an indispensable part of our lives by improving interaction demands relating within our environment. The result of interference of information passing through different systems often caused by noise reduces the completeness of the information or data received. A Fault-tolerant mechanism for wireless networks is of utmost importance to be devised due to the use of modular arithmetic over identical channels. Using the RRNS technique, we will be able to compute using modular arithmetic over identical channels. We can make this system fault tolerant by increasing the number of channels by adding more redundant residues which provides the error detection and error correction functions resulting from RRNS. This capability makes the redundancy in RNS a great indication to exhibit a faster arithmetic process in the field of digitizing computer information. From receivers end, RRNS codes are decoded using CRT. Alternatively, scheme called MRC is also used which results in low decoding complexity when compared to CRT. This research presents a fault-tolerant technique which is based on the RRNS for multiple error detection and correction. This algorithm doesn't require look-up table and detects multiple error which helps to save memory during implementation.
Wireless Networks, Error Detection & Correction, Residue Number Systems (RNS), Redundant Residue Number Systems (RRNS), Chinese Remainder Theorem (CRT), Mixed Radix Conversion (MRC), Base Extension (BEX)
Generally in wireless network, set of data are corrupted during
transmission whenever bits flow from one point to another, they
are subject to unpredictable changes of interference [
For wireless network, the error detection and correction services are usually provided by communication protocols at the data link and the transport layers in the OSI model.
The error detection scheme requires certain amount of overhead in
term of additional bits which are added to the total transmitted
data. These additional bits are used by the receiver to check for
error on the sequence of data that might occur during the
transmission. Some error detection scheme could be used to
correct the error which is called error correction scheme.
However, the number of bits in error that can be detected may be
different depending on the scheme and required overhead [
Residue number system helps to increase the speed of arithmetic
operations when compared to other conventional number systems
in digital communication systems. Residue number system (RNS)
is a non-weighted, non positional number system which can be
represented by specifying its base. Thus, in RNS any given integer
is represented by a set of residues which are obtained by modulo
dividing the integer with moduli set[
Redundant residue number system (RRNS) is obtained by adding
some redundancy to the RNS. RRNS can be used for self
checking, error detection and error correction in digital computers
[
The fundamental arithmetic operations are carry-free in RNS
operations and does not propagate error from one residue digit to
other. Another interesting advantage of RNS operation is the lack
of ordered significance among residue digits. Therefore, an integer
can be recovered from its residues even after discarding some of
the redundant residues, provided that the retained residue digits
should be correct. RNS offers great speed as a result of its
underlying carry-free nature. As a result, these have increased the
development of a number of error detection and error correction
algorithms based on RNS [
The uniqueness of the proposed schemes used in this paper over other related schemes is the high modularity level i.e. same hardware can encode and decode codes with different parameters therefore a generalized scheme will be achieved. The proposed scheme will eliminate multiple errors by using other schemes like the Mixed Radix MRC and BEX decoding schemes with lower complexity compared to the higher order of complexity of CRT by detecting by correcting using more consistent check. This proposed scheme in summary will be highly modular, detect and correct multiple errors, memory-less scheme (space complexity), more secured.
Encoder DaTtraawnosrdm(kis-bsits) ion
Generator Code word (n-bits)
DaTtraawnosrdm(ki-sbsitis) on
Generator Code word (n-bits) Unreliable Transmission Unreliable Transmission
Decoder DatTarwaonrds m(k-ibsists) ion Extract & Correct
Checker Code word (n-bits)
on Extract & Correct
Checker Code word (n-bits) The content of this paper is organized as follows: Section 2 reviews existing related works are presented, also introducing the fundamental mathematical model of RNS and RRNS. Section 3 describes the decoding alternative techniques of error correction and detection using RRNS and the description of the proposed algorithm is given in section 4. Section 5, Results, Discussions and comparison with representative examples showing the implementation of algorithm. Section.6 conclusion.
[
Residue Number System: Residue number system is a technique
in which an integer is represented by a set of remainders that are
obtained after the modulo division by a set of relatively prime
moduli. The process of converting a weighted number system to
residue format is called RNS encoding [
∏
Then integer X can be represented as a set of w remainders (r1,
r2... rw) where ri = X (mod mi) (2)
The dynamic range of the RNS is given by M and the set [0,M
1] gives the legitimate range such that all integers in this range can
be represented as residues by this set of moduli[
Redundant Residue Number System: Redundant Residue Number System is achieved by adding some redundancy to the Residue Number System. RRNS helps in both error correction and error detection. By adding (u - w) redundant moduli (mw+l, mw+2... mw) to the v information moduli (ml, m2... mw), a RRNS (u,w) code can be generated. This process is called RRNS encoding. Thus an integer X is represented in the RRNS form as
X= {r1, r2…..rw, rw+1 …ru} (4) Where (m1' m2, ..., mw) are called information moduli and (mw+I' mw+2, ..., mw) are called redundant moduli. Similarly (r1, r2, ..., rw) are called information residues and (rw+l' rw+2, ..., rw) are called redundant residues. Mr denotes the product of redundant moduli. In RRNS, the legitimate range is defined as [0, M] and illegitimate range indicating overflow, where residues are obtained using redundant moduli, is [M, M Mr ].
For RRNS, even if we remove some of the redundant residues, an
integer can be recovered if the retained residue digits are correct.
Theorem 1: RRNS (u - w, v) code has a detection capability of (u
- w - v) errors and an error correction capability of (u - w - v) /2
[
∑ where kb = log2Mr and kbj = log2mjl, where mj, (j = 1,2 ... u) are the moduli. By varying the number of redundant bits that are transmitted, the code rate and error correction capability are varied. Redundancy is added to the information/data, therefore the code rate decreases and error correction property is improved. In RNS, the number of non-zero elements in a vector is defined as its hamming weight. Let Xi and Xj are two code vectors, then hamming distance d (Xi, Xj) is defined as the number of bits in which two code vectors Xi and Xj differ. Minimum distance, d is the minimum of hamming distances
d = min (d (xi,x j);xi ≠ Xj). (6) Theorem 2: The minimum hamming distance d of an RRNS (u,w)code is defined as d = u - w + 1, provided (ml < m2 < ... < mw < mw+l < ... < mu).
Theorem 3: For a redundant residue number system, the error
detecting capability, c = d - 1 and the error correcting capability
[
In the course of converting back the received residues into the integers the decoding algorithms are used. Two decoding algorithms, CRT and MRC can be used. For CRT, we have ∑
where Mi = M/mi and Ti is the multiplicative inverse of Mi which can be calculated as
Ti Mi = 1 mod mi (8)
This can be simplified as Ti Mi _
This study will be limited to the MRC because the real time
implementation of CRT is not possible because it involves a
modular operation with large integer M which results in a
complexity of O (n3). To avoid the computations with such larger
M, the CRT satisfies the real-time signal processing due to its
parallel means of computation and there is a constant limit to this
(9)
approach[
∏ Where ai are the mixed radix system coefficients and are determined sequentially in the following manner. Locating the residue digit error is more time- consuming than correcting the residue digit error. This process dictates the overall delay of an error detection and correction algorithm.
RRNS codes can be used for error detection and correction in both information residues and redundant residues.
Theorem 4: The redundant residue number system can correct any single residue error if it satisfies the following two conditions[l]: 1) R > mwmw-1 2) min (R/mw+i) ≠ mw 1 ≤ j≤ r where R = mw+1mw+2 ...m w+r and r ≥ 2.
Consider that a set of residues |X|'mi, are transmitted and received sequence are |X|’mi, where i = 1, 2,… u. With the help of W received information residues, redundant residues (|X|”mw+l ,|X|”mw+2,···,|X|”mu) can be computed using base extension method.
Define this procedure is called as consistency checking which forms the basis of error correction algorithm described in this paper.
BEX is given as enlargement of the original base ∏
∏
Theorem 5: If any one of the residue is in error, then one of the
following cases can occur[
Case 2: If only one of the element in this set (|∆|mw+r' ...,|∆|mw+1) is non-zero, then |X|’mz is wrong and this can be corrected by replacing with |X|”mz.
Case 3: If more than one element in this set (|∆|mw+r, ... , |∆|mw+l) is non-zero, then any one of the information residue is in error and all the redundant residues are correct. The above theorem helps in the detection of a single residue error and helps to identify whether the detected error is in information residue or in redundant residue. Theorem 6: If one of the residues in the set (|X|’m1, |X|’m2, ... , |X|mw_2j) is in error, then one of the following cases can occur[I]. Case 1: If the residue |X|’mz, 1≤ z ≤ w -2j -2, is in error, then |∆|mw-2j and |∆|mw-2j-l are non-zero.
Case 2: If |X|’mw-2j-1 is in error, then |∆|mw-2j-l is non-zero and |∆|mw-2j is zero. Error can be corrected by replacing it with |X|" .. mw-2j-l Case 3: If |X|’mw-2j is in error, then |∆|mw-2j is non-zero and |∆|mw2j-l is zero.
Error can be corrected by replacing it with |X|”mw-2j. This
theorem helps in finding the location of multiple residue error.
This paper describes a multiple error correction algorithm which is
based on the above theorem proposed by [
1.
Decode information into the information residue digits and redundant residue digits using both information and redundant moduli sets.
Compute the mixed radix digit for the information residue digit with respect to information moduli set. Compute the consistent check respectively to detect erroneous digit & location. If d1=d2=d3=0 , there is no error, goto stop Else Correct the error by substituting two error free residues from the information moduli and from the redundant residue.
Perform consistent check ,IF=Ai(s) = Ai(r)=0 goto Stop Else repeat step 2
Illustrative Example: Suppose given the moduli set {7, 9, 11, 13, 17, 19, 23, 25, 29} where {7, 9, 11} are the information moduli and {13, 17, 19, 23, 25, 29} are the redundant moduli. Therefore, Mu = 693, Mw= 4,199 and MV=16,675. Since the number of redundant moduli is 6, this RRNS is capable of correcting three residue digit errors. Let the error free residue representation be X = 246 (1, 3, 4, 12, 8, 18, 16, 21, 14). Consider if due to error three residue digit errors were introduced into the received codeword which changed to {1,5,4,12,8,5,0,21,14} Here we consider the first three codeword for decoding.
Step 1: Using MRC The received codeword is decoded as XU(154)=554 , Xw(12,8,5)=2456 and Xv=(0,21,14)=10396. Step 2: Perform Consistent check to respectively to detect erroneous digit & location. If d1=d2=d3=0, there is no error, goto stop |554|7=1 =1 yes |554|9=5=3=no |554|11=4=4=yes |2456|13=12=12=yes |2456|17=8=8=yes,|2456|19=18=5=no |10396|23=16=0=no, |10396|25=21=21=yes, |10396|29=14=14 yes. Step 3: Since non-zeros occurred, error has occurred in both the information residue and redundant residue. Using base extension method, we can now find redundant residue since in the information moduli m2, m6 for redundant moduli and m7 are the error channel. Now we take m1, m3, m4, m5, m2 using base extension, to decode the residue for m2 in the information moduli to replace corrected residue with the error residue respectively for each channel. We then have |X|”9=3 |X|”19=18 and |X|”23=16. So therefore we can conclude that the received codeword has been corrected for each channel.
Step 4: Perform consistent check, IF=Ai(s) = Ai(r) =0 goto Stop Else repeat step 2 So for |∆|9 =|3-3|9 = 0 , |∆|19= |18-18|19= 0 |∆|19= |16-16|23= 0 since all |∆|9,19,23 equals zero respectively then error is corrected 5.1
The numbers of detectable and correctable residue digit errors are governed by the number of redundant moduli. i.e. with r redundant moduli , RRNS is capable of detecting r and correcting| r/2|.Eliminating look-up table by performing more consistent check. Decoding using CRT requires large compute intensive modulo operation. Legitimate range represents useful computational range while illegitimate range is useful for error and overflow detection. Our algorithm uses MRC which are smaller and needs to be performed sequentially therefore from the first decoding. Comparison of Multiple Residue Digit Error Detection and correction Algorithms can easily identify if error is in a channel.
The algorithm applies base extension and MRC to detect, locate and correct error by eliminating table- look up, therefore the scheme provides a memory less based scheme. Locating error is usually time consuming in most algorithm, but in our algorithm, it uses a pipelining approach to breakdown the problem with a level of complexity O(n) after decoding and performing consistent checks on all the residue, these can be achieved for hardware design we can tell which channel the error has occurred. So therefore we believe the overall delay will be lesser. The proposed algorithm corrected multiple errors, performs double consistent check because distortion can occur either from the information residue or a redundant residue. Consequently with this property any residue can be restored belonging to the legitimate range of either the information residue or redundant residue, but we believe the decoding time can be improved upon but will eliminate total error, therefore O≤X<M is satisfied. The proposed algorithm will be more efficient for hardware implementation due to the less complexity in using MRC O(n) and size of modulo operation. Detect Error Syndrome Locate Error No y r o m e
M Yes No tup ian t uO odm Residue Residue
Residue A new multiple residue digit error detection and correction algorithm in RRNS is presented. I t requires a small a n d fixed number of computations with no table look-up compared to other existing algorithm. The hardware implementation of an RNS based application is greatly dependent on the chosen moduli set. The theoretical implementation of the proposed algorithm in this study is explained only with illustrative examples. The advantages of RNS encoding is fast computational blocks , carry free and parallel operations are possible which helps in developing fast digital signal processing(DSP) processors which is the aim of parallel computation. The outcome of this research, which will provide the following expected contributions amongst others: 1. Capability to understand and reason about error detection and correction, and the ability to withstand faults as communication circuits are stochastic in nature and may fail. The ability to cope up with fault will be driven from the parallelisms property of RNS, as a error that occur in one channel will not affect the other channels. 2. The speed of the communication channel will tremendously be increased due to the carry-free property of RNS. 3. Congestion in the communication channel will be reduced as partial representation of actual data will be transmitted, therefore reducing the data traffic in the communication channel. This will increase the general throughput of the communication system. 4. There will be a reduction in energy and memory consumption. 5. Generally the quality of service is expected to improve.