Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-05
2001-07-17
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06263471
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to error-correction coding in digital communications and storage devices. More specifically, the present invention relates to a method and apparatus for solving the key equation to decode Reed-Solomon (RS) codes utilizing the modified Euclidean algorithm to generate an error location polynomial and an error evaluation polynomial.
2. Description of the Related Art
Bose-Chaudhuri-Hocquenghem (BCH) codes form a large class of powerful random error correcting cyclic codes. Among the nonbinary BCH codes, the most important subclass is the class of Reed-Solomon codes. Reed-Solomon codes are equivalent to a BCH code with the code symbol field being the same as the field of the roots of the code generator polynomial. Reed-Solomon codes have been widely used in digital communications and data storage devices (e.g. compact discs) in such a way that induced errors are efficiently correctable. The most commonly used approach to constructing the Reed-Solomon codes is the generator polynomial construction represented by BCH codes.
The following references, incorporated by reference herein in their entireties, are helpful to achieve a general understanding of the principles of Reed-Solomon codes: (1) Stephen B. Wicker and Vijay K Bhargava,
Reed
-
Solomon
Codes and Their Applications, IEEE Press, 1994; (2) E. Dahlman, K. Shu Lin, and Daniel J. Costello, Jr.,
Error Control Coding: Fundamentals and Applications
Prentice-Hall, Inc. Englewood Cliffs, N.J., 1983.
Generally, the arithmetic of error correction codes is based on a finite (Galois) field GF(2
m
) which is the extension field of GF(2) and is generated by a field generator polynomial f(x) of degree m with binary coefficients (0,1) in GF(2). For example, assuming &agr; is a primitive element in GF(2
m
) satisfying f(&agr;)=0, then the set {1, &agr;,&agr;
2
, . . . , &agr;
m−1
} is called the standard basis that spans GF(2
m
). In field GF(2
m
), a primitive element is defined as an element that has order 2
m
−1. The order n of an element &agr; in GF(2
m
) is defined as the smallest positive integer such that &agr;
n
=1. Any finite field element &bgr; can be expressed in the standard basis as
&bgr;=&bgr;
0
+&bgr;
1
&agr;+&bgr;
2
&agr;
2
+. . . +&bgr;
m−1
&agr;
m−1
(1)
where the binary digits {&bgr;
0
, &bgr;
1
, . . . , &bgr;
m−1
} represent the standard coordinates of &bgr;.
For convenience, &bgr;
m−1
is referred to as the most significant bit (MSB) and &bgr;
0
as the least significant bit (LSB). All arithmetic operations in GF(2
m
) are performed by exclusive OR (XOR) gates which perform modulo 2 addition (modulo 2 subtraction is equivalent to addition) and AND gates which perform modulo 2 multiplication.
A Reed-Solomon code (n,k,t) over GF(2
m
) can correct up to t error symbols, where GF(2
m
) is a finite field with 2
m
m-bit symbols, n is the total number of symbols in a code word, k is the number of information symbols in a code word, n−k is the number of check symbols in a code word and t=(n−k)/2.
The RS code is defined by a code generator polynomial G(x) of degree 2t with {1, &agr;, &agr;
2
, . . . , &agr;
2t−1
} as its roots. Any legal code word, treated as a polynomial of degree n−1, must be divided by G(x).
The following table represents the RS codes in the digital television standard of the United States Advanced Television Systems Committee (ATSC) and the Standard of Digital Video Broadcasting by Satellite (DVB-S) of the European Telecommunications Standard Institute (ETSI), where m=8 (eight-bit symbol=one byte).
ATSC
DVB-S
k
187
188
n
207
204
t
10
8
m
8
8
A brief description of the conventional error correcting procedure with regard to a Reed-Solomon code (n,k,t) will be given below. In this description, we assume that R
i
, i=0,1,2, . . . ,n−1, are the n received error-corrupted m-bit symbols.
Step (
1
): Generate 2t syndrome values
s
i
=
∑
j
=
0
n
-
1
R
j
(
α
i
)
j
,
for
0
,
1
,
2
,
…
,
2
t
-
1
(
2
)
and then, based on these syndrome digits, form a syndrome polynomial S(x) of degree 2t−1 representing the received codeword
S
(
x
)
=
∑
i
=
0
2
t
-
1
s
i
x
i
(
3
)
Step (
2
): Solve the key equation
&OHgr;(
x
)=&Lgr;(
x
)
S
(
x
)mod
x
2t
(4)
using the modified Euclidean algorithm to generate an error location polynomial &Lgr;(x) of degree t and an error evaluation polynomial &OHgr;(x) of degree t−1;
Step (
3
): Determine the roots of &Lgr;(x) by the Chien search method, each of which indicates an error location. If &agr;
−&mgr;
is a root of &Lgr;(x), there is an error in the received symbol R
&mgr;
and the associated error value is given by the Forney algorithm
&OHgr;(&agr;
−&mgr;
)/&Lgr;
odd
(&agr;
−&mgr;
) (5)
where &Lgr;
odd
(x) is the polynomial of preserving the odd terms of &Lgr;′(x), the terms associated with {x,x
3
,x
5
, . . .}.
Step (
4
): Correct the errors by subtracting the error magnitudes from the received codeword in the associated error locations.
It should be noted that, as used herein, the term “received codeword” refers to a codeword that is either received through a communication medium or reproduced from a storage medium.
The modified Euclidean algorithm for solving the key equation is mathematically described as follows, starting with S(x) generated in accordance with step (
1
) above:
Initialization:
A
(
x
)=
S
(
x
),
A′
(
x
)=1,
B
(
x
)=
x
2t
, B
′(
x
)=0 (6)
Euclidean Iteration:
if deg_A(x)<deg_B(x) then
swap A(x) and B(x)
swap A′(x) and B′(x)
endif
Q=a
lead
/b
lead
(7)
A
(
x
)←
A
(
x
)−
Q·B
(
x
)·
x
deg
—
A(x)−deg
—
B(x)
(8)
A
′(
x
)←
A
′(
x
)−
Q·B
′(
x
)·
x
deg
—
A(x)−deg
—
B(x)
(9)
if deg A(x)<t, then
algorithm finished
&OHgr;(
x
)=
A
(
x
) (10)
&Lgr;(
x
)=
A
′(
x
) (1)
endif
where a
lead
represents the leading coefficient of A(x), b
lead
represents the leading coefficient of B(x), and “deg” means the degree of polynomial.
The notation ← means “simultaneous assignment upon Euclidean iteration.”
As to Q, it is typically obtained by computing the multiplication of
Q=a
lead
·INV
(12)
where
INV=
(
b
lead
)
−1
(13)
and the value of INV is typically generated by a look-up table.
A brief description of prior art hardware implementations of a key equation solver for Reed-Solomon codes is given below.
Conventional key equation solvers using parallel multipliers are illustrated by, for example, U.S. Pat. Nos. 4,873,688, 5,170,399, 5,396,502, 5,428,628, 5,442,578, and 5,570,378. In these systems, generally, a global m-bit parallel bus is used to transmit the m-bit quotient value Q, and m-by-m parallel multipliers are used to perform the multiplication function. The parallel multiplier operates in parallel-in parallel-out (PIPO) mode, completes its operation in one clock, and requires m
2
AND gates and at least m
2
XOR gates. Thus, these systems have the disadvantage of incurring large gate counts and requiring an m-bit quotient bus.
Systolic implementations of the key equation solver using parallel multipliers are disclosed in, e.g., U.S. Pat. Nos. 4,958,348 and 5,323,402. In these systems, a set of registers is used for storing A(x), A′(x), B(x), B′(x), INV, Q, deg_A(x), and deg_B(x), while another set of registers is used to pipeline data transfer and perform arithmetic operations. Thus, these systems have the disadvantage of needing extra registers to pipeline data transfer and processing.
In the prior art discussed above, m-by-m parallel multipliers are implemen
Baker Stephen M.
Industrial Technology Research Institute
Stevens Davis Miller & Mosher LLP
LandOfFree
Method and apparatus for decoding an error correction code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for decoding an error correction code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for decoding an error correction code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443218