Method and apparatus for decoding code words protected wordwise by a non-binary BCH code from one or more symbol errors

• US 5,297,153 A
• Filed: 07/07/1992
• Issued: 03/22/1994
• Est. Priority Date: 08/24/1989
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Vries, deceased, Lodewijk B., Baggen, Constant P. M. J.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): HUA, LY
• Application Number:
  US07/911,252
• Time in Patent Office: 623 Days
• Field of Search: 371/37.1, 371/38.1, 371/39.1
• US Class Current: 714/782
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial

Abstract

A method and apparatus for decoding code words which are error protected by a non-binary BCH-code against at least one symbol error. Upon reception of an input code word a syndrome information thereof is generated under control of code defining information. From the syndrome information, a key equation is set up and solved for generating an error locator polynomial sig (z) and an error evaluator polynomial w(z). On the basis of the polynomial sig (z) and its formal derivative polynomial sig'"'"' (z), Euclid'"'"'s algorithm is employed to calculate two accessory polynomials b(z), c(z), such that b(z)sig(z)+c(z)sig'"'"'(z)=1. From these, a Lagrangian polynomial L(z) is calculated which for any inversed error location value has the associated error symbol value. The error data is then calculated by evaluating the error locator polynomial and the Lagrangian polynomial.

Claims

1. A method of decoding a series of electrical signals which represent non-binary BCH-code words each of which includes data symbols and parity symbols, the parity symbols of a code word providing protection against at least one data symbol error in such code word;

said method comprising the steps of;

a. receiving a protected code word and, in accordance with code defining information, generating error locating and error evaluating syndrome information relating to said code word;

b. processing the syndrome information in accordance with a key equation and solving said key equation so as to derive an error locator polynomial sig(z) and an error evaluator polynomial w(z);

c. deriving a formal derivative polynomial sig'"'"'(z) of the error locator polynomial sig(z), and using Euclid'"'"'s polynomial algorithm to derive from said two polynomials sig(z) and sig'"'"'(z) first and second accessory polynomials b(z) and c(z) such that

space="preserve" listing-type="equation">b(z)·

sig(z)+c(z)·

sig'"'"'(z)=1;

d. generating an intermediate polynomial L*(z) from the error locator polynomial sig(z), the formal derivative polynomial sig'"'"'(z), the error evaluator polynomial w(z), and the second accessory polynomial c(z), according to;

##EQU3## e. generating a Lagrange polynomial L(z) which is a minimal degree polynomial for inversed errors in said code word, in accordance with;

space="preserve" listing-type="equation">L(z)=L*(z)mod sig(z),

said Lagrange polynomial for any inversed error location signifying an error value at such location;

f. evaluating the error locator polynomial sig(z) so as to derive a set of error locations in said code word which, upon substitution in said Lagrange polynomial, results in a set of error values associated with said set of error locations; and

g. outputting said set of error values and the error locations associated therewith in the form of electrical signals.

2. A method as claimed in claim 1, wherein Euclid'"'"'s polynomial algorithm is also used in step (b) for solving said key equation.

3. Apparatus for decoding a series of electrical signals which represent non-binary BCH code words each of which includes data symbols and parity symbols, the parity symbols of a coded word of a code word providing protection against at least one data symbol error in such code word, said apparatus comprising:

syndrome generating means for receiving a protected code word and, in accordance with code defining information, generating a series of at least two syndrome symbols representing error locating and error evaluating syndrome information relating to such code word;

processing means for processing the series of syndrome symbols generated by said syndrome generator in accordance with a key equation and solving said key equation so as to generate an error locator polynomial sig(z) and an error evaluator polynomial w(z), said processing means comprising;

Euclid'"'"'s algorithm means for receiving said error locator polynomial sig(z) and deriving a formal derivative polynomial sig'"'"'(z) thereof which has no common divisor therewith other than unity, and applying Euclid'"'"'s polynomial algorithm to said sig(z) and sig'"'"'(z) polynomials to derive therefrom first and second accessory polynomials b(z), c(z) such that

space="preserve" listing-type="equation">b(z)·

sig(z)+c(z)·

sig'"'"'(z)=1,

and

Lagrangian algorithm means for receiving said error locator polynomial sig(z), said formal derivative polynomial sig'"'"'(z), said error evaluator polynomial w(z) and said first accessory polynomial b(z), and deriving therefrom an intermediate polynomial L*(z) given by ##EQU4## and a Lagrangian polynomial L(z) given by

space="preserve" listing-type="equation">L(z)=L*(z)mod sig(z),

said Lagrangian polynomial L(z) for any inversed error location signifying an error value at such location;

first evaluating means for receiving the error locator polynomial sig(z) from said processing means and generating therefrom a set of error locations in said protected code word;

second evaluating means for receiving the Lagrangian polynomial L(z) from said processing means and generating therefrom a set of error values associated with said set of error locations; and

output means coupled to said first and second evaluating means for outputting said set of error values and the error locations associated therewith in the form of electrical signals.

4. Decoder apparatus as claimed in claim 3, wherein said processing means uses said Euclid'"'"'s algorithm means to also solve said key equation in accordance with Euclid'"'"'s polynomial algorithm.