Back to results
US 8,413,023 B2Granted
Error-locator-polynomial generation with erasure support
AssigneeSTMicroelectronics S.r.l.
InventorsVincent Brendan Ashe, Hakan C. Ozdemir, Razmik Karabed, Richard Barndt
Life of this patent
Estimating the term…
Abstract
A system and method for correcting errors in an ECC block using erasure-identification data when generating an error-locator polynomial. In an embodiment, a ECC decoding method, uses “erasure” data indicative of bits of data that are unable to be deciphered by a decoder. Such a method may use an Berlekamp-Massey algorithm that receives two polynomials as inputs; a first polynomial indicative of erasure location in the stream of bits and a syndrome polynomial indicative of all bits as initially determined. The Berlekamp-Massey algorithm may use the erasure identification information to more easily decipher the overall codeword when faced with a error-filled codeword.
Claims23
A code error-locating module, comprising:
- a first input configured to receive a polynomial indicative of a stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- a first output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an algebraic decoding module;
- and
- a second output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an inferential decoding module.
3 more elements
An code error-locating module, comprising:
- a first input configured to receive a polynomial indicative of a stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- an output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure;
- wherein the output is coupled to a computational block that generates the polynomial using an Inversionless Blahut Dual Line algorithm.
2 more elements
An code error-locating module, comprising:
- a first input configured to receive a polynomial indicative of a stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and an output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure;
- further comprising a non-polynomial processing unit configured to generate polynomials from bits of data received at the first and second inputs;
- wherein the polynomials comprise an error-locator polynomial, an auxiliary polynomial and a gradient polynomial derived from a sector of data coded is a Reed-Solomon code.
2 more elements
A controller, comprising:
- a read channel configured to receive read data from a stream of bits, including:
- a first input configured to receive a polynomial indicative of the stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- a first output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an algebraic decoding module;
- and
- a second output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an inferential decoding module.
4 more elements
A controller, comprising:
- a read channel configured to receive read data from a stream of bits, including:
- a first input configured to receive a polynomial indicative of the stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- an output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure;
- the controller further comprising a Berlekamp Massey algorithm block coupled to the output and configured to generate the polynomial using one of the calculations comprising:
- a Forney algorithm approach, a Blahut algorithm approach, an inversionless Forney algorithm approach, an inversionless Blahut algorithm approach, and a dual-line inversionless Blahut algorithm approach.
4 more elements
A hard-disk drive system, comprising:
- a storage medium;
- a read head configured to read data from the storage medium;
- and
- a read channel coupled to the read head having an error-code correction module including:
- a first input configured to receive a polynomial indicative of the stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- a first output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an algebraic decoding module;
- and
- a second output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an inferential decoding module.
7 more elements
A receiver, comprising:
- a receiving channel;
- a read channel queue configured to receive data from the receiving channel;
- and
- a read channel coupled to the read channel queue having an error-code correction module including:
- a first input configured to receive a polynomial indicative of the stream of bits, the stream of bits including at least one error and at least one erasure;
- a second input configured to receive a polynomial indicative of erasure information about the stream of bits;
- and
- a first output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an algebraic decoding module;
- and
- a second output configured to generate a polynomial indicative of the location of the at least one error and the at least one erasure and coupled to an inferential decoding module.
7 more elements
A method, comprising:
- receiving, at a data input, a stream of bits having at least one error and having at least one erasure;
- generating a first polynomial identifying the at least one error in the stream of bits;
- generating a second polynomial identifying at least one erasure in the stream of bits;
- generating a third polynomial from the first and second polynomials;
- and
- correcting the errors and erasures in the stream of bits from an algebraic analysis of the third polynomial;
- and
- correcting the errors and erasures in the stream of bits from an inferential analysis of the third polynomial.
5 more elements
A method, comprising:
- receiving, at a data input, a stream of bits having at least one error and having at least one erasure;
- generating a first polynomial identifying the at least one error in the stream of bits;
- generating a second polynomial identifying at least one erasure in the stream of bits;
- generating a third polynomial from the first and second polynomials;
- correcting the errors and erasures in the stream of bits from an analysis of the third polynomial to generate a stream of bit without errors or erasures;
- and identifying the locations of the roots of the third polynomial by passing the third polynomial through a hard decision decoding block.
3 more elements
A method, comprising:
- receiving, at a data input, a stream of bits having at least one error and having at least one erasure;
- generating a first polynomial identifying the at least one error in the stream of bits;
- generating a second polynomial identifying at least one erasure in the stream of bits;
- generating a third polynomial from the first and second polynomials;
- correcting the errors and erasures in the stream of bits from an analysis of the third polynomial to generate a stream of bit without errors or erasures;
- and
- identifying the locations of the roots of the third polynomial by passing the third polynomial through a soft-decision decoding block.
4 more elements
Dependencies are inferred from the claim text.