US4866716A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Real-time BCH error correction code decoding mechanism
Assignee: Maxtor Corp
•
Filing: 1988-01-22
•
Granted: 1989-09-12
•
Expires: 2008-01-22
Abstract
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, x a1 , 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 (x a1 ) and δ odd (x a1 ) to determine if x a1 is a solution, the now known values of the error evaluator polynomial Φ(x a1 ) and δ odd (x a1 ) are substituted into an error value formula: ##EQU1## Thus as soon as an error location is found, the error value, v a1 , 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, x a2 . If x a2 is a solution, the error value v a2 which was simultaneously calculated for x a2 is used to correct the error. If x a2 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.
Inventors
- 👤 Lih-Jyh Weng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:06
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
278 words
A method of correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2 p ) 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(2 p ) 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.
Claim 2
Independent Claim
278 words
A method of correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2 p ) 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(2 p ) 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.
Claim 3
Dependent Claim
89 words
The method for correcting errors in claim 1 wherein: A. if the generator polynomial has x 1 as a root, said error value formula for determining the value of an error, v, at the code word location corresponding to x is: ##EQU8## and B. if the generator polynomial does not have x 1 as a root, said error value formula for determining the value of an error, v, at the code word location corresponding to x is: ##EQU9## where C is a constant which depends on the generator polynomial.
Claim 4
Dependent Claim
22 words
The method for correcting errors in claim 2 wherein the error correction code used to encode the data is a Reed-Solomon code.
Claim 5
Dependent Claim
203 words
The method for correcting errors in claim 2 wherein said error evaluation polynomial and error locator expressions for determining the location and value of errors in a data code word are evaluated using an iterative evaluation method comprising the steps of: A. calculating the values of the terms of the two error locator expressions δ even (x) and δ odd (x) and the values of the terms of the error evaluator polynomial Φ(x) for a first value of x corresponding to a given code word location; B. storing the calculated value of each term of the error locator expressions and the error evaluator polynomial; C. substituting the stored values into the error locator polynomial and the error value formula to determine the locations and values of errors in the code word corresponding to x; D. to try a next value of x corresponding to another possible error location, multiplying each stored value by a constant B n , where: i. x * B is equal to the next value of x to be tried, and ii. n is the exponent of the variable in the term having that value; and E. repeating steps B-D for each x corresponding to a possible error location.
Claim 6
Independent Claim
110 words
An apparatus for correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2 p ), 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:
Claim 7
Independent Claim
110 words
An apparatus for correcting data which is encoded into code words using a BCH error correction code based on Galois Field GF(2 p ), 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:
Claim 8
Dependent Claim
158 words
first substitution means for, for each successive value of x, which are elements of GF(2 p ) 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.
Claim 9
Dependent Claim
158 words
first substitution means for, for each successive value of x, which are elements of GF(2 p ) 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.
Claim 10
Dependent Claim
11 words
repeating steps 1-5 for all remaining values of x corresponding to
Claim 11
Dependent Claim
11 words
repeating steps 1-5 for all remaining values of x corresponding to
Claim 12
Dependent Claim
79 words
possible error locations in the code word. 6. The apparatus for correcting errors in claim 5 wherein said error value formula into which the first substitution means substitutes the calculated expression value is ##EQU10## if the generator polynomial has x 1 as the lowest root the error value formula, or ##EQU11## if the generator polynomial does not have x 1 as the lowest root the error value formula, where C is a constant which depends on the generator polynomial.
Claim 13
Dependent Claim
151 words
The apparatus for correcting errors in claim 6, wherein said first evaluating means includes: 1. calculating means for calculating the values of the terms of the two error locator expressions δ even (x) and δ odd (x) and the values of the terms of the error evaluator polynomial for a first value of x corresponding to a given code word location; 2. storage means for storing the calculated values of each of the terms of the error locator expressions and the error evaluator polynomial and applying said values to said second substitution means; and 3. multiplication means for calculating a next value of x corresponding to another possible error location by multiplying each of the stored values by a constant where: i. x * B is equal to the next value of x to be tried, and ii. n is the exponent of the variable in the term having that value.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-09-11 | 1993-03-13 | 1993-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-09-11 | 1997-03-13 | 1997-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-09-11 | 2001-03-13 | 2001-09-12 | $7700.00 | Window Closed / Lapsed |