=Paper=
{{Paper
|id=Vol-2913/paper9
|storemode=property
|title=Efficient implementation of error correction codes in modular code
|pdfUrl=https://ceur-ws.org/Vol-2913/paper9.pdf
|volume=Vol-2913
|authors=Nikolay Kucherov,Viktor Kuchukov,Elena Golimblevskaia,Natalia Kuchukova,Irina Vashchenko,Ekaterina Kuchukova
|dblpUrl=https://dblp.org/rec/conf/iccs-de/KucherovKGKVK21
}}
==Efficient implementation of error correction codes in modular code==
https://ceur-ws.org/Vol-2913/paper9.pdf
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