Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-05-28
2002-10-15
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06467063
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a Reed Solomon coding apparatus and a Reed Solomon coding method for correcting multiple errors, which are widely used in error correction of digital signal processing.
BACKGROUND OF THE INVENTION
As codes which enable multiple error correction for storage information in a variety of mass storages, transmission information in high-speed communication, and the like, Reed Solomon codes are widely used.
The Reed Solomon code is a code on a Galois field which contains roots &agr; of P(x) (primitive polynomial)=0 as primitive elements, and is known as one type of block error-correcting code.
Consider a Reed Solomon code of a code length n=2
m
−1 assuming that t is the number of errors to-be-corrected, m is a degree of an extended field, and primitive elements of a Galois field GF (2
m
) are a &agr;
0
, &agr;, . . . &agr;
2m−2
. According to this code, m bits is a processing unit, i.e., a symbol. The amount of original information is (n−2t) symbols. In description below, suppose that m=8 and one symbol is represented as 8 bits (1 byte). A receiving word of one packet is composed of n symbols. The number of symbols “n” is called a code length. When t=8, the Reed Solomon code is capable of correcting eight symbol errors. The original information in the receiving word, i.e., the (n−2t) symbols are called an information word and 2t symbols added to correct errors are called a check word.
The Reed Solomon coding apparatus is adapted to add the check word of 2t symbols to the information word of (n−2t)symbols so as to generate a codeword comprising a symbol sequence of a code length n.
A description will be given of an algorithm for a coding process of the Reed Solomon code (hereinafter referred to as an RS code).
First, a primitive polynomial will be described as a first element for determining the RS code.
In case of m=8, 255 primitive elements, i.e., &agr;
0
-&agr;
254
are present in the Galois field, and vector values of respective primitive elements are determined by a primitive polynomial P(z).
In general, when m=8, the primitive polynomial P(x) is expressed as:
P
(
x
)=
x
5
+x
4
+x
3
+x
2
+1.
In this case, vector values for the respective primitive elements are:
&agr;
0
=00000001, &agr;
1
=00000010, &agr;
2
=00000100,
&agr;
3
=00001000, &agr;
4
=00010000, &agr;
5
=00100000,
&agr;
6
=1000000, &agr;
7
=10000000, &agr;
8
=00011101,
&agr;
9
00111010 . . . .
Here, how these vector values are determined will be explained. When m=8, each of the vector values is represented as 8 bits. In &agr;
0
to &agr;
7
, as a degree increases one by one, bit-shifting is performed to the left. &agr;
8
is calculated by assigning &agr; to the primitive polynomial P(x) and assuming that P(&agr;)=0, and this is expressed as:
P
(&agr;)=&agr;
8
+&agr;
4
+&agr;
3
+&agr;
2
+1=0
Since addition and subtraction are the same in Galois operation, P(&agr;)=&agr;
8
+&agr;
4
+&agr;
3
+&agr;
2
+1=0 is expressed as:
&agr;
8
=&agr;
4
+&agr;
3
+&agr;
2
+1
Therefore, &agr;
8
=00011101, and &agr;
9
is obtained by bit-shifting &agr;
8
to the left.
Thus, the primitive elements have vector values determined according to a rule, where bit-shifting is performed to the left as the degree increases, and when the most significant bit is “1”, the corresponding vector value is bit-shifted to the left, and then &agr;
m
&agr;
8
=00011101 is added to generate a vector value of a subsequent degree. It should be noted that addition in Galois operation corresponds to an exclusive-OR(XOR) addition of respective vector values.
The RS code is a code on the Galois field, and is determined by operation using primitive elements (255 primitive elements when m=8). Hence, if each of the primitive elements has different vector values, then different codes are obtained even if the same operational procedure is used. In other words, if different primitive polynomials are used, different RS codes are obtained.
Subsequently, a description will be given of a generator polynomial as a second element for determining the RS code.
The RS code for correcting “t” errors is generated in the following way. Express (n−2t) original information as input data in information polynomial form, and find a remainder polynomial resulting from dividing the information polynomial by a generator polynomial shown below. Then, to the (n−2t) original information data (information word), the check word of the 2t symbols calculated as the remainder polynomial is added to generate the RS code of the code length n.
The general form of the generator polynomial for the RS code for correcting the multiple errors (n≦2
m
−1, the number of errors to-be-corrected is t, and a minimum distance dmin≦2t+1) is:
G
(
x
)
=
(
x
-
α
n
)
(
x
-
α
1
)
(
x
-
α
2
)
…
(
x
-
α
2
t
-
1
)
=
∏
i
=
0
2
t
-
1
(
x
-
α
1
)
=
x
2
t
+
c
2
t
-
1
x
2
t
-
1
+
c
2
t
-
2
x
2
t
-
2
+
c
2
t
-
3
x
2
t
-
3
+
…
c
2
x
2
+
c
1
x
+
c
0
(
1
)
“k” information data, a
k−1
a
k−2
. . . a
2
, a
1
, a
0
are expressed by means of the following information polynomial:
I
(
x
)=a
k−1
x
n−1
+a
k−2
x
n−2
+ . . . +a
1
x
2t+1
+a
0
x
2t
. . . (2)
The expression (2) is divided by the expression (1), resulting in a remainder polynomial R(x), which becomes a check polynomial, “2t” coefficients of which become the check word. This is summarized as:
I(x)=Q(x)G(x)+R(x) (I(x): information polynomial, G(x): generator polynomial, Q(x): quotient polynomial, R(x): remainder polynomial)
In the Galois operation, addition and subtraction are the same as described above, and therefore,
R
(
x
)=
Q
(
x
)
G
(
x
)+
I
(
x
)=:
b
2t−1
x
2t−1
+b
2t−t
x
2t−2
+b
2t−3
x
2t−3
+ . . . +b
1
x+b
0
Therefore, the whole coded polynomial X (x) is expressed as:
X
(
x
)=
I
(
x
)+
R
(
x
)=a
k−1
x
n−1
+a
k−2
x
n−2
+ . . . +a
1
x
2t+1
+a
0
x
2t
+b
2t−1
x
2t−1
+b
2t−t
x
2t−t
+ . . . +b
1
x+b
0
. . . (3)
In this expression (3), n coefficients, i.e., a
k−1
, a
k−2
, a
2
, a
1
, a
0
, b
2t−2
, . . . b
1
, b
0
become the RS code.
As concerns an initial value “i” of the generator polynomial (1), in case of an RS code for transmission in a communication system, i=0 is generally adopted, wile in case of an RS code in a disc system, i=120 is generally adopted.
Depending upon the initial value “i”, coefficients C of an expanded expression (1) vary, and thereby coefficients b of the remainder polynomial vary. Hence, like the primitive polynomial, when a different generator polynomial is used, a different RS code is generated even if the same procedure is used.
Subsequently, a description will be given of implementation of an RS coding algorithm as hardware.
The RS code is composed of the information word comprising coefficients of the information polynomial and the check word comprising coefficients of the remainder polynomial obtained by dividing the information polynomial by the generator polynomial.
When finding the remainder polynomial, in order to sequentially divide the coefficients of the information polynomial by the coefficients of the generator polynomial, it is necessary that multiplication and addition be performed using the coefficients of the information polynomial and the coefficients of respective degre
De'cady Albert
Lamarre Guy
Matsushita Electric - Industrial Co., Ltd.
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Reed Solomon coding apparatus and Reed Solomon coding method 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 coding apparatus and Reed Solomon coding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed Solomon coding apparatus and Reed Solomon coding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2942917