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

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
• b(z).multidot.sig(z)+c(z).multidot.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
• 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.