Efficient implementation of error correction codes in modular code Nikolay Kucherov1,2† , Viktor Kuchukov1,2‡‡ , Elena Golimblevskaia1,2‡ , Natalia Kuchukova1†† , Irina Vashchenko1†‡ and Ekaterina Kuchukova1,‡† 1 North-Caucasus Center for Mathematical Research, North-Caucasus Federal University, 1, Pushkin Street, 355017, Stavropol, Russia 2 Sirius University of Science and Technology, 1, Olympic Ave, 354340, Sochi, Russia E-mail: † nkucherov@ncfu.ru, ‡‡ vkuchukov@ncfu.ru, ‡ elena.golimblevskaya@gmail.ru, †† nkuchukova@ncfu.ru, †‡ irishechka.26@mail.ru, ‡† ekuchukova@ncfu.ru Abstract. The article develops an efficient implementation of an algorithm for detecting and correcting multivalued residual errors with a fixed 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 finding 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 identified 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. 1. Introduction 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 overflow 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 fix 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 Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 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 difficult and time consuming. This is mainly due to the sheer number of combinations of different locations and residues to find errors in the second step. Typically, existing multiple error detection and correction algorithms use three different 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. 2. Projection method 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 identified 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 fixed 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 classifies 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 finds one deduction error for RRNS with only two redundant moduli. The first 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 difference between the received residue digits and the residue digits in extended bases. The |∆|pi syndroms for i = 1, 2, . . . , k, k + 1, . . . , k + 2t are grouped into the following sets: n o S1 ≡ |∆|pk+1 , |∆|pk+2 , . . . , |∆|pk+2t n o S2 ≡ |∆|pk−t , |∆|pk−t+1 , . . . , |∆|pk+t−1 n o S3 ≡ |∆|pk−2t−1 , |∆|pk−2t , . . . , |∆|pk−2 (1) .. n . o S[(k+t−1)/(t+1)]+1 ≡ |∆|p1 , |∆|p2 , . . . , |∆|p2 t 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 algorithm. However, this method requires more iterations for more moduli and residue digit errors, which makes this method ineffective 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 first 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 different approach from the first 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 first 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 |y · X̃|N ≡ 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) = li=0 ci xi of degree l such that P Pl i i=0 ci x N = 0, where l 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 finding 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 first 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 differ 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 significantly less than in the first 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. 3. Syndrome method From the expression of the error vector t t n−t PN PN PN Pl−1 X X Y El = eli = ali − rn PN = a Qt =a plj (2) p i=1 li i pli p li P i=1 pli i=1 pli j=1,l 6=l N j i El is a multiple of the product of error-free moduli. When pk+2 , . . . , pk+r > pi , ∀i ≤ k and t ≤ [r/2], the minimum difference 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 X 0 falls within the invalid range. However, decoding X 0 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 fixed regardless of the size of the set of moduli. 3.1. Segregation of syndromes for identification 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 different groups, (x01 , x02 , . . . , x0n ), x0k+1 , x0k+2 , . . . , x0k+t   and x0k+t+1 , x0k+t+2 , . . . , x0k+r , so that the modulo operations required to unambiguously resolve the error vector are about three n times less than PN . o The dynamic range PN of RRNS p1 , p2 , . . . , pk , pk+1 , . . . , p( k + r) , where pk+1 , pk+2 , . . . , pk+r > pi , ∀i ≤ k can be divided into k Y k+r Y PN = pi × pi = PK × PU × PV (3) i=1 i=k+1 k+t where PK = ki=1 pi is a product of information moduli, PU = i=k+1 Q Q pi is a product of the first Qk+r t redundant moduli, and PV = i=k+t+1 pi is the product of the remaining t redundant moduli. For convenience, we define 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 first 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. EK , EU and EV denote the values of the error digits located in the information channels of the moduli, in the first 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 X̃K = X̃ (4) PK X̃U = X̃ (5) PU X̃V = X̃ (6) PV If there is no error, X̃ = X. Based on the formulas (4) – (6), X̃K = |X|PK = X (7) X̃U = |X|PU = X (8) X̃V = |X|PV (9) 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, X̃K = |X + EK |PK = X + |EK |PK − αK PK (10) X̃U = |X + EU |PU = X + |EU |PU − αU PU (11) X̃V = |X + EV |PV = |XV |PV + |EV |PV − αV PV (12) where ( 0, if X + |EK |PK < PK αK = (13) 1, if X + |EK |PK ≥ PK ( 0, if X + |EU |PU < PU αU = (14) 1, if X + |EU |PU ≥ PU ( 0, if |XV |PV + |EV |PV < PK αV = (15) 1, if |XV |PV + |EV |PV ≥ PK Since the resulting residue digits are grouped into three different 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 different li locations and eli values. Therefore, the two syndromes are not enough to correct the errors entered  in the three different 0 groups of residual digits. The third syndrome δ3 , calculated from xk+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: δ1 = X̃U + X̃K (16) PU δ2 = X̃V + X̃K (17) PV δ3 = X̃V + X̃U (18) PV Replacing (7)-(9) with (16)-(18), we get δ1 = |X − X|PU = 0 (19) X   δ2 = |X|PV − X = − PV =0 (20) PV PV PV δ3 = |X|PV − X = 0 (21) 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:   δ1 = X − X + |EK |PK − αK PK = αK PK − |EK |PK (22) PU PU   δ2 = X − X + |EK |PV − αK PK = αK PK − |EK |PK (23) PU PV δ3 = |X|PV − X = 0 (24) PV EL2:   δ1 = X − X + |EU |PU − αU PU = |EU |PU (25) PU δ2 = |X|PV − X = 0 (26) PV   δ3 = |X|PV − X + |EU |PU − αU PU = αU PU − |EU |PU (27) PV PU EL3: δ1 = |X − X|PU = 0 (28)   δ2 = |X|PV − X + |EV |PV − αV PV = |EV |PV (29) PV   δ3 = |X|PV + |EV |PV − αV PV − X = |EV |PV (30) PV EL4:     δ1 = X + |EU |PU − αU PU − X + |EK |PK − αK PK = PU = |EU |PU − |EK |PK + αK PK (31) PU   δ2 = |X|PV − X + |EK |PK − αK PK = αK PK − |EK |PK (32) PV PV   δ3 = |X|PV − X + |EU |PU − αU PU = αU PU − |EU |PU (33) PV PV EL5:   δ1 = X − X + |EK |PK − αK PK = αK PK − |EK |PK (34) PU P    K δ2 = |X|PV + |EV |PV − αV PV − X + |EK |PK − αK PK = PV = |EV |PV − |EK |PK + αK PK (35) P   V δ3 = |X|PV + |EV |PV − αV PV − X = |EV |PV (36) PV EL6:   δ1 = X + |EU |PU − αU PU − X = |EU |PU (37) PU   δ2 = |X|PV − X + |EV |PV − αV PV = |EV |PV (38) PV     δ3 = |X|PV + |EV |PV − αV PV − X + |EU |PU − αU PU = PV = |EV |PV − |EU |PU + αU PU (39) PU EL7:     δ1 = X + |EU |PU − αU PU − X + |EK |PK − αK PK = PU = |EU |PU − |EK |PK + αK PK (40) P   U  δ2 = |X|PV + |EV |PV − αV PV − X + |EK |PK − αK PK = PV = |EV |PV − |EK |PK + αK PK (41) P   K  δ3 = |X|PV + |EV |PV − αV PV − X + |EU |PU − αU PU = PV = |EV |PV − |EU |PU + αU PU (42) PU 3.2. Error detection and correction From (22)-(42) there are nine different syndrome expressions, and each syndrome can take three of these nine expressions, as shown in table 1. Table 1. Possible syndrome expressions for error location categories EL1-EL7 δ Matching values Error vectors Categories EK EU EV v1 = |EU |PU − |EK |PK + αK PK + + EL4, EL7 PU δ1 v2 = αK PK − |EK |PK + EL1, EL5 PU v3 = |EU |PU + EL2, EL6 v4 = αK PK − |EK |PK + EL1, EL4 PV δ2 v5 = |EV |PV − |EK |PK + αK PK + + EL5, EL7 PV v6 = |EV |PV + EL3, EL6 v7 = αU PU − |EU |PU + EL2, EL4 PU δ3 v8 = |EV |PV + EL3, EL5 v9 = |EV |PV − |EU |PU + αU PU + + EL6, EL7 PV 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 first 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 Table 2. Mapping error location categories to syndromes EL1 EL2 EL3 EL4 EL5 EL6 EL7 δ1 v1 v3 0 v1 v2 v3 v1 δ2 v4 0 v6 v4 v5 v6 v5 δ3 0 v7 v8 v7 v8 v9 v9 all possible combinations of αK ∈ {0, 1} and EK for t or less residue digit errors. If an error is identified 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 identified before the corresponding error vector extracted from the look-up table is used to correct the erroneous digits of the residues. Table 3. Characteristics of look-up tables for searching error vectors Table Error vectors Value Key Groups of location EK EU EV substitutions searching errors T1 + v2 δ1 EL1, EL5 T1 + v4 δ2 EL1, EL5 T2 + v3 δ1 EL2, EL6 T2 + v7 δ3 EL2, EL4 T3 + v6 δ2 EL3, EL6 T3 + v8 δ3 EL3, EL5 T4 + + v1 δ1 EL4, EL7 T5 + + v5 δ2 EL5, EL7 T6 + + v9 δ3 EL6, EL7 If only one of the three syndromes is zero, as indicated in table 2, the error location category can be identified 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 = find (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 = find (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 = find (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 = find (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 defined as follows: Step 8.1 If EEL4 = find (T4 , δ1 ) = find (T1 , δ2 ) ∪ find (T2 , δ3 ) 6= 0, then the error is in EL4. Set E = EEL4 . Step 8.2 If EEL5 = find (T5 , δ2 ) = find (T1 , δ1 ) ∪ find (T3 , δ3 ) 6= 0, then the error is in EL5. Set E = EEL5 . Step 8.3 If EEL6 = find (T6 , δ3 ) = find (T2 , δ1 ) ∪ find (T3 , δ2 ) 6= 0, then the error is in EL6. Set E = EEL6 . Step 8.4 If we find find (T4 , δ1 ) ∩ find (T5 , δ2 ) 6= 0 or find (T4 , δ1 ) ∩ find (T6 , δ3 ) 6= 0, then the error is in EL7. Set E = EEL7 = find (T4 , δ1 ) ∪ find (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 different syndromes. The same syndrome can be accessed simultaneously by different look-up tables, but different 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. 4. An approximate method for determining the positional characteristic of a number 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 defined by the Chinese remainder theorem, which connects the positional number X with its representation in the residues (x1 , x2 , . . . , xn ), where Xi is the 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 n P Pi−1 X X= xi (43) p i=1 i pi P Pi−1 Qn where P = i=1 pi , pi are the RNS moduli, is a multiplicative inversion with respect to pi pi , and Pi = pPi = p1 p2 · · · 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 −1 n Pi xi X X pi X = xi ≈ (44) P i=1 p i ki 1 1 |Pi−1 | where ki = pi pi are the constants of the selected system, and xi are the digits of the number presented in the RNS, while the value of each sum is in the range [0, 1). The final 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 difference 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 finding the residue of the division by the range of the system by taking the least significant bits of the number, which makes it possible to reduce the computational complexity from quadratic to linear-logarithmic complexity. 5. Conclusion The paper presents an efficient modification of the algorithm for detecting and correcting multiple residue errors with a fixed number of calculations of the syndrome, regardless of the size of the set of moduli, using an approximate method. The proposed modification 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 finding 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 identified 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 SP- 3149.2019.5 References [1] Yang L L and Hanzo L 2002 IEEE transactions on vehicular technology 51 1534–1546 [2] How H, Liew T H, Kuan E L, Yang L L and Hanzo L 2006 IEEE transactions on vehicular technology 55 387–396 [3] Etzel M and Jenkins W 1980 IEEE Transactions on Acoustics, Speech, and Signal Processing 28 538–545 [4] Keller T, Liew T H and Hanzo L 2000 IEEE Journal on Selected Areas in Communications 18 2292–2301 [5] Hanzo L, Liew T H and Yeap B L 2002 Turbo coding, turbo equalisation, and space-time coding (Wiley Online Library) [6] Liew T H, Yang L L and Hanzo L 2006 IEEE transactions on communications 54 1006–1016 [7] Zhang S, Yang L L and Zhang Y 2012 IEEE transactions on vehicular technology 61 1234–1250 [8] Sengupta A and Natarajan B 2013 IEEE transactions on wireless communications 12 2458–2469 [9] Yatskiv V, Yatskiv N, Jun S, Sachenko A and Zhengbing H 2013 The use of modified correction code based on residue number system in wsn 2013 IEEE 7th International Conference on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS) vol 1 (IEEE) pp 513–516 [10] Beckmann P E and Musicus B R 1993 IEEE transactions on Signal Processing 41 2300–2313 [11] Haron N Z and Hamdioui S 2011 ACM journal on emerging technologies in computing systems (JETC) 7 1–19 [12] Yin P and Li L 2013 A new algorithm for single error correction in rrns 2013 International Conference on Communications, Circuits and Systems (ICCCAS) vol 2 (IEEE) pp 178–181 [13] Goh V T, Tinauli M and Siddiqi M U 2004 A novel error correction scheme based on the chinese remainder theorem The Ninth International Conference onCommunications Systems, 2004. ICCS 2004. (IEEE) pp 461–465 [14] Tang Y, Boutillon E, Jégo C and Jézéquel M 2010 A new single-error correction scheme based on self-diagnosis residue number arithmetic 2010 Conference on Design and Architectures for Signal and Image Processing (DASIP) (IEEE) pp 27–33 [15] Tay T F and Chang C H 2014 A new algorithm for single residue digit error correction in redundant residue number system 2014 IEEE International Symposium on Circuits and Systems (ISCAS) (IEEE) pp 1748– 1751 [16] Yau S S and Liu Y C 1973 IEEE Transactions on Computers 100 5–11 [17] Krishna H, Lin K Y and Sun J D 1992 IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 39 8–17 [18] Mandelbaum D M 1976 IEEE Transactions on Information Theory [19] Goldreich O, Ron D and Sudan M 1999 Chinese remaindering with errors Proceedings of the thirty-first annual ACM symposium on Theory of computing pp 225–234 [20] Goh V T and Siddiqi M U 2008 IEEE Transactions on Communications 56 325–330 [21] Tay T F and Chang C H 2015 IEEE transactions on computers 65 396–408 [22] Barsi F and Maestrini P 1973 IEEE Transactions on Computers 100 307–315 [23] Jenkins W K and Altman E J 1988 IEEE transactions on circuits and systems 35 159–167