Parallel Algorithms for Residue Scaling and Error Correction in Residue Arithmetic ()
1. Introduction
Because the residue number system (RNS) operations on each residue digit are independent and carry free property of addition between digits, they can be used in highspeed computations such as addition, subtraction and multiplication. To increase the reliability of these operations, a number of redundant moduli were added to the original RNS moduli [RRNS]. This will also allow the RNS system the capability of error detection and correction. The earliest works on error detection and correction were reported by several authors [1-12]. Waston and Hasting [1,2] proposed the single residue digit error correction. Yau and Liu [3] suggested a modification with the table lookups using the method above. Mandelbaum [4-6] proposed correction of the AN code. Ramachandran [7] proposed single residue error correction. Lenkins and Altman [8-10] applied the concept of modulus projection to design an error checker. Etzel and Jenkins [11] used RRNS for error detection and correction in digital filters. In [12-16] an algorithm for scaling and a residue digital error correction based on mixed radix conversion (MRC) was proposed. Recently Katti [17] has presented a residue arithmetic error correction scheme using a moduli set with common factors, i.e. the moduli in a RNS need not have a pairwise relative prime.
In this study, we developed two new algorithms without using MRD (Mixed-radix digit) or CRT (Chinese remained Theorem) for speeding-up the scaling processes and simplifying the error detection and correction in RNS. The first algorithm is used for these purposes, through the residue digit difference cyclic property (CPRDD) within the range of
, where
with r additional moduli. The moduli
are called the nonredundant moduli;
are the redundant moduli. The interval,
, is called the legitimate range, where
, and the interval,
, is the illegitimate range, where
, and
is the total range. This paper is organized as follows: Section II will describe the scheme the cyclic property of residue digit difference (CPRDD). Section III describes the Target Race Distance (TRD) algorithm and followed by some examples. Section IV discusses residue scaling and error correction using the TRD and CPRDD algorithms. Finally, the conclusion is given in section V.
2. Error Detection and Correction Using Residue Digit Difference Cyclic Property
Any residue digit xi representation in moduli set
has its cyclic length with respect to its module number. For example, if the moduli set is (4, 5, 7, 9), then the cyclic lengths of any residue digits
are 4, 5, 7 and 9, respectively. Since these cyclic lengths are not equal, they are very difficult to use as tools for error detection and correction. Actually, there exists the property of common (uniform) cyclic length in RNS between residue digital-differences (RDD). Consider three moduli set
. The residue representations and their corresponding digit-differences are shown in Table 1 and defined as the difference in value between two digits,
where
s are all modulo to positive values with respect to
if the cycle length of
is assigned.
Note that the residue digit-differences
in Table 1 are obtained from
if
, and from
if
. This difference of
or
in values may be positive or negative, depending upon
or
and
or
respectively All negative values must be modulo to positive values. For example, on starred row 28, as shown in Table 1, the digit difference in value for
and
is
. It results in ![](https://www.scirp.org/html/7-6801081\e122284a-2335-4c7e-aaac-b0c95352d544.jpg)
From the cyclic property of residue-digit difference (CPRDD) in RNS, we now have the following theorem.
Theorem 1. For a moduli set
and residue representation for
in RNS, there exists a cyclic property in differences between two residue digits,
or
. The cyclic length can be assigned, either to
or
, depending upon modulo operation with respect to
or
.
Proof: Consider the case respective to
, the residue-digit difference (RDD) between two digits in
can be in general expressed by the equation
(2-1)
where ![](https://www.scirp.org/html/7-6801081\163de8f0-a8cc-4cd9-aa12-032a99e26bcd.jpg)
![](https://www.scirp.org/html/7-6801081\60a76186-1a09-4a87-802c-3d6fe4ca0f17.jpg)
and
are integers.
For simplicity, we only consider the case of
and assume
, and the case of
can be obtained in a similar way.
The related theorem and algorithm are described as follows.
1) In cycle 0, (the initial cycle), we have
with
,
As ![](https://www.scirp.org/html/7-6801081\f925af5e-8433-44ca-826a-6ed5eede7316.jpg)
![](https://www.scirp.org/html/7-6801081\6c961b88-ee98-4f9b-9eb3-6bdcc89f752d.jpg)
Table 1. Cyclic property of Residue Digit Difference.
with
, we have
with mj’s 0s in cycle 0, where
means the largest integer less than or equal to x.
Thus, the RDD has mj’s “0” in the initial cycle for each modulus, i.e., in cycle 0,
for all
.
2) Next consider each modulus
Since
and
then
where
![](https://www.scirp.org/html/7-6801081\121d3170-2ef2-4e98-b56a-f190809b58a3.jpg)
![](https://www.scirp.org/html/7-6801081\eef4be54-4635-47a9-8bd9-24ec46d272a4.jpg)
For RDD = 0 (for cycles
)
then
![](https://www.scirp.org/html/7-6801081\dbcbe742-a9e6-4f5c-a5d1-7d3db27d5008.jpg)
with mj’s 0 s.
For RDD = 1 (not necessary in cycle 1),
with mj’s 1 s.
…
For RDD = mi − 1
![](https://www.scirp.org/html/7-6801081\5e571fc7-dc06-4cca-b4b8-60265cc36c3b.jpg)
with
s.
Corollary 1. From the above theorem, we can immediately obtain that each cycle in the residue-digit difference of x will start at location 0, and end at location
.
Corollary 2. It is easily shown that there exists mi number of cycles with respect to the cyclic length of
.
Proof. Since the residue-digit difference of
representation is pair-wise, the legitimate range of this pair-wise
is
, (from 0 through
). From corollary 1, the cyclic length is
. Thus the number of cycles within this cyclic length for
is
, and for
.
Theorem 2. The algorithm of theorem 1 and its corollaries can be extended to two or more pair-wise residuedigit differences.
Proof: consider a three moduli set, we have two pairwise moduli sets, whose RDD (Residue Digital Difference) is
![](https://www.scirp.org/html/7-6801081\460b8643-8a42-471b-aa80-5812f91e1399.jpg)
where
is again the referenced module.
Follow the same procedure as step (2) as above.
Assume
, and also pair-wise numbers
and
.
1) For ![](https://www.scirp.org/html/7-6801081\8a18f1ac-a4f5-4500-bbd9-9bb0ec9356df.jpg)
thus
![](https://www.scirp.org/html/7-6801081\808ef32f-d609-4498-a592-1f0bd48ad314.jpg)
“0” r2’s “
”![](https://www.scirp.org/html/7-6801081\b2659797-f846-4b47-92d3-c0013b5844fc.jpg)
This shows that
has also
“0”s in cycle 0 of
. The cyclic length is
, and the number of cycles for
is
.
2) For
and
(a constant for any RDD), if ![](https://www.scirp.org/html/7-6801081\a4aea4c2-6a53-4a52-8265-a40ec433d0e7.jpg)
![](https://www.scirp.org/html/7-6801081\fee931f4-6f7c-4e26-9977-74038bbbe584.jpg)
This shows that the
in any location has also
in cycle i of
. The number of cycles for
is still
. Combining these three moduli
into one set, we have cyclic length
(for example,
). The number of cycles for
are
,
, and
, respectively. As shown in Table 1, the RDD pairs of
, and
(1, 1)
In general,
and
with
rows and
in each row.
This completes the proof.
Example 2-1.
Consider a moduli set
,
and its corresponding residue digits representation set is
. The cyclic length is
and the number of cycles for
, and
are
, and
, respectively.
Error detection and correction:
Before the CPRDD algorithm used for error detection and correction is described, some basic terms in use must be defined.
Definition 1: Stride distance
: It is the incremental or decremental distance between moduli
and
in absolute value from ith cycle to
cycle.
For example:
.
(1) Error detection Let the moduli set be
where
are the nonredundant moduli and
are the redundant moduli. Since the cyclic lengths of CPRDD
are constant, it is thus easily found that the number of cycles on track
from the starting point 0 (or other
) to its target position. In turn the distance of RDD’s can also be found.
Theorem 3. The number of cycles on track
(column
) from any starting point (say
) to its target position
can be found using the equation below;
![](https://www.scirp.org/html/7-6801081\df11f6b4-9476-4257-a2bc-8f31d26a7c4c.jpg)
where
the stride distance between moduli
and
and k = the number of cycles passing through from starting point
to the destination,
on track
If
, then the number of cycles are equal to the total cycles from the starting point “0” to its target position
.
Proof: Since
is the number of cycles from 0 to
with respect to module
, and
is the cyclic length, thus
is the total distance from the starting point
to its target position
. The remaining distance for
on track
in the
th cycle must be on the same row of
on track
. Thus,
.
Once the RDD’s of
are found, the error detection and correction for moduli can be found just by comparing the calculated cycles or RDD with the original residue representation, pair-wise so that the error module can be detected.
The procedure for error detection by using CPRDD algorithm is summarized as follows.
1) Choose two most significant (largest) moduli as the referred moduli among the n moduli, say
and
.
2) Find the skip distance of a cycle
.
3) Find the digit difference
.
4) Create the equation of
or
(2-2)
5) Solve for
from Equation (2-2) as the
and
are known. The value of
must be less than or equal to
.
6) Find the corresponding
distance from the starting point to
.
7) Calculate
from RDD1, RDD2,
, and check the values of
, and …. If these sets’ numbers are equal, then no error occurs; otherwise, error exists.
We take the similar numerical as example 2-1 to verify this algorithm. (CPRDD)
Example 2-2. Assume that a moduli set
and number X whose residue representation is
. If an error occurs at
, the error detection can be described as follows.
Let us begin our procedures from the
. Since
and
. Then
. Solve for
, and let
within legitimate range
, then
.
The corresponding
primary distances for these two
are, respectively,
![](https://www.scirp.org/html/7-6801081\bf78ee83-1b3b-4eb4-ae95-2eb88b927da0.jpg)
Thus, the generated results of the residue representation from
and
are respectively
,
.
Since the calculated results of X1 and X2 are not identical, there must be errors in one of these moduli. We cannot determine which one is erroneous. To locate the module where the error exists, at least one additional (redundant) module must be used.
The procedure for error correction by using CPRDD algorithm is essential the same as the error detection. However, two additional redundant moduli
and
must be added for one error correction. Note that only one redundant modulus added for error detection.
1) Choose
as a referred modulus.
2) Find
as the same procedures of error detection steps 2-7.
3) Examine the values of
. If common value exists among,
then no error occurs. If there is one and only one, say
that has no common value with all other
, then an error exits in modulus
. This completes the error correction procedures.
The following example is illustrated here to verify this algorithm.
Example 2-3. Error correction As before we can further locate and correct a single error by adding two redundant moduli,
and
. Let us use the same example. The moduli set
, where
and
are redundant moduli
and
, and the residue X representation,
. If a single error occurs at
, e.g.
, and
is assigned as a reference module, then
,
,
,and
. From CPRDD algorithm, we can find the number of cycles for these RDD’s.
,
,
,
![](https://www.scirp.org/html/7-6801081\c3bf6930-3985-4a71-b01d-a13be99565be.jpg)
Since the cycle length is 9, all above
values must be less than
. Thus we have
![](https://www.scirp.org/html/7-6801081\b4272ca0-da6a-4e8b-8b7e-c4e82e2552f9.jpg)
![](https://www.scirp.org/html/7-6801081\89469892-eb18-44c3-b6df-a5f513d70a33.jpg)
.
![](https://www.scirp.org/html/7-6801081\ad098e7d-8e59-4220-96c7-c499dcbbc199.jpg)
If no errors occur, all kij’s are equal, i.e.,
.
Compared to the above results with pairwise moduli, only
meets this condition. There exists no such value in
.
This shows that the module
is faulty, therefore we can correct it as follows: since
, the
.
Thus ![](https://www.scirp.org/html/7-6801081\af787c4b-fba0-4152-b06f-e95c731eedca.jpg)
![](https://www.scirp.org/html/7-6801081\48359a0f-23b8-4f7d-baee-6ab3e1042a4e.jpg)
![](https://www.scirp.org/html/7-6801081\c5139117-d9b1-4e91-a544-cf78078df710.jpg)
.
This completes the error correction.
Note that the above CPRDD’s for each residue-digit difference,
, and
can be processed in parallel. In addition, if the referenced module is assigned to the erroneous module by chance, e.g.,
this algorithm will fail to locate the error. In this case, there are no
values that can be found to match this condition. The way to solve the problem is, of course, to assign any other moduli, e.g.,
or
.
The hardware design for the proposed algorithm in Example 2-3 is shown in Figure 1.
3. The Target Race Distance (TRD) Scheme
The conversion or decoding technique from residue representation to X in binary is usually accomplished using the mixed-radix digit (MRD) or Chinese remained theorem (CRT). An optimal matched and parallel converter of this kind can be seen in [13]. The MRD is shown by the following expression with weighted numbers:
![](https://www.scirp.org/html/7-6801081\75a1b018-e793-40df-a9b4-4fab58587a58.jpg)
where
, and
is the mixed-radix conversion (MRC) of x.
Optimization can be obtained using this method, as the accessed table lookup time is exactly equal to the right addition time, after immediate column stage for the tree network of the adders.
Figure 1. The hardware implementation for the proposed error and correction location algorithm can be accomplished without using lookup tables.
However, time is still consumed reading a large number of lookup tables. Additional hardware complexity is required by the adder-tree networks. An algorithm called the target race distance was with a simpler structure was developed for high-speed conversion.
TRD algorithm Suppose each residue number in the
has its own track
, and the distance over track
from 0 (starting point) to
(end point) through
cycles can be expressed using
.
Obviously, the primary (no multiples of mi) distance of
is
. To obtain the X from its residue representation of
, we must find a target such that
traversing the same distances over tracks
respectively, i.e. when the TRD distance of each target
is reached, then
The TRD distance of X can be found from the following theorem:
Theorem 4. Consider the simple case of two moduli sets
. Its residue representation and targets are x1 and x2 respectively. Let
be the primary distance of residue x1 from 0 to x1 on the track
, and
be the primary distance of x2 from 0 to x2 on track
. Then the TRD distance for these two residues x1 and x2 that have the same TRD distances can be obtained by the following equation.
(3-1)
In addition, k1 can be calculated from the equation
![](https://www.scirp.org/html/7-6801081\2dc0868e-10f8-49b8-8a1b-a303b5289195.jpg)
where m1 is the cyclic length of x1, and k1 is number of cycles, all of the integers,
.
Proof: It is easy to show that the above
is the common target distance of x1 and x2, Since
![](https://www.scirp.org/html/7-6801081\e9d856cd-7062-405c-a379-3e41775135e9.jpg)
And
thus
is the TRD distances for both of x1 and x2.
Corollary: It is evident that the above theorem can be extended to n moduli set
and residue number
. The corresponding TRD of
are therefore
![](https://www.scirp.org/html/7-6801081\c15c84c8-d3f1-4fa6-a5d0-ebbee6cdcd94.jpg)
In addition, ki can be solved from the following equations.
![](https://www.scirp.org/html/7-6801081\6b670095-77a4-42bb-bd88-30aaf60ec5be.jpg)
…
![](https://www.scirp.org/html/7-6801081\11722bc7-7e30-449b-8d09-8c7f396d3925.jpg)
where ![](https://www.scirp.org/html/7-6801081\c753a8fc-cfde-4fc4-beff-c368bece437e.jpg)
Note that
are the targets of moduli
respectively and the
is the distance that has equal track lengths, i.e.
. That is;
.
Example 3-1 Let the moduli set be
and the residue representation be
. The procedures to find the TRD distance can be described as follows:
1) Find the primary distance
of residue
since
and ![](https://www.scirp.org/html/7-6801081\8a3cfb99-5117-48c8-84f4-6eefbf272144.jpg)
is required , thus
, and
![](https://www.scirp.org/html/7-6801081\ef5c023a-8232-485c-a256-3c5c2116a771.jpg)
2) Repeat the procedure 1 to find the number of cycles k2 and k3 and the last TRD distances (destinations),
and
.
Since ![](https://www.scirp.org/html/7-6801081\774231eb-5f45-40be-8dd1-b822dcac66ab.jpg)
![](https://www.scirp.org/html/7-6801081\8cfb0d3b-913a-47f4-9165-bd86d63f1163.jpg)
![](https://www.scirp.org/html/7-6801081\2d03d198-15ee-40f6-8303-4f938be3348c.jpg)
![](https://www.scirp.org/html/7-6801081\78f68da6-6b71-4601-8bd7-c2380761c00c.jpg)
thus ![](https://www.scirp.org/html/7-6801081\817e374f-c60c-404c-af0e-aea1554801c4.jpg)
and ![](https://www.scirp.org/html/7-6801081\7707f431-77d6-4f21-8bf2-a027db3efc8e.jpg)
![](https://www.scirp.org/html/7-6801081\6973b86e-e2a8-465f-a2ff-159b28db05d6.jpg)
![](https://www.scirp.org/html/7-6801081\f0b812d9-8a9f-4251-a0b7-d1046398807c.jpg)
![](https://www.scirp.org/html/7-6801081\afb1ee1e-ca85-4167-bee7-e5cab8125064.jpg)
thus ![](https://www.scirp.org/html/7-6801081\d04951a8-8257-4400-b16f-1907b18a85ff.jpg)
and ![](https://www.scirp.org/html/7-6801081\9961bb25-45e1-43e7-a196-6f815c78241d.jpg)
The final TRD distance is the common distinction of this system for targets
and
i.e.
. This result can be verified as follows:
,
,
and ![](https://www.scirp.org/html/7-6801081\b2495ba5-6155-4379-b3ce-6a38f85a6b03.jpg)
Figure 2 Shows the TRD’s on tracks
and
respectively.
Error detection and correction by TRD algorithm A redundant residue number system with
redundant moduli will allow detection of any single error [4,14]. Consider the moduli set
and the correct residue representation
. Let us
Figure 2. TRD’s on track L1, L2, L3 and L4.
assume that
is the redundant moduli with a single error
residue representation. The TRD theorem can be used to detect this error. We find that final TRD for
and
does not fall into the legitimate range as follows i.e.
![](https://www.scirp.org/html/7-6801081\5293fff1-acdf-4cbb-aa48-431ac1a78be6.jpg)
![](https://www.scirp.org/html/7-6801081\2c920bb5-e116-4ee2-aa57-2ab65f549aa6.jpg)
The final TRD distance
. If we need to locate and correct this module error, another redundant module must be added. Let us assume that
for this requirement in the above residue representation.
The current redundant moduli set is
and the correct residue representation is
. Let us assume that
and
are the redundant moduli. With a single error
. The TRD theorem can again be used to locate and correct this error. We find that final TRD’s for
dose not fall in the legitimate range, but other final TRD’s for
do, falls in the legitimate range:
1) TRD for
and ![](https://www.scirp.org/html/7-6801081\a5ff6451-7d92-4421-9ba5-8863c90b3355.jpg)
![](https://www.scirp.org/html/7-6801081\e5aa2df1-1db7-4555-b2d6-e5216463cef2.jpg)
2) TRD for
and ![](https://www.scirp.org/html/7-6801081\eb923c34-a23c-448a-b9f3-f8ad84bc3cd6.jpg)
![](https://www.scirp.org/html/7-6801081\8de5da0e-2b12-4733-baab-d6e03000dc07.jpg)
![](https://www.scirp.org/html/7-6801081\5a12f309-5b19-4692-b65b-a746936c0b3f.jpg)
Thus, the error is located at module m2 and must be corrected to
.This algorithm can also be used for multiple error corrections. However, at least three redundant moduli are required. The procedures are similar.
4. Scaling with Error Correction
The above proposed algorithm used for error detection and correction has the advantage of not requiring lookup tables. No CRT (Chinese residue theorem) decoding processes are required. However, it is still time consuming and requires extensive hardware complexity for each module having multiple-value inputs to the match unit and selecting a correct one as a output. To improve this drawback, an optimal matching algorithm is proposed here for the error correction. The following two theorems will be used and an example follows.
Theorem 5. Let m1 and m2 be two relative prime numbers in RNS for module 1 and module 2 respectively. Then there must exist the relation represented by the equation
, where
so that
, assuming
. The
and k are restricted to integers.
Proof: As a first step, let
. It is easily seen that
and
will be satisfied. Next consider
. Since there are two different pair combination
and
, thus the difference between
and
of k will always be satisfied for
, where k is restricted in integers.
Theorem 6. If the values of m1 and m2 and k in the equation
are known, then p1
and p2 can always be determined from equation
or
, where p1p2 and k are within the range: ![](https://www.scirp.org/html/7-6801081\546f13b5-3ac5-4217-83db-7ab34e9a4413.jpg)
Proof: Let the difference value of
be equal to d, then d will be the integers within the range between 0 and m2, i.e.,
, or
. These two expressions show that we can always select an integer value p, within the interval between 0 and
or
to satisfy the conditions
or ![](https://www.scirp.org/html/7-6801081\883ec0bc-b91f-4dcb-af46-8f7641bbea66.jpg)
Example 4-1 Let
, and
. Find the minimum values of p1 and p2 respectively from the following equation :
![](https://www.scirp.org/html/7-6801081\4ebd6bc6-68a3-4ec4-aa1c-3e50db54aa9b.jpg)
Since
and
, we have
and
(4-1)
or
(4-2)
from Equation (4-1)
so![](https://www.scirp.org/html/7-6801081\aca39798-bb55-4b82-9f54-a7e03cbe4b50.jpg)
from Equation (4-2)
, so
.
This result can be verified by substituting
into the above equation. Theorem 6 is very useful as shown in the following example.
In Theorem 3 of Section III, the number of cycles on track
from the starting point “0” to its target position “
” can be expressed by setting
, i.e.
(4-3)
where
is the module i stride distance referring to module j. Similarly, the number of cycles on track
from the starting point ”0” to its target position “
” can be expressed by setting
, i.e.;
(4-4)
Since, from theorem 3, the cyclic length of the residue digits differences reference to module mj is constant (uniform), then there must exist a condition,
Eliminating the above terms from Equations (4-3) and (4-4),
![](https://www.scirp.org/html/7-6801081\79f0ce91-2caa-4604-8bd8-43951cffddcb.jpg)
![](https://www.scirp.org/html/7-6801081\3e52f7cb-2d84-4e37-8cc0-46445855e1fd.jpg)
where
,
and
![](https://www.scirp.org/html/7-6801081\333bd651-4fe1-496a-8ed0-5acaff34d862.jpg)
Example 4-2 Let the moduli set ![](https://www.scirp.org/html/7-6801081\e70e1dbf-0ded-405a-89a3-6814fa19e791.jpg)
, and the error
, the error occurs at m3.
Follow the same procedures of the Example 4-1 to use this algorithm.
(4-5)
(4-6)
(4-7)
(4-8)
Eliminating
and
from Equation’s (4-5) and (4-6)
,
![](https://www.scirp.org/html/7-6801081\bd369a51-4eaa-4f7a-bf9c-76acf95f74c7.jpg)
solve for
from (4-5),
![](https://www.scirp.org/html/7-6801081\ad74eecb-8b7b-41b1-bb39-2751e99ac14e.jpg)
![](https://www.scirp.org/html/7-6801081\a5b28569-0422-49d0-9dbb-2392513a81e9.jpg)
![](https://www.scirp.org/html/7-6801081\2444e828-9107-4eda-89f4-25b0575cd82a.jpg)
or ![](https://www.scirp.org/html/7-6801081\e71473f0-6a1d-4f15-b2fb-d6f2b4c70843.jpg)
![](https://www.scirp.org/html/7-6801081\a13f034c-98b2-463a-80b9-2641126a7731.jpg)
.
Check from Equation (4-5),
![](https://www.scirp.org/html/7-6801081\b1c1f3a8-9c28-424c-a2c4-e82050281997.jpg)
![](https://www.scirp.org/html/7-6801081\c0b0cc96-305b-43a6-904e-e07c8fd6c9b4.jpg)
This shows that the error occurs at module m3. From this result, we can immediately obtain
. Noting that it may happen that the assigned referenced memory moduli falls coincidentally with error memory module m3. In this occurrence, we cannot find the correct (integers) values of P1 and P2 within the legitimate range. It seems that this algorithm can only detect error. To complete the error correction procedure, we can simply change the referenced module to any other and follow the same procedure as before. This guarantees that the proposed algorithm in Theorem 4 will also work well in this case. The hardware structure for illustrating this algorithm is shown in Figure 3.
The proposed TRD (target Race Distance) scheme used for error correction can be used for scaling and assigning numbers in a residue number system. A redundant residue number system (RRNS) is defined as before in an RNS with r additional moduli. The moduli
, are called the nonredundant moduli, while the extra r moduli,
are the redundant moduli. The interval,
, is called the legitimate range where
and the interval,
, is the illegitimate range, where
is the total range. In the RRNS, the negative numbers within the dynamic range are represented as states at the upper extreme of the total range, which is part of the illegitimate range. The positive members are mapped to the interval
, if Mk is odd, or
, if Mk is even. The negative numbers are mapped to the interval
Figure 3. In the block diagram using optimal matching between multiples Pi m and Pkmk, the residue digits are corrected by xi - x4 = di4.
if Mk is odd or
if Mk is even [14].
The one-to-one correspondence between the integers of the dynamic range and the states of the legitimate range in the RRNS can be established using a polarity shift. [11], The polarity shift is defined as below.
![](https://www.scirp.org/html/7-6801081\a4492ad1-0333-44c7-bde8-b344e6017393.jpg)
where
denotes the value X after a polarity shift and
if
is odd, so that
a polarity shift needs to be performed prior to correcting or scaling since
belongs to the legitimate range. If a single residue digit error
is introduced and corresponds to modules mj, then, after a polarity shift.![](https://www.scirp.org/html/7-6801081\d4259a13-4211-42d0-814b-b9645444b0d7.jpg)
![](https://www.scirp.org/html/7-6801081\c09c5e70-8831-42da-82ed-65418e669a84.jpg)
where
is the multiplicative inverse of
moduli mj i.e.
and
The ![](https://www.scirp.org/html/7-6801081\4d7b302a-a55c-4bbb-a9f5-1392fd0d1f2d.jpg)
denotes a single residue digit error and must fall within the illegitimate range ,
[11].
Since
, and can be represented uniquely by
,where ![](https://www.scirp.org/html/7-6801081\39b792ef-3385-4a11-ade4-432005c9321d.jpg)
are the coefficient from the Chinese Remainder Theorem
(CRT), i.e,
, where
. Note that the redundant digits
are zeros if no error is introduced, while at least one redundant digit is not equal to zero if a single error is introduced. Therefore, it has the same meaning that ![](https://www.scirp.org/html/7-6801081\9d4a577c-372d-4546-9b3c-c7f92c25b172.jpg)
or
is used to be the entries of the error correction.
1)
2) ![](https://www.scirp.org/html/7-6801081\6c1eda03-74c1-4fc6-830b-265ac2f85743.jpg)
Although the errors detection and correction described in section II have been simplified the processes due to no need of CRT conversion. It is still hardware complex and time consuming for the residue scaling operation. To improve this drawback, a direct residue-scaling algorithm can be used. It is flexible and direct to detect and prevent the errors. The flexibility means that the scaling factor can be arbitrary chosen any single module such as
, i.e. not necessarily beginning from
to
. in order. The direct capability means no requirement for CRT extension processes for decoding or lookup tables. The following theorem (theorem 7) and example are clarified.
Theorem 7. If the scaling factor K is one of the module set
and the residue digits are
, respectively, then the residue digit
scaled by a factor
can be obtained using the equation
(4-9).
Proof: It is easy to show that when
, and Equation (4-9) is divided by
on both side, we have
(4-10).
Example 4-3. For convenient comparison of the proposed TRD algorithm to other schemes such as appeared in [14], we take the same numerical example in [11]. Let the moduli set
, where
are regular moduli and
are redundant moduli. Then
,
,
, and
. The sufficient conditions for correcting single residue digits errors are 1)
, or 4,
, or 2,
, The maximum
, and 2) ![](https://www.scirp.org/html/7-6801081\83dd07dc-d90d-4c08-9b23-6b1a5a3f35b9.jpg)
![](https://www.scirp.org/html/7-6801081\c651caa8-7003-48c1-8696-7cc5bb6f62ff.jpg)
Thus the moduli set satisfies the necessary and sufficient conditions for correcting single errors digit. Assume
and a single digit error
is introduced, then
.
After a polarity shift, ![](https://www.scirp.org/html/7-6801081\8ad6c5c4-e322-4b0a-817c-bae911e6d003.jpg)
Follow the same procedures as shown in Example 4-2. CPRDD is applied for correction without the need for using a table.
1) Assign the moduli
as the reference moduli, the following residue digit references and its corresponding CPRDD equations:
are obtained
![](https://www.scirp.org/html/7-6801081\a35aca14-a923-4fe7-97d6-8035dccf4f0e.jpg)
![](https://www.scirp.org/html/7-6801081\f37c6940-d717-420d-bb10-3831be9bf8a9.jpg)
![](https://www.scirp.org/html/7-6801081\5e5e21c4-ee9e-44f5-ab3c-1487aa75407e.jpg)
![](https://www.scirp.org/html/7-6801081\88fec4ef-70f9-4daf-b13b-5cf0b4ac8e78.jpg)
![](https://www.scirp.org/html/7-6801081\55b0f1e5-5a24-4f90-9c12-41bda00041f5.jpg)
2) Choose two highest digit difference as one pair for equal target race distance e.g.
. Then the true primary RDD equations are
(4-11)
And
(4-12)
where
and
are selected so that the two RDD are equal distances.
3) Eliminating k terms in Equation’s (4-11) and (4-12) by putting ![](https://www.scirp.org/html/7-6801081\ac3d7725-db37-4b0c-a471-2e99a37a7b62.jpg)
![](https://www.scirp.org/html/7-6801081\0b27397e-b6fc-4e57-8b49-bed3d358fabf.jpg)
where
, then
.
4) Substituting p1 and p2 into equations (4-9) and (4-10) respectively, we have
, then
, and
, also,
.
5) Checking other three RDD’s
![](https://www.scirp.org/html/7-6801081\fe1518c8-e0d6-49c1-8850-d4e9d3e33f25.jpg)
![](https://www.scirp.org/html/7-6801081\895ca5ad-65c4-4961-a8f7-d086ecde61bc.jpg)
![](https://www.scirp.org/html/7-6801081\da05bcad-79a4-4474-a4fe-9c87197621e4.jpg)
The only different module residue occurs on module number at
, i.e.,
. The three target distances, can be from any module residue, say, (except
),
.
.
The residue representation of X is therefore,
. If a single digit error
is introduced, then,
.The corresponding error is therefore
![](https://www.scirp.org/html/7-6801081\591542f1-f776-4cc7-abb8-1152ea90d2cc.jpg)
![](https://www.scirp.org/html/7-6801081\22e4dd46-cbfa-45ba-a864-9c3d1b25eb0b.jpg)
![](https://www.scirp.org/html/7-6801081\bbd18a4a-6c82-4259-b4c3-59821c7053c7.jpg)
After a polarity shift,
![](https://www.scirp.org/html/7-6801081\5a73c8a7-0ef6-49cc-bacf-8ab8e7f8a8ba.jpg)
and the scaling factor
to
is
. The final step must use a lookup table to obtain the result,
[13].
For verifying our proposed algorithm, the table of the corresponding
is not required as in [13]. The processes for finding and correcting a single error based on our method are described below.
1) Find the residue digit difference to a selected module, say
as before
. For verifying that our proposed algorithm detects and corrects single error without using a table, the same numerical example is used to describe the procedure as follows:
,
,
![](https://www.scirp.org/html/7-6801081\8110bbe2-9b27-4d59-8ea1-4c2d513f9d8f.jpg)
![](https://www.scirp.org/html/7-6801081\e43635b2-a255-4a9c-9cad-de1c8786aa21.jpg)
![](https://www.scirp.org/html/7-6801081\9565cb21-69a0-45e4-8ede-98327cef5903.jpg)
Then
![](https://www.scirp.org/html/7-6801081\a3365597-5ee4-45a8-9826-f0787dce318d.jpg)
![](https://www.scirp.org/html/7-6801081\a50329e2-40e4-409f-9ce4-15b8ee01e481.jpg)
![](https://www.scirp.org/html/7-6801081\ab92f0d8-f517-4a06-b78f-a8a15ef39511.jpg)
![](https://www.scirp.org/html/7-6801081\d41f9920-7b4b-4005-a4b4-4f5afa86a6fa.jpg)
![](https://www.scirp.org/html/7-6801081\69a66103-9ae0-4db4-a58d-a38f60c88094.jpg)
2) Choose two highest digit differences as one pair for equal target race distances. e.g.
and
, the following two equations can be obtained:
(4-13a)
(4-13b)
3) Eliminating k terms in (4-13a) and (4-13b) by putting ![](https://www.scirp.org/html/7-6801081\8e05ea2d-4ef8-41cf-9054-10edbbfacd5f.jpg)
then
and
.
4) Substituting
and
into Equation’s (4-13a) and (4-13b) respectively, we have
, then
, and
, also,
![](https://www.scirp.org/html/7-6801081\3f3a70ec-47ad-45d1-9faf-4123317f9e88.jpg)
Obviously, the error is located at
thus
.
Furthermore, the CPRDD algorithm can be used directly and in parallel for residue scaling and error correction. Thus the process is greatly speeded up.
Example 4-4 For convenient comparison, the same numeric example as in [13] is illustrated here. Consider
, and scaling factor
. If an input
and a single residue digit error
, corresponding to
Then ![](https://www.scirp.org/html/7-6801081\76f9742c-6b78-4d2d-8596-23cf927628f1.jpg)
After a polarity shift,
![](https://www.scirp.org/html/7-6801081\2d6bd238-6271-41c4-b77f-a973477a7836.jpg)
1) Dividing by
after subtracting
from ![](https://www.scirp.org/html/7-6801081\a462c33a-cb7a-4fe6-a0b8-9b9376e87613.jpg)
, this leads
,
,
,
,
.
2) Dividing by
after subtracting
from ![](https://www.scirp.org/html/7-6801081\37003c8b-7835-4e04-a8a8-0eddcfe306c7.jpg)
![](https://www.scirp.org/html/7-6801081\a97c3a7d-b7ae-46d7-95a6-2a8cfbc272f2.jpg)
![](https://www.scirp.org/html/7-6801081\8b1f7a0e-d65d-4934-9499-80e15e0654a9.jpg)
![](https://www.scirp.org/html/7-6801081\4f2a52f2-bfdf-45cc-8510-400dad633743.jpg)
![](https://www.scirp.org/html/7-6801081\8d2be72c-b168-46d6-9062-cc908eb46752.jpg)
Since from above only k3 does not match with all other’s ki, i.e.
and
. Therefore, there occurs an error at
. Once this error is detected, it is easily found and corrected from the above equations,
, which in turn
and
.
![](https://www.scirp.org/html/7-6801081\369a1676-275b-4e6a-8d2c-7db8c76d552b.jpg)
![](https://www.scirp.org/html/7-6801081\93ccbdbe-5070-4e87-b895-71b0ae50ecb6.jpg)
![](https://www.scirp.org/html/7-6801081\576d0d32-5f7a-4451-990f-f84c533cff7a.jpg)
![](https://www.scirp.org/html/7-6801081\0c2202e2-caa1-4101-8e95-c9c3b145d82b.jpg)
that ![](https://www.scirp.org/html/7-6801081\7ef22315-3b70-46b4-aad2-c4d23b62ce3e.jpg)
Divided by “2”,
![](https://www.scirp.org/html/7-6801081\c265a822-81e9-4303-80a6-cab8dd827024.jpg)
![](https://www.scirp.org/html/7-6801081\54297052-2b41-424a-bce4-61a0ed3414df.jpg)
![](https://www.scirp.org/html/7-6801081\5169d92d-d3b8-4f97-b2c0-0f677f9ec272.jpg)
![](https://www.scirp.org/html/7-6801081\cdf75e4a-3004-457d-bf91-4f2939bfee68.jpg)
![](https://www.scirp.org/html/7-6801081\4071790e-2f5e-49e3-b190-af28ad5e59bf.jpg)
.
Divided by “5”
;
![](https://www.scirp.org/html/7-6801081\8972eabb-50c2-471f-b36e-e37120862c76.jpg)
![](https://www.scirp.org/html/7-6801081\e22ddbd9-a19f-46b4-8809-3f4020ab9fef.jpg)
![](https://www.scirp.org/html/7-6801081\764b64b8-4a0c-459d-91ad-ce5393c100fa.jpg)
.
The hardware structure of this example for the residue scaling is shown in Figure 4.
Actually this algorithm can be divided by any arbitrary moduli.
Example 4-5 Divided by any arbitrary moduli, say
, it must subtract
from X
![](https://www.scirp.org/html/7-6801081\6c72f6da-b16b-4ad5-b136-3077fa3f85c3.jpg)
![](https://www.scirp.org/html/7-6801081\633d2db2-9a7f-4bc6-b46b-2661a1888b3e.jpg)
![](https://www.scirp.org/html/7-6801081\f353f6da-af04-4240-b152-cbb2efe8b2bf.jpg)
![](https://www.scirp.org/html/7-6801081\d78fdfbe-d04a-4811-b0e0-3066496c08e2.jpg)
![](https://www.scirp.org/html/7-6801081\0b0c780a-cbf4-4c34-a922-88adae91d20a.jpg)
Then
![](https://www.scirp.org/html/7-6801081\aa1f1a6d-619a-4575-b6ab-2744e6d1b69e.jpg)
![](https://www.scirp.org/html/7-6801081\b8dc9ec1-fc4a-4b60-8f5b-106066806fd6.jpg)
![](https://www.scirp.org/html/7-6801081\d3533864-fd4c-4f5f-b64e-2f37a613304c.jpg)
![](https://www.scirp.org/html/7-6801081\4956da78-759a-4e5f-ad96-a046453e3fa9.jpg)
![](https://www.scirp.org/html/7-6801081\8eee0a62-21db-42a2-8590-b5f3a73fe1dd.jpg)
check
.
This results
![](https://www.scirp.org/html/7-6801081\7fce12d1-eb28-4c97-94bd-948bf6585ddc.jpg)
![](https://www.scirp.org/html/7-6801081\51a348ca-b18a-4617-9f2f-1be82393a6b2.jpg)
It can be seen from above that
which are equal each other as expected.
Example 4-6 For processing two residue scalings and error corrections in parallel, we take Example 4-4 as an illustration. Let scaling factor
, i.e., the first residue scaling factor is 2 and the second one is 5 or verse versa. It is easily shown that the extended CPRDD algorithm is used and can be completed in one cycle. That is
![](https://www.scirp.org/html/7-6801081\ff45ef9d-b63e-42df-b497-9c7629520ea3.jpg)
![](https://www.scirp.org/html/7-6801081\83b2d083-33b7-400f-bdd2-490d3c1e0de8.jpg)
![](https://www.scirp.org/html/7-6801081\83a1c2f8-0cde-43f6-a6e2-5f1d446213c9.jpg)
![](https://www.scirp.org/html/7-6801081\c8d1b2b9-41e5-4306-8770-83a90522ae16.jpg)
![](https://www.scirp.org/html/7-6801081\01a97b17-ed93-4fe5-b414-64e036d66bb3.jpg)
The result is identical
, i.e.,
, and
, which are identical results as shown in Example 4-4.
Example 4-7 For error correction
![](https://www.scirp.org/html/7-6801081\ec606736-256a-434c-afb8-37d4506409b1.jpg)
![](https://www.scirp.org/html/7-6801081\edc9fab1-ae2e-47c0-a7fd-f205d7c2d625.jpg)
![](https://www.scirp.org/html/7-6801081\74a1bfbd-34f6-4703-8a40-a26afa22b78c.jpg)
Figure 4. Hardware structure of the residue scaling number for Example 4-4.
![](https://www.scirp.org/html/7-6801081\788f6abc-5881-4411-9517-dd39cca71d7b.jpg)
![](https://www.scirp.org/html/7-6801081\1338c1b6-1838-4de4-ba93-c8a33ddb5fe0.jpg)
![](https://www.scirp.org/html/7-6801081\78cb805c-d083-431b-ae4c-d16bce405441.jpg)
![](https://www.scirp.org/html/7-6801081\9d952ef5-251e-462d-95b3-d97fe95b3d52.jpg)
the correct
, and
![](https://www.scirp.org/html/7-6801081\e9887272-d7e9-4925-b581-6d3f4f62a8f9.jpg)
This shows
. Therefore the error correction is made by
and
, which corresponds to the value in Example 4-4, in scaling factor
, (dividing by “5” part).
From above results, this checks that scaling
which is within the accuracy of the residue scaling factor.
In a general case,
, this time we must modify the subtraction of
and
from the X, before the process of the scaling. If
is the scaling factor, then the subtraction must change to
, where
so that
or
Let us consider the following example:
Example 4-8
of moduli set
. The scaling factor
. is assumed. Then, residue
, and
can be found from
.
. Thus
and
.
Alternatively, it could be from other module
,
, where
and
![](https://www.scirp.org/html/7-6801081\180fa235-aecb-4e39-af86-9fb200fa306e.jpg)
![](https://www.scirp.org/html/7-6801081\a4fd295c-925c-4450-b267-1f4c4b34251b.jpg)
which has the same number to be subtracted.
![](https://www.scirp.org/html/7-6801081\b3c705ec-c27b-440d-92a3-327b22614a85.jpg)
![](https://www.scirp.org/html/7-6801081\0bdff765-8c78-4d06-8e37-81cc0eb143e3.jpg)
![](https://www.scirp.org/html/7-6801081\24e93783-b51c-49a3-90ab-7c2cfb817041.jpg)
![](https://www.scirp.org/html/7-6801081\961b2feb-3a43-49a9-b5c9-1386239f35a5.jpg)
![](https://www.scirp.org/html/7-6801081\dedc476a-dc1d-4b47-8616-c9579b2a914a.jpg)
From CPRDD algorithm, the scaling processes are performed as before, we then have the following results by scaling factor
;
![](https://www.scirp.org/html/7-6801081\37f502ec-ef96-4bc9-a869-9f8ba00d06e6.jpg)
![](https://www.scirp.org/html/7-6801081\73961dfe-776d-4bb3-a6dc-6d56ec2e01da.jpg)
![](https://www.scirp.org/html/7-6801081\6923330a-7487-4f3f-aefa-944488ae2fd7.jpg)
![](https://www.scirp.org/html/7-6801081\0f4265ef-fbb7-473c-a3ec-0b48948ff0c9.jpg)
![](https://www.scirp.org/html/7-6801081\1c6529fe-8ad8-4c01-bb47-7fcd86334470.jpg)
Thus
, which is exactly the value
and is the most closed to
.
This result can be checked using sequential steps as follows:
For ![](https://www.scirp.org/html/7-6801081\77ffab0e-b53a-47cc-8110-4da392fec984.jpg)
![](https://www.scirp.org/html/7-6801081\50df4120-0e83-4f57-82b4-07c749c1f276.jpg)
![](https://www.scirp.org/html/7-6801081\c0139cba-0a86-4e68-a923-b2239dde95d7.jpg)
![](https://www.scirp.org/html/7-6801081\03646cab-6722-4801-8d2a-c6a514109448.jpg)
Divided by 2:
![](https://www.scirp.org/html/7-6801081\f882761b-bb3b-4232-98ed-e72101e7de19.jpg)
![](https://www.scirp.org/html/7-6801081\3bd4a0d9-3049-44fe-9c74-f8d0755d7a83.jpg)
![](https://www.scirp.org/html/7-6801081\031d5f19-3246-4ba9-b7ed-c917d61b56d6.jpg)
![](https://www.scirp.org/html/7-6801081\35219673-b085-41b3-85a8-c8b9511b23be.jpg)
![](https://www.scirp.org/html/7-6801081\1713ea04-2114-4999-aeb7-51fd1ea4b0af.jpg)
![](https://www.scirp.org/html/7-6801081\f8c25b90-de57-4b9b-910c-4eb491ee8f4d.jpg)
![](https://www.scirp.org/html/7-6801081\39070906-249e-44b0-b288-9572fb756c41.jpg)
![](https://www.scirp.org/html/7-6801081\0ba6472b-6153-4798-9c41-5fc85c51a1d1.jpg)
![](https://www.scirp.org/html/7-6801081\e3e01f56-ffd1-47e3-b3a5-1bcf45284173.jpg)
30 0 811 Divided by 7:
![](https://www.scirp.org/html/7-6801081\6a33ba3c-abbd-4f3e-a439-26986159b90d.jpg)
![](https://www.scirp.org/html/7-6801081\ec8efa2d-6949-45f7-9d8a-acbf5241af49.jpg)
![](https://www.scirp.org/html/7-6801081\3bd57e3e-e4f4-4db7-926d-78bac1b29999.jpg)
![](https://www.scirp.org/html/7-6801081\2c6a4791-4160-45b2-afcd-f573f2eb783c.jpg)
![](https://www.scirp.org/html/7-6801081\af0811df-33ff-4265-a369-f5fdc07e115d.jpg)
This result of
shows that the CPRDD algorithm has the capability of parallel processing operations in residue scaling and error corrections, i.e., any combination moduli scaling factors for Ks of moduli set {m1, m2,
, mk} can be performed simultaneously.
5. Conclusions
The arithmetic operations in the residue number system for addition, subtraction, and multiplication can be speeded up by using its parallel processing properties. However, some difficult operations, such as error detection and correction, must go through conversion or decoding processes from the residue representation to the regional binary number x. This is because the decoding technique is usually accomplished using the mixed-radix digit (MRD) or Chinese Remained Theorem (CRT), which are time consuming processes requiring hardware complexity. We proposed two algorithms for scaling and error correction without the need for lookup tables or increasing the encoding process.
The Cyclic property of the Residue-Digit Difference (CPRDD) algorithm can detect and correct errors from the RNS cyclic property. Any residue moduli set has a specific cycle length, which can be obtained from the individual residue number, difference, each pair, to a reference memory module mi. Once the cyclic length is known, then the original value x is easily found, and in turn, the errors can be detected and corrected.
The TRD (Target Race Distance) algorithm combined with CPRDD is used for scaling and for error detection and correction. The scaling results and error correction can be directly performed by these two algorithms without using MRD or CRT. Thus, the decoding process is significantly reduced, and the hardware structure is greatly simplified. Several examples are illustrated and verified for these two algorithms.