The article develops an e cient implementation of an algorithm for detecting and correcting multivalued residual errors with a xed number of calculations of the syndrome, regardless of the set of moduli size. Criteria for uniqueness are given that can be met by selecting moduli from a set of primes to satisfy the desired error correction capability. An extended version of the algorithm with an increase in the number of syndromes depending on the number of information moduli is proposed. It is proposed to remove the restriction imposed on the size of redundant moduli. Identifying the location of the error and nding the error vector requires only look-up tables and does not require arithmetic operations. In order to minimize the excess space, an extended algorithm is also proposed in which the number of syndromes and look-up tables increases with the number of information moduli, but the locations of errors can still be identi ed without requiring iterative computations. By using the approximate method, we have reduced the computational complexity of the algorithm for calculating the syndrome from quadratic to linear-logarithmic, depending on the number of bits in the dynamic range.
Redundant residue number system (RRNS) error detection and correction has been used in several fault tolerant applications described in the literature [1]-[9]. In addition to correcting errors, a range over ow can be detected by adding two redundant moduli. RRNS has also been used to develop a fault-tolerant convolution algorithm that is well suited for implementation on multiprocessor systems [10, 8]. Using the long division method, the algorithm can detect and correct processing errors. In addition, the six-moduli RRNS based error correction code has been implemented on the hybrid storage [11, 7]. Compared to Reed-Solomon codes, this code provides a larger data storage with similar error correction capabilities [5, 6].
As a rule, the detection and correction of errors in RRNS is carried out in three sequential stages: checking for errors, identifying erroneous digits of the residue and correcting errors. Algorithms that x only one residual digit error have been proposed in [12, 13, 14, 15]. In the case of using two redundant moduli, decoding of the value and location of a single error can be solved using only one syndrome and one look-up table [15, 4]. On the other hand, detecting and correcting multiple residue digit errors is more di cult and time consuming. This is mainly due to the sheer number of combinations of di erent locations and residues to nd errors in the second step. Typically, existing multiple error detection and correction algorithms use three di erent methods to locate the erroneous residue digits. This is a consistency check using the syndrome [16, 17], number recovery according to the Chinese Remainder Theorem (CRT) [18, 19] and the modulus projections [17, 20]. These algorithms require iterative and recursive computations and comparisons that defy parallel hardware implementation.
Let's consider an approach to detecting and correcting multiple errors in RRNS [21, 3]. The digits of the RRNS residues are divided into three groups so that any combination of errors can be uniquely identi ed by one of the seven error location categories. From the obtained representation of the residue, three syndromes are deduced to detect up to 2t and correct up to t errors of the residue digits, where the number of redundant moduli is equal to 2t. Regardless of the number of moduli, the error residue representation can be unambiguously extracted by these syndromes from six look-up tables in a few steps and subtracted directly from the resulting residue digits to correct the errors. The delay is xed and does not depend on the size of the moduli set. The second criterion for the selection of modules, which imposes a large excess space, can be completely eliminated, making the number of calculations of the syndrome dependent on the number of information moduli. Compared to existing algorithms, the proposed algorithm is simpler and has a very low complexity of error decoding. Only one modulo subtraction is required for each syndrome computation. The proposed algorithm classi es various combinations of deduction errors into seven groups of locations without limiting the amount of information and redundant moduli, which is in stark contrast to the [15]algorithm, which simply nds one deduction error for RRNS with only two redundant moduli.
The rst algorithm for detecting and correcting multiple residue digits errors was introduced in [16]. The error decoding algorithm establishes the order dependence in the residue digits in such a way that it is able to correct single packet errors up to t adjacent residue digits. The syndrome computation method calculates the di erence between the received residue digits and the residue digits in extended bases. The j jpi syndroms for i = 1; 2; : : : ; k; k + 1; : : : ; k + 2t are grouped into the following sets: where k is a number of information moduli.
The location of the error of the received digits of the residue is determined by Si for i = 1; 2; : : : ; [(k + t 1) = (t + 1)] + 1, provided that the number of nonzero elements is less than or equal to t. An error-free residue representation is then constructed by replacing the erroneous residue digits with the corresponding base extended residue digits. The complexity of this algorithm depends on the number of test sets and the number of syndromes calculated for each set.
Instead of looking for erroneous residue digits in [18] another algorithm was proposed using the continued fraction method. The correct fraction of error is then used to compute the value of the error-free residue representation. Calculations of fractions are solved by a recursive Euclidean o o o o (1)
S1 S2 S3
n n n
j jpk+1 ; j jpk+2 ; : : : ; j jpk+2t j jpk t ; j jpk t+1 ; : : : ; j jpk+t 1 j jpk 2t 1 ; j jpk 2t ; : : : ; j jpk 2 . .
.
n S[(k+t 1)=(t+1)]+1
j jp1 ; j jp2 ; : : : ; j jp2t algorithm. However, this method requires more iterations for more moduli and residue digit errors, which makes this method ine ective for hardware implementation.
Sun and Krishna [17] introduced a coding theory approach to error control in RRNS and introduced the concepts of Hamming weight, minimum distance, weight distribution, and error detection and correction capabilities in RRNS. Four algorithms have been proposed, namely single error correction and multiple error detection, double error correction and multiple error detection, single batch error correction, and extended double-digit error correction. The rst three algorithms require the computation of syndromes, as in [16], except that only excess residue digits are used in the computations. Erroneous digits of residues are found by matching of all digits of errors calculated by syndromes. Although the number of computed syndromes is less than in [16], the consistency check requires iterative computations involving every possible combination of error locations. The advanced double error correction algorithm uses a di erent approach from the rst three algorithms. It uses the modulus projection concept introduced in [22] to correct residue singular errors, and is an extension of the residue singular error correction algorithm proposed in [23]. The location of erroneous residues is obtained when the value of the representation of a number after excluding two erroneous digits of the residue falls within the allowed range. The value is checked by calculating the mixed digits of the root of the representation of the residue of each projection. This process is similar to the rst three algorithms in that it requires iterative estimation of every possible combination of residue digit error locations.
In [19] two algorithms based on CRT, unambiguous coding and list decoding, were proposed for detecting and correcting small and large numbers of residue digit errors, respectively. The unambiguous encoding method is an extended version of the algorithm proposed in [18]. It looks for two unknown integers y and z of bounded size, such that jy X~ jN z, where X~ is the resulting representation of the residue, and N is the dynamic range of the RRNS. The search for y and z must be calculated recursively until z=y becomes an integer. The list decoding method searches for a sequence of integers c0; c1; : : : ; cl, of certain limited sizes from the received residue digits to form a polynomial C(x) = Pli=0 cixi of degree l such that Pli=0 cixi = 0, where l N is a function of the number of information and redundant moduli, as well as the values of the largest and smallest moduli. The error-free representation of the residue is restored by solving the polynomial for integer roots and nding their matching amplitudes with the resulting residue digits.
The error correction algorithm in [20] uses the same unit projection concept as the extended 2-digit error correction algorithm in [17], but it uses the CRT instead of the generalized weigted number system (GWNS) to compute the value of each projection. The algorithm is able to correct up to t errors in the size of the residues, ignoring the t digits of the residues from the obtained residues at each iteration of the calculation of the value. If the calculated value falls within the valid range, the ignored residue digits are invalid. The maximum number of iterations required in this algorithm is Ctn, where n is the total number of moduli. [19] also proposed an extended iteration reduction scheme based on the maximum likelihood decoding (MLD) method. It rst calculates the value of r of the residue digits, where r is the number of redundant residue digits. Only when the calculated value is within the valid range will the remaining residue digits be calculated using the radix expansion method. If t or fewer digits of the extended bases of the residue di er from the resulting digits of the residue, then the digits of the extended bases of the residue are unerring digits of the residue. The required number of iterations is [(Ctn)=(Ctr)], which is signi cantly less than in the rst method, especially when the number of modules is large.
In general, recursive or iterative computations and comparisons are required to determine erroneous residue digits for existing error detection and correction algorithms with multiple residue digits. Since the number of iterations depends on the location of bit errors, the time taken to detect and correct bit errors is non-deterministic. The worst case increases with the size of the selected set of moduli, which depends on the number of information moduli and the error correction capabilities of the algorithms. Consequently, these algorithms are not amenable to hardware implementation.
From the expression of the error vector
El =
Xt PN i=1 pli
Pli 1 pli eli pli PN
t = X a i=1
PN li pli rnPN = a
PN Qit=1 pli = a n t
Y j=1;lj6=li plj (2) El is a multiple of the product of error-free moduli. When pk+2; : : : ; pk+r > pi, 8i k and t [r=2], the minimum di erence between the values of any two vectors of errors is always more than PK . Beginning with X < PK , a misrepresentation of the residue can be detected by checking if X0 falls within the invalid range. However, decoding X0 from (x01; x02; : : : ; x0n) using CRT requires large computational operations modulo PN . Once errors have been found, the location of the erroneous residues must be located before they can be corrected. Typically, locating the erroneous residues requires time-consuming iterative computations that increase with the size of the selected set of moduli. To overcome the above disadvantages, this section proposes a new method for calculating the syndrome. It uses smaller modulo operations and the number of computations is xed regardless of the size of the set of moduli. 3.1. Segregation of syndromes for identi cation of errors The value of El is limited to PN . Thus, each error vector corresponds to a unique El. Considering the value of the El error, it is possible to uniquely determine the corresponding error digits eli and the location of the li error. Unfortunately, El cannot be obtained by directly decoding the representation of the residue (x01; x02; : : : ; x0n), since X is unknown.
To avoid the use of large error decoding operations modulo PN , n residue digits (x01; x02; : : : ; x0n) X are divided into three di erent groups, (x01; x02; : : : ; x0n), x0k+1; x0k+2; : : : ; x0k+t pk+1; pk+2; : : : ; pk+r > pi, 8i and x0k+t+1; x0k+t+2; : : : ; x0k+r , so that the modulo operations required to unambiguously resolve the error vector are about three times less than PN .
The dynamic range PN of RRNS np1; p2; : : : ; pk; pk+1; : : : ; p(k + r)o, where k can be divided into
k PN = Y pi i=1 k+r
Y pi = PK i=k+1
PU
PV (3) where PK = Qik=1 pi is a product of information moduli, PU = Qik=+kt+1 pi is a product of the rst t redundant moduli, and PV = Qik=+kr+t+1 pi is the product of the remaining t redundant moduli.
For convenience, we de ne the following notation:
X denotes the value of error-free representation of RRNS (x1; x2; : : : ; xk; xk+1; : : : ; xk+r). X falls within the range [0; PK 1].
X~ denotes the value of the resulting representation of the RRNS (x~1; x~2; : : : ; x~k; x~k+1; : : : ; x~k+r). X~ falls within the range [0; PN 1].
X~K , X~U and X~V denote the values of the RNS representations for information moduli, for the rst t redundant moduli, for the remaining t redundant moduli respectively, that is X~K (x~1; x~2; : : : ; x~k), X~U (x~k+1; x~k+2; : : : ; x~k+t) and X~V (x~k+t+1; x~k+t+2; : : : ; x~k+r). X~ , X~K , X~U and X~V may be erroneous or non-erroneous.
~ XK ~ XU ~ XV = = = ~ X ~ X ~ X
PK PU
PV ~ XK ~ XU ~ XV = jXjPK = X = jXjPU = X =
jXjPV
If there is no error, X~ = X. Based on the formulas (4) { (6), 6 It should be noted that (8) is valid if and only if PU > PK , and PU and PK are coprime.
Otherwise, if there is erroneous residue digit(s) in one or more groups among (x~1; x~2; : : : ; x~k), (x~k+1; x~k+2; : : : ; x~k+t) and (x~k+t+1; x~k+t+2; : : : ; x~k+r), X~ can be expressed as X~ = X + E, that is,
EK , EU and EV denote the values of the error digits located in the information channels of the moduli, in the rst t of the redundant channels of the moduli, and in the remaining t of the redundant channels of the moduli, that is, EK (ek1 ; ek2 ; : : : ; eki ; 0; : : : ; 0), EU 0; : : : ; 0; eu1 ; eu2 ; : : : ; euj ; 0; : : : ; 0 and EV (0; : : : ; 0; ev1 ; ev2 ; : : : ; evl ), where (k1; k2; : : : ; ki), (u1; u2; : : : ; uj ) and (v1; v2; : : : ; vl) represent the positions of the error digits and i; j; l t. EK , EU and EV are limited by PN and can be computed from their respective error digits using the formula (2).
Based on the above notation, X~K , X~U and X~V can be expressed in terms of X~ through (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) where ~ XK = jX + EK jPK ~ XU = jX + EU jPU ~ XV = jX + EV jPV = = =
X + jEK jPK jXV jPV + jEV jPV
V PV K = U = ( 0; if
1; if ( 0; if 1; if
X + jEK jPK < PK X + jEK jPK PK X + jEU jPU < PU
X + jEU jPU PU V = ( 0; if jXV jPV + jEV jPV < PK
1; if jXV jPV + jEV jPV PK
Since the resulting residue digits are grouped into three di erent groups, erroneous residue digits may exist in one of the following categories depending on their error location.
EL1: erroneous digit(s) of the residue only in X~K .
EL2: erroneous digit(s) of the residue only in X~U .
EL3: erroneous digit(s) of the residue only in X~V .
EL4: erroneous digits of the residue in X~K and X~U .
EL5: erroneous digits of the residue in X~K and X~V .
EL6: erroneous digits of the residue in X~U and X~V .
EL7: erroneous digits of the residue in X~K , X~U and X~V .
In principle, the presence of any t remaining errors in the numbers of n residues can be detected by two syndromes, 1 and 2. 1 is calculated from (x01; x02; : : : ; x0n) and x0k+1; x0k+2; : : : ; x0k+t , 2 is calculated from (x01; x02; : : : ; x0n) and x0k+t+1; x0k+t+2; : : : ; x0k+r . Each of these syndrome computations includes the residue digits (k + t). Since the dynamic ranges of 1 and 2 are much smaller than PN , each syndrome value can be displayed in more than one error vector with no more than t remaining digits in di erent li locations and eli values. Therefore, the two syndromes are not enough to correct the errors entered in the three di erent groups of residual digits. The third syndrome 3, calculated from x0k+1; x0k+2; : : : ; x0k+t and x0k+t+1; x0k+t+2; : : : ; x0k+r , is required. Having found the common vector of errors, represented by three syndromes, it is possible to accurately determine the errors of the residue digit, provided that PU > PK .
Three syndroms 1, 2 and 3 can be calculated as follows: (16) (17) (18) (19) (20) (21) (22) (23) (24) Replacing (7)-(9) with (16)-(18), we get
2 = jXjPV 3 = jXjPV
X X
PV PV Therefore, when there is no erroneous residue digit, the syndromes are 1 = 2 = 3 = 0.
If any digit of the residue contains an error, then the values of the three syndromes can also be used to determine the category of the place of the error. Replacing (10)-(12) with (16)-(18), the values 1, 2 and 3 for each possible error location category can be calculated as follows: EL1: 3 = jXjPV
X + jEU jPU U PU PU
2 = jXjPV X PV X + jEU jPU U PU PV = jEU jPU = 0 = U PU
jEU jPU PU 1 = jX 2 = jXjPV X + jEV jPV 3 = jXjPV + jEV jPV V PV
V PV PV
X PV = 0 = jEV jPV = jEV jPV 1 =
= 2 = 3 = 1 = 2 =
= 3 =
X + jEU jPU U PU jjjEXXUjjPPjPVVU jXXEK++jPjjEEKUK+jjPPUKK PKUKPPUPUK PPVV ==
X + jEK jPK
K PK PU = K PK U PU
jEK jPK PV jEU jPU PV X X + jEK jPK
jXjPV + jEV jPV jEV jPV jEK jPK + K PK PV jXjPV + jEV jPV V PV
K PK PU = K PK V PV X + jEK jPK jEK jPK PK
K PK PV =
X PV = jEV jPV
X + jEU jPU U PU jXjPV X + jEV jPV
jXjPV + jEV jPV V PV jEV jPV jEU jPU + U PU PU
X PU = jEU jPU V PV PV = jEV jPV
X + jEU jPU
U PU PV = (39) 1 =
U PU
K PK jEU jPU
jEK jPK + jXjPV + jEV jPV jEV jPV
jEK jPK + jXjPV + jEV jPV jEV jPV jEU jPU +
K PK PU V PV K PK PK V PV U PU PU
X + jEK jPK 3.2. Error detection and correction From (22)-(42) there are nine di erent syndrome expressions, and each syndrome can take three of these nine expressions, as shown in table 1. v3 = jEU jPU
jEU jPU PU v9 = jEV jPV jEU jPU +
U PU PV
EK
Table 2 shows the mapping of error location categories to expressions of the three syndromes. Each syndrome value in the column must match an error vector in the column error location category, and each error vector in the error location category must also map to at least one of the three syndrome values in the column.
Six look-up tables are built from tables 1 and 2. In each look-up table, the values for the error vectors are precomputed and stored along with their error vectors. If the look-up key in the look-up table matches the look-up value, the error vectors that match the look-up value will be retrieved. Table 3 shows the types of (EK ; EU ; EV ) errors corresponding to error vectors stored in each look-up table, look-up values (computed from v1 to v9) and a search key ( 1, 2 or 3), used to identify error location categories (EL1-EL7), and search for error vectors. For example, from the rst row of the table 3 we can conclude that T1 was created to extract the error vector EK for EL1, EL4 and EL5. The search values v2 and v4 for T1 are calculated for all possible combinations of K 2 f0; 1g and EK for t or less residue digit errors. If an error is identi ed as being in EL1 or EL5 (or EL1 or EL4), its error vector EK can be extracted from T1 using the 1 syndrome (or 2). The exact error vector is recovered in two stages. The error location category must be identi ed before the corresponding error vector extracted from the look-up table is used to correct the erroneous digits of the residues.
If only one of the three syndromes is zero, as indicated in table 2, the error location category can be identi ed by syndrome zero. This is EL1 for 3 = 0, EL2 for 2 = 0 and EL3 for 1 = 0. The error vectors for EL1, EL2, and EL3 can be obtained from look-up tables T1, T2 and T3 respectively, using either of the two nonzero syndromes. If none of the syndromes is zero, the error location category can be EL4, EL5, EL6, or EL7, as indicated in table 2. In this case, the actual category of the error location can be determined by checking the consistency of the error vectors received by 1, 2 and 3, according to the table 3. For example, since EKV = EK [ EV , if errors fall into EL5, the error vector EKV , obtained from T5 on 2, must include the error vectors EK and EV , obtained from T1 and T3 on 1 and 3 respectively. After locating the actual error location category, the erroneous residue digits are corrected by subtracting the resulting error vector from the resulting residue digits.
Let E = nd (T; ) be the table look-up function that returns the error vector E for the look-up key into the look-up table T or zero if the corresponding record is not found. Steps required to detect and correct errors with multiple residue digits: Step 1. Decode X~K , X~U amd X~V from the obtained residue digits.
Step 2. Calculate 1, 2 and 3 by (19), (20) and (21) respectively.
Step 3. If 1 = 2 = 3, then there is no error, go to step 10.
Step 4. If only one of 1, 2 and 3 is not zero, then there are more than t residue digit errors. Go to step 10. .
Step 5. If 1 6= 0, 2 6= 0 and 3 = 0, then the erroneous digit(s) of the residue are in the EL1. EEL1 = nd (T1; 2). Subtract the error vector EEL1 from the obtained residue digit to correct the error. Go to step 10.
Step 6. If 1 6= 0, 2 = 0 and 3 6= 0, then the erroneous digit(s) of the residue are in the EL2. EEL2 = nd (T2; 1). Subtract the error vector EEL2 from the obtained residue digit to correct the error. Go to step 10.
Step 7. If 1 = 0, 2 6= 0 and 3 6= 0, then the erroneous digit(s) of the residue are in the EL3. EEL3 = nd (T3; 2; or 3). Subtract the error vector EEL3 from the obtained residue digit to correct the error. Go to step 10.
Step 8. If 1 6= 0, 2 6= 0 and 3 6= 0, the erroneous residue digits can be in EL4, EL5, EL6 or EL7. The exact category of the error location is de ned as follows: Step 8.1 If EEL4 = E = EEL4.
Step 8.2 If EEL5 = E = EEL5.
Step 8.3 If EEL6 = E = EEL6.
nd (T4; 1) = nd (T1; 2) [
nd (T2; 3) 6= 0, then the error is in EL4. Set nd (T5; 2) = nd (T1; 1) [
nd (T3; 3) 6= 0, then the error is in EL5. Set nd (T6; 3) = nd (T2; 1) [ nd (T3; 2) 6= 0, then the error is in EL6. Set Step 8.4 If we nd nd (T4; 1) \ nd (T5; 2) 6= 0 or nd (T4; 1) \ nd (T6; 3) 6= 0, then the error is in EL7. Set E = EEL7 = nd (T4; 1) [ nd (T5; 2) Step 9. If no or more error location categories are found, then there are more than t residue digits errors. Go to step 10. Otherwise, subtract the error vector E from the resulting residue digit(s) to correct the erroneous reside digit.
Step 10. Complete the procedure.
In step 8, each look-up table is accessed by no more than three di erent syndromes. The same syndrome can be accessed simultaneously by di erent look-up tables, but di erent syndromes cannot access the same look-up table at the same time. Thus, the search for the error vector can be completed in no more than three search cycles. As the search key in the search for these tables are three syndromes PU size and PV , size and speed of access to the look-up table are dependent on the number and size of RRNS moduli. This problem can be solved using multi-level look-up table with a smaller width of the input address and less complex addresses decoding schemes. However, the algorithm for calculating the syndrome has a quadratic computational complexity of the number of digits in the working range. To reduce the subtractive complexity of calculating syndromes, we propose to use an approximate method.
To calculate the residue of the division in the method described in paragraph 3, we use an approximate method that allows implementing this operation absolutely correctly.
The essence of the approximate method is based on the use of the relative value of the analyzed numbers to the full range de ned by the Chinese remainder theorem, which connects the positional number X with its representation in the residues (x1; x2; : : : ; xn), where Xi is the X =
Xn P i=1 pi
P 1 i pi xi
P pi X P
n = X i=1
P 1 i pi pi xi 1 xi X ki 1 (43) (44) where P = Qin=1 pi, pi are the RNS moduli, P 1 i is a multiplicative inversion with respect to pi, and Pi = pPi = p1p2 pn.
If the left and right sides of the expression (43) are divided by the constant P , corresponding to the range of numbers, then we get an approximate value smallest non-negative residues of a number in relation to to the moduli of the residue number system p1; p2; : : : ; pn by the following expression where ki = jPi 1jpi are the constants of the selected system, and xi are the digits of the number pi presented in the RNS, while the value of each sum is in the range [0; 1). The nal result of the sum is determined after summing and discarding the integer part of the number, keeping the fractional part of the sum. The fractional part can also be written as X mod 1, because X = bXc + X mod 1. The number of digits of the fractional part of a number is determined by the maximum possible di erence between adjacent numbers. If it is necessary to perform an exact comparison, we need to calculate the value (44), which is the equivalent of converting from RNS to weighted number system. To solve the tasks, it is enough to know approximately the value of the used number X in relation to the dynamic range P , which is performed quite simply, but at the same time the ratio X = P , X < P or X > P is correctly determined.
The use of the approximate method makes it possible to replace the computationally complex operation of nding the residue of the division by the range of the system by taking the least signi cant bits of the number, which makes it possible to reduce the computational complexity from quadratic to linear-logarithmic complexity.
The paper presents an e cient modi cation of the algorithm for detecting and correcting multiple residue errors with a xed number of calculations of the syndrome, regardless of the size of the set of moduli, using an approximate method. The proposed modi cation allows reducing the computational complexity of the algorithm for calculating the syndrome from quadratic to linear-logarithmic.
The criteria for uniqueness can be met by selecting moduli from a set of primes to satisfy the desired error correction capability. An extended version of this algorithm with an increase in the number of syndromes depending on the number of information moduli was also proposed to remove the limitation imposed on the size of redundant moduli.
Identifying the location of the error and nding the error vector requires only look-up tables and does not require arithmetic operations. In order to minimize the excess space, an extended algorithm is also proposed in which the number of syndromes and look-up tables increases with the number of information units, but the locations of errors can still be identi ed without requiring iterative computations.
Acknowledgements The reported study was funded by RFBR, Sirius University of Science and Technology, JSC Russian Railways and Educational Fund "Talent and success", project number 20-37-51004, and Russian Federation President Grant MK-24.2020.9, and SP3149.2019.5