ERROR AND ERASURE DECODING APPARATUS AND METHOD

• US 20140281839A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Kwok, Zion S.
• Granted Patent: US 9,054,742 B2
• Time in Patent Office: Days
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey 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/159 Remainder calculation, e.g. for encoding and syndrome calculation

Abstract

Embodiments of apparatus and methods for decoding errors and erasures are described. A codeword may have errors and erasures. In embodiments, an apparatus may include a syndrome calculator configured to generate partial syndromes of the codeword, an erasure locator configured to generate an erasure locator polynomial, and a syndrome modifier configured to generate modified partial syndromes based at least in part on the partial syndromes and the erasure locator polynomial. The apparatus may further include an error locator configured to generate an error locator polynomial using the modified partial syndromes, for error and erasure decoding of the codeword. Other embodiments may be described and/or claimed.

Claims

1. An apparatus, comprising:

a syndrome calculator configured to generate a plurality of partial syndromes of a codeword;

an erasure locator configured to generate an erasure locator polynomial for the codeword;

a syndrome modifier, coupled with the syndrome calculator and the erasure locator, configured to generate modified partial syndromes for the codeword based at least in part on the partial syndromes and the erasure locator polynomial for the codeword; and

an error locator, coupled with the syndrome modifier, configured to generate an error locator polynomial using the modified partial syndromes, for error and erasure decoding of the codeword.

2. The apparatus according to claim 1, wherein the error locator is configured to use a Berlekamp-Massey algorithm to generate the error locator polynomial.

3. The apparatus according to claim 2, wherein the modified partial syndromes comprise no more than (2t−

B) partial syndromes, wherein t is a number of correctable errors, and B is a number of erasures.

4. The apparatus according to claim 3, wherein B is greater than t.

5. The apparatus according to claim 1, wherein the apparatus is a memory controller.

6. The apparatus according to claim 1, wherein the apparatus is a microprocessor comprising:

a memory controller having the syndrome calculator, the erasure locator, the syndrome modifier, and the error locator; and

one or more processor cores coupled with the memory controller.

7. The apparatus according to claim 1, wherein the apparatus is a computing device, comprising:

a system memory; and

a microprocessor, coupled with the system memory, having the syndrome calculator, the erasure locator, the syndrome modifier, and the error locator.

8. The apparatus according to claim 7, wherein the computing device is a selected one of a laptop, a netbook, a notebook, an ultrabook, a smartphone, a tablet, a personal digital assistant, an ultra-mobile PC, a mobile phone, a desktop computer, a server, a printer, a scanner, a monitor, a set-top box, an entertainment control unit, a digital camera, a portable music player, a digital video player, or a bar code reader.

9. One or more non-transient machine readable storage medium having a plurality of instructions configured to cause a memory controller, in response to execution of the plurality of instructions by the memory controller, to:

generate a plurality of partial syndromes for a codeword;

generate an erasure locator polynomial for the codeword;

generate modified partial syndromes based at least in part on the plurality of partial syndromes and the erasure locator polynomial of the codeword; and

generate an error locator polynomial using the modified partial syndromes, for error and erasure decoding of the codeword.

10. The one or more machine readable storage medium according to claim 9,

wherein the error locator polynomial is generated using a Berlekamp-Massey algorithm.

11. The one or more machine readable storage medium according to claim 9,

wherein the modified partial syndromes comprise no more than (2t−

B) partial syndromes wherein t is a number of correctable errors, and B is a number of erasures.

12. The one or more machine readable storage medium according to claim 11, wherein B is greater than t.

13. A method, comprising:

generating, by a memory controller, a plurality of partial syndromes for a codeword;

generating, by the memory controller, an erasure locator polynomial for the codeword;

generating, by the memory controller, modified partial syndromes based at least in part on the plurality of partial syndromes and the erasure locator polynomial of the codeword; and

generating, by the memory controller, an error locator polynomial using only a part of the modified syndrome, for error and erasure decoding of the codeword.

14. The method of claim 13, wherein a Berlekamp-Massey algorithm is used in generating the error locator polynomial.

15. The method of claim 13, wherein the modified partial syndromes comprise no more than (2t−

B) partial syndromes, wherein t is a number of correctable errors, and B is a number of erasures.

16. The method of claim 15, wherein B is greater than t.

17. An apparatus, comprising:

means for generating a plurality of partial syndromes for a codeword;

means for generating an erasure locator polynomial for the codeword;

means for generating modified partial syndromes for the codeword based at least in part on the plurality of partial syndromes and the erasure locator polynomial of the codeword; and

means for generating an error locator polynomial for the codeword using the modified partial syndromes, for error and erasure decoding of the codeword.

18. The apparatus of claim 17, wherein the means for generating an erasure locator polynomial comprises means for generating the erasure locator polynomial using a Berlekamp-Massey algorithm.

19. The apparatus of claim 17, wherein the modified partial syndromes comprise no more than (2t−

B) partial syndromes, wherein t is a number of correctable errors, and B is a number of erasures.

20. The apparatus of claim 19, wherein B is greater than t.