Real-time BCH error correction code decoding mechanism
First Claim
1. A method of correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2p) and a selected generator polynomial, said method comprising the steps of:
- A. generating error syndromes corresponding to a given data code word containing errors;
B. using said error syndromes, generating an error evaluator polynomial Φ
(x) and an error locator polynomial δ
(x) of the form δ
(x)=1+δ
even (x)+δ
odd (x), where δ
even (x) and δ
odd (x) are the even- and odd- terms of δ
(x), respectively;
C. for each successive value of x, which are each elements of GF(2p) corresponding to possible locations of errors in the code word, simultaneously substituting x into expressions for the error evaluator polynomial, Φ
(x), and δ
even (x) and δ
odd (x);
D. evaluating said expressions;
E. substituting the results of step D into the error locator polynomial and an error value formula;
F. evaluating said error locator polynomial and said error value formula to obtain the location of a possible error in the code word and a corresponding error value, respectively;
G. (a) if said error locator polynomial is equal to one for a given x, indicating that there is an error at the code word location corresponding to x, correcting the error with the corresponding calculated error value, or (b) if said error locator polynomial is not equal to one for a given x, indicating that there is no error at the code word location corresponding to x, disregarding the corresponding calculated error value; and
H. repeating steps C-G for all remaining values of x corresponding to possible error locations in the code word.
5 Assignments
0 Petitions
Accused Products
Abstract
The invention simultaneously calculates error locations and associated error values by solving the error locator polynomial equation re-written as:
1=δ.sub.even (x)+δ.sub.odd (x)
where δeven (x) and δodd (x) are the even- and odd-power terms of the error locator polynomial. A first value of x, xa1, is simultaneously inserted into the expression δeven (x) and δodd (x) and also into an error value polynomial Φ(x). Next, while the error locator equation is evaluated at the calculated values of δeven (xa1) and δodd (xa1) to determine if xa1 is a solution, the now known values of the error evaluator polynomial Φ(xa1) and δodd (xa1) are substituted into an error value formula: ##EQU1## Thus as soon as an error location is found, the error value, va1, associated with that location is also known. The error can then be quickly corrected. Next, these calculated terms are used to calculate similar expressions for a next value of x, xa2. If xa2 is a solution, the error value va2 which was simultaneously calculated for xa2 is used to correct the error. If xa2 is not a solution, the calculated error value is ignored. The expression δodd (x), δeven (x) and the polynominal Φ(x) are similarly evaluated for each of the remaining values of x.
126 Citations
9 Claims
-
1. A method of correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2p) and a selected generator polynomial, said method comprising the steps of:
-
A. generating error syndromes corresponding to a given data code word containing errors; B. using said error syndromes, generating an error evaluator polynomial Φ
(x) and an error locator polynomial δ
(x) of the form δ
(x)=1+δ
even (x)+δ
odd (x), where δ
even (x) and δ
odd (x) are the even- and odd- terms of δ
(x), respectively;C. for each successive value of x, which are each elements of GF(2p) corresponding to possible locations of errors in the code word, simultaneously substituting x into expressions for the error evaluator polynomial, Φ
(x), and δ
even (x) and δ
odd (x);D. evaluating said expressions; E. substituting the results of step D into the error locator polynomial and an error value formula; F. evaluating said error locator polynomial and said error value formula to obtain the location of a possible error in the code word and a corresponding error value, respectively; G. (a) if said error locator polynomial is equal to one for a given x, indicating that there is an error at the code word location corresponding to x, correcting the error with the corresponding calculated error value, or (b) if said error locator polynomial is not equal to one for a given x, indicating that there is no error at the code word location corresponding to x, disregarding the corresponding calculated error value; and H. repeating steps C-G for all remaining values of x corresponding to possible error locations in the code word. - View Dependent Claims (2, 3, 4)
-
-
5. An apparatus for correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2p), comprising:
-
A. an error syndrome generator for generating error syndromes; B. a polynomial generator connected to receive the error syndromes for generating, using the error syndromes, an error evaluator polynomial Φ
(x) and an error locator polynomial δ
(x) of the form δ
(x)=1+δ
even (x)+δ
odd (x), where δ
even (x) and δ
odd (x) are the even- and odd- terms of δ
(x), respectively;C. code word error correction means for locating the errors in the code word and correcting them, said code word error correction means including; - View Dependent Claims (8)
-
-
6. first substitution means for, for each successive value of x, which are elements of GF(2p) corresponding to possible error locations in the code word, simultaneously substituting x into expressions for the error evaluator polynomial Φ
- (x), δ
even (x) and δ
odd (x);2. first evaluating means for evaluating said expressions at the substituted values of x; 3. second substitution means for substituting the values of the evaluated expressions into the error locator polynomial and an error value formula; 4. second evaluating means for evaluating said error locator polynomial and said error value formula to obtain the locations of errors in the code word and corresponding error values; and 5. correcting means for (1) if said error locator polynomial is equal to one, correcting the error at the code word location corresponding to x using the calculated error value, or (2) if said error locator polynomial is not equal to one, disregarding the calculated error value; 6. - View Dependent Claims (9)
- (x), δ
-
7. repeating steps 1-5 for all remaining values of x corresponding to
Specification