Patent ID: 6122766
Filing Date: 2000-09-19
Classification: H03M

Abstract:
A Reed-Solomon decoder comprising:a first unit for finding a syndrome polynomial S(z) from a received polynomial Y(z) consisting of t-multiple error correcting Reed-Solomon codes where t is any positive integer;a second unit, having a single inverse element calculator, a single Galois multiplier, and a single Galois adder, for finding from said syndrome polynomial S(z) an error locator polynomial .sigma.(z) and an error evaluator polynomial .omega.(z) by performing a Euclidean algorithm arithmetic operation implemented by iterative use of said inverse element calculator, said Galois mulitplier, and said Galois adder, and for calculating k error values e.sub.u by dividing k error evaluation values by corresponding error locator polynomial differential values where k is any positive integer and is equal to or less than t, said calculation to find said k error values e.sub.u being also implemented by iterative use of said inverse element calculator, said Galois multiplier, and said Galois adder;a third unit for finding k roots .sub..alpha..sup.-ju of said error locator polynomial .sigma.(z) by conducting a Chien search and for providing error evaluation values obtained by substituting each one of said k roots .sub..alpha..sup.-ju in said error evaluator polynomial .omega.(z) and error locator polynomial differential values obtained by substituting each one of said k roots .sub..alpha..sup.-ju in a derivative of said error locator polynomial .sigma.(z), to said second unit; anda fourth unit for finding k error locations from said k roots .sub..alpha..sup.-ju and for finding an error-corrected polynomial W(z) by subtracting said k error values e.sub.u from said k error locations in said received polynomial Y(z), respectively;wherein said first unit forms a first pipeline stage corresponding to a first packet cycle, said second and third units form a second pipeline stage corresponding to a second packet cycle following said first packet cycle, and said fourth unit forms a third pipeline stage corresponding to a third packet cycle following said second packet cycle.