Reed-solomon decoder and decoding method for errors and erasures decoding
AssigneeHewlett-Packard Development Company, L.P.
InventorDavid Murray Banks
Life of this patent
Estimating the term…
Abstract
A single polynomial expander 22 is time multiplexed to produce firstly a modified syndrome polynomial T(x) and then an erasure located polynomial Λ(x). T(x) is supplied to a key equation solving unit 32 which solves the key equation to calculate an error locator polynomial σ(x) and an errata evaluator polynomial ω(x). These polynomials σ(x), Λ(x) and ω(x) form three inputs to polynomial evaluators 52–56 and a Forney block 62 for determining the location and magnitude of each symbol error and symbol erasure, allowing the received codeword to be corrected in a correction block 72. Optionally, a transform block 42 is provided to avoid unnecessary delay and improve throughput when decoding shortened codewords.
Claims14
A method for decoding of Reed-Solomon encoded data, comprising the steps of:
- receiving a codeword comprising a set of symbols, and calculating a syndrome polynomial S(x) for the received codeword;
- receiving erasure information which identifies zero or more symbols in the received codeword that have been declared as a symbol erasure;
- calculating a modified syndrome polynomial T(x) from the syndrome polynomial S(x) and then calculating an erasure locator polynomial Λ(x), each with reference to the received erasure information;
- finding an error locator polynomial σ(x) and an errata evaluator polynomial ω(x), from the modified syndrome polynomial T(x);
- determining a location and magnitude of symbol errors and symbol erasures in the received codeword, from the error locator polynomial σ(x), the erasure locator polynomial Λ(x), and the errata evaluator polynomial ω(x);
- and
- correcting the received codeword using the determined location and magnitude of symbol errors and symbol erasures.
A Reed-Solomon decoder, comprising:
- a syndrome block arranged to calculate a syndrome polynomial S(x) from a received codeword;
- an erasurelist block for receiving erasure information which identifies zero or more symbols in the received codeword as symbol erasures;
- a polynomial expander arranged to calculate a modified syndrome polynomial T (x) from the syndrome polynomial S(X) and arranged to calculate an erasure locator polynomial Λ(x), each with reference to the erasure information;
- a key equation block arranged to find an error locator polynomial σ(x) and an errata evaluator polynomial ω(x), from the modified syndrome polynomial T(x);
- a polynomial evaluator block and a Forney block arranged to determine a location and magnitude of symbol errors and symbol erasures in the received codeword, from to the error locator polynomial σ(x), the erasure locator polynomial Λ(x), and the errata evaluator polynomial ω(x);
- and
- a correction block arranged to correct the received codeword from the determined location and magnitude of each symbol error and each symbol erasure.
Dependencies are inferred from the claim text.