Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-05-13
2001-05-15
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000, C714S752000
Reexamination Certificate
active
06233710
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a Reed-Solomon decoding device that decodes Reed-Solomon encoded signals that are used for error correction and coding for recording media and digital transmission.
BACKGROUND OF THE INVENTION
The Reed-Solomon Code (hereinafter, RS code) is mainly used for recording media and external coding of digital transmissions, from the appropriateness in relation to the quality of the encoding efficiency and the error burst.
For example, the error correction code that is used with a compact disc is called the CIRC correction code (cross interleaved Reed-Solomon code); this is a product code that is combined with the interleave method. RS (28, 24) code is used as the external code, and RS (32, 28) code as the internal code, and they are called the C2 code and the C1 code, respectively. In either code, the RS encoding unit is constructed of 1 byte, and a single RS decoding block contains a parity check string of 4 bytes.
Generally, the RS code is a check string of 2t nits, and correction of t units is possible. In the correction of t units, it is necessary to know the t units of error positions, and the value of t units of error corresponding to the respective errors. The RS coding obtains an independent linear formula for 2t units by performing a syndrome calculation at the decoding side in relation to the generation of t units of error. By solving this formula, the error position for the above-mentioned t units, which is an unknown number of 2t units, and the value of the error of the above-mentioned t units corresponding to the respective error positions, can be found.
On the other hand, as for adopting a construction of a product code like the CIRC code, by applying a erasure flag to the RS-encoded block for which correction could not be done at the internal RS decoding in relation to the internal code and the RS-encoded block in which the possibility of error correction is comparatively high, erasure error correction becomes possible in the external RS decoding corresponding to the external code. The erasure units for the internal code to which the erasure flags were applied are dispersed in multiple external RS-encoded blocks by means of deinterleaving. In the erasure error correction, by assuming that there is an error present in the above-mentioned erasure unit, the simultaneous formulas that are obtained from the syndrome calculations are solved. Since the error positions are already known, the value of the error for the maximum 2t can be solved. In other words, it is possible to error-correct a maximum 2t units by executing the erasure error correction for the RS codes having check strings of 2t units.
The method for the erasure error correction is explained by offering an example of the CIRC code.
In the case of the CIRC code, by applying a erasure flag in the RS decoding (C1 decoding) for the C1 code, which is the internal code, the erasure error correction is possible in the RS decoding (C2 decoding) for the C2 code, which is the external code. Because t=2 in both the C1 code and the C2 code, in C1 coding, correction of a maximum 2 bytes is possible, but in the erasure error correction of C2 decoding, the correction of a maximum of 4 bytes is possible. The syndrome s
0
to s
3
and the error value e
1
to e
4
in that C2 code can be found as follows.
The code-generating polynomial expression Ge(x) for the CIRC code is shown by Formula 1 below.
[
Mathematical
Formula
1
]
Ge
(
x
)
=
∏
j
=
0
3
(
x
+
a
j
)
[
1
]
Here, &agr; is the primitive element for the Galois field. At this time, s
0
to s
3
obtained by means of the syndrome calculations from the input string have the relationship shown by the following Formula 2 between the above-mentioned x
1
to x
4
, and e
1
to e
4
.
[
Mathematical
Formula
2
]
s0
=
e1
+
e2
+
e3
+
e4
s1
=
x1
·
e1
+
x2
·
e2
+
x3
·
e3
+
x4
·
e4
s2
=
x1
2
·
e1
+
x2
2
·
e2
+
x3
2
·
e3
+
x4
2
·
e4
s3
=
x1
3
·
e1
+
x2
3
·
e2
+
x3
3
·
e3
+
x4
3
·
e4
Here, the symbol “·” shows multiplication over the Galois field, and the symbol “+” shows addition over the Galois field. Below, as for the four basic mathematical operations between the elements of a given Galois field, it has been decided to show the calculations for that Galois field.
If the error values e
1
to e
4
, which are unknown numbers, are found by solving the simultaneous formulas, the above-mentioned Formula 2 becomes as follows.
First, e
4
is obtained as Formula 3 below.
[
Mathematical
Formula
3
]
e4
←
s3
+
(
x1
+
x2
+
x3
)
·
s2
+
(
x1
·
x2
+
x2
·
x3
+
x3
·
x1
)
·
s1
+
x1
·
x2
·
x3
·
s0
(
x4
+
x1
)
·
(
x4
+
x2
)
·
(
x4
+
x3
)
A simultaneous formula is reconstructed by substituting this e
4
obtained in the above-mentioned Formula 2. In other words, as for the Galois field that was used in the CIRC code, by correcting it as in Formula 4 below, noting the fact that the addition and the subtraction are the same, the simultaneous formula of the above-mentioned Formula 2 is transformed to Formula 5 below.
[
Mathematical
Formula
4
]
s0
←
s0
+
e4
s1
←
s1
+
x4
·
e4
s2
←
s2
+
x4
·
e4
[
Mathematical
Formula
5
]
s0
=
e1
+
e2
+
e3
s1
=
x1
·
e1
+
x2
·
e2
+
x3
·
e3
s2
=
x1
2
·
e1
+
x2
2
·
e2
+
x3
2
·
e3
As for this, the solving of the simultaneous formula is a method that is frequently used when finding the sequence in manual calculations. If e
3
is found by solving the simultaneous formula of Formula 5, it becomes like Formula 6 below.
[
Mathematical
Formula
6
]
e3
←
s2
+
(
x1
+
x2
)
·
s1
+
x1
·
x2
·
s0
(
x3
+
x1
)
·
(
x3
+
x2
)
By executing the corrections in the same manner, the simultaneous Formula of the above-mentioned Formula 5 is modified as in Formulas 7 and 8 below.
[
Mathematical
Formula
7
]
s0
←
s0
+
e3
s1
←
s1
+
x3
·
e3
[
Mathematical
Formula
8
]
[
7
]
s0
=
e1
+
e2
s1
=
x1
·
e1
+
x2
·
e2
[
8
]
Also, if e
2
is found by solving the simultaneous formula of Formula 8, it becomes Formula 9 below.
[
Mathematical
Formula
9
]
e2
←
s1
+
x1
·
s0
x2
+
x1
Next, Formula 10 below is obtained by substituting this e
2
that was found in the above-mentioned Formula 8.
[Mathematical Formula 10]
e
1←
s
0+
e
2
In this manner, the error values e
1
to e
4
can be found sequentially.
In the above-mentioned method, in order to distinguish between those which were originally held as information, and the calculation operations that were conducted at the time of the actual decoding, the symbols “=” and “6” are used in different ways. In other words, the Formulas corresponding to the actual decoding calculations are Formulas 3, 4, 6, 7, 9, and 10, and in the Galois field, at least 23 additions, 17 multiplications, and 3 divisions are necessary.
On the other hand, in the event the erasure error correction is not conducted, corrections (double error corrections) can be done for a maximum of 2 bytes in the C2 decoding. At this time, the error values e
1
, e
2
, and the error positions X′
1
, X′
2
are found from the syndromes s
0
to s
3
.
Above, the quadruple erasure error correction, in other words, the number of erasure positions, is the decoding calculation processes for 4 cases.
A flow chart for the erasure error correction process according to the method u
De'cady Albert
Lin Samuel
Petersen Bret J.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Reed-Solomon decoding device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reed-Solomon decoding device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon decoding device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2527645