Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-05-07
2001-01-16
Baker, Stephen (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06175945
ABSTRACT:
FIELD OF THE INVENTION
This invention pertains to a type of Reed Solomon decoder that decodes Reed Solomon encoded signals used for error correction in recording media and in digital transmission.
BACKGROUND OF THE INVENTION
The Reed Solomon code (referred to as RS code hereinafter) has a high coding efficiency and a good adaptivity to error bursts, and is hence used mainly as the external code for recording media and in digital transmission.
For example, the error correction code adopted for compact discs is called CIRC correction code (Cross Interleaved Reed Solomon code), and it is a product of two RS codes combined with the interleave technique. It adopts RS (
28
,
24
) as its external code, and RS (
32
,
28
) as its internal code. They are called the C
2
code and C
1
code, respectively. For all of these codes, each RS code symbol is constructed of 1 byte, and each RS code block contains a 4-byte parity check string.
Usually, for the RS code, correction of t symbol can be performed with a check string of 2t symbols. For correction of t symbols, it is necessary to know t error positions and t error values corresponding to these errors, respectively. For the RS code, when t errors are generated, by performing the syndrome operation on the decoder side, 2t independent linear equations are obtained. When these equations are solved, there are 2t unknown parameters, and it is possible to derive the aforementioned t error positions and the aforementioned t error values corresponding to said error positions, respectively.
On the other hand, as the configuration of the product code, such as CIRC code, is handled, by adding the erasure flag to the RS-encoded block that cannot be corrected and the relatively high RS-encoded block that can be corrected in the internal RS decoding for the internal code, it is possible to correct the erasure error in the external RS decoding corresponding to the external code. The erasure symbol of the internal code with the erasure flag added to it is distributed to plural outer RS-encoded blocks by means of de-interleaving. In the erasure error correction, it is assumed that errors exist in the aforementioned erasure symbol, and the simultaneous equations obtained by the syndrome operation are solved. In solving the equations with the error positions taken as known, it is possible to derive up to 2t error values. That is, for the RS code having a check string of 2t symbols, it is possible to perform correction for errors of up to 2t symbols by executing the erasure error correction.
In the following, explanation will be made on the erasure error correction method with reference to the CIRC code as an example.
In the case of CIRC code, by adding the erasure flag to the RS decoding (C
1
decoding) of the C
1
code as the internal code, it is possible to perform the erasure error correction through the RS decoding (C
2
decoding) of the C
2
code as the external code. As both C
1
code and C
2
code have t=2, the C
1
decoding allows up to 2 bytes of correction, and the erasure error correction of the C
2
decoding allows up to 4 bytes of correction. Syndromes s
0
-s
3
in the C
2
decoding and error values e
1
-e
4
are derived as follows.
Formula (1) below shows the code-generating polynomial Ge(x) of the CIRC code.
[
Mathematical
Formula
1
]
Ge
(
x
)
=
∏
j
=
o
3
(
x
+
α
j
)
(
1
)
Here, &agr; represents the primitive element of the Galois field. In this case, s
0
-s
3
obtained through the syndrome operation from the input series are related to said x
1
-x
4
and e
1
-e
4
by following Formula 2.
[
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
·
o3
+
x4
3
·
e4
(
2
)
Here, symbol “·” represents multiplication over the Galois field, and symbol “+” represents addition over the Galois field. In the following, the mathematical operations of the elements of certain Galois fields will be shown.
Simultaneous Formulas 2 listed above are solved, and error values e
1
-e
4
are derived as follows as the unknown values.
First of all, e
4
is obtained as represented by following Formula 3.
[
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
)
(
3
)
e
4
obtained here is substituted into said Formula 2 to reconstruct the simultaneous formulas made of three formulas. That is, by noticing the fact that addition and subtraction are the same for the Galois field used in the CIRC code, correction is performed as shown in following Formula 4, and said Formula 2 as simultaneous equations are transformed to following Formula 5.
[Mathematical Formula 4]
s
0
←s
0
+e
4
s
1
←s
1
+x
4
·e
4
s
2
←s
2
+x
4
2
·e
4 (4)
[
Mathematical
Formula
5
]
s0
=
e1
+
e2
+
e3
s1
=
x1
·
e1
+
x2
·
e2
+
x3
·
e3
s2
=
x1
2
·
e1
+
x2
2
·
e2
+
x3
2
·
e3
(
5
)
Solution of the simultaneous formulas is the method often adopted when the sequence is derived by manual calculation. Then, Formulas 5, as simultaneous equations, are solved to derive e3, obtaining following Formula 6.
[
Mathematical
Formula
6
]
e3
←
s2
+
(
x1
+
x2
)
·
s1
+
x1
·
x2
·
s0
(
x3
+
x1
)
·
(
x3
+
x2
)
(
6
)
By performing the same correction, said Formulas 5 as simultaneous equations are transformed to following Formulas 7 and 8.
[Mathematical Formula 7]
s
0
←s
0
+e
3
s
1
←s
1
+x
3
·o
3 (7)
[
Mathematical
Formula
8
]
s0
=
e1
+
e2
s1
=
x1
·
e1
+
x2
·
e2
(
8
)
Also, Formulas 8 as simultaneous equations are solved to give e
2
, and following Formula 9 is obtained.
[
Mathematical
Formula
9
]
e2
←
s1
+
x1
·
s0
x2
+
x1
(
9
)
Then, the obtained e
2
is substituted into said Formulas 8, giving the following Formula 10.
[Mathematical Formula 10]
e
1
←s
0
+e
2 (10)
In this way, errors e
1
-e
4
are derived in sequence.
In the aforementioned method, in order to distinguish the original information and the operation performed during the applied decoding operation, symbols “=” and “←” are used to indicate the difference. That is, Formulas 3, 4, 6, 7, 9 and 10 correspond to the applied decoding operation, which requires at least 23 rounds of addition, 17 rounds of multiplication, and 3 rounds of division over the Galois field.
On the other hand, when the erasure error correction is not carried out, it is possible to perform correction up to 2 bytes in the C
2
decoding (double error correction). In this case, error values e
1
and e
2
and error positions x′
1
and x′
2
are derived from syndromes s
0
-s
3
.
The aforementioned is the processing procedure of the decoding operation in the case of quadruple erasure error correction, that is, when the number of the erasure positions is 4.
In the following, a conventional Reed Solomon decoder will be explained.
FIG. 9
is a diagram illustrating the configuration of conventional Reed Solomon decoder
1
.
As shown in
FIG. 9
, Reed Solomon decoder
1
has memory block
2
, bus I/F block
3
, and decoding operation processing unit
4
.
Memory block
2
has cache memories
5
,
6
and switches
7
and
8
.
Switch
7
outp
Baker Stephen
Petersen Bret J.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Reed-Solomon decoder 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 decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-Solomon decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531053