Techniques for correcting errors and erasures using a single-shot generalized minimum distance key equation solver

• US 8,166,376 B2
• Filed: 04/08/2008
• Issued: 04/24/2012
• Est. Priority Date: 04/08/2008
• Status: Expired due to Fees

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Hitachi Global Storage Technologies Netherlands BV (Western Digital Corporation)
• Inventors: Hassner, Martin, Oenning, Travis Roger, Galbraith, Richard Leo
• Primary Examiner(s): MASKULINSKI, MICHAEL C
• Application Number:
  US12/099,532
• Publication Number:
  US 20090254796A1
• Time in Patent Office: 1,477 Days
• Field of Search: None
• US Class Current: 714/781
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location polynomials
• 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/455 using a set of erasure patterns or successive erasure decoding, e.g. generalized minimum distance [GMD] decoding

Abstract

A system corrects errors in a codeword. The system includes a channel that sorts reliability numbers of symbols in the codeword to create an ordered list of candidate erasure locations. The system also includes a generalized minimum distance decoder that iteratively processes the ordered list of candidate erasure locations and at least two syndromes of the codeword using a single-shot key equation solver to generate an error locator polynomial and an error evaluator polynomial. The generalized minimum distance decoder processes the least reliable candidate erasure locations first within the ordered list of candidate erasure locations.

Claims

1. A system for correcting errors in a codeword, the system comprising:

a channel that sorts reliability numbers of symbols in the codeword to create an ordered list of candidate erasure locations; and

a generalized minimum distance decoder that iteratively processes the ordered list of candidate erasure locations and at least two syndromes of the codeword using a single-shot key equation solver to generate an error locator polynomial and an error evaluator polynomial,

wherein the generalized minimum distance decoder processes the least reliable candidate erasure locations first within the ordered list of candidate erasure locations.

2. The system defined in claim 1 wherein the generalized minimum distance decoder evaluates symbols and counts a number of zeros in the error evaluator polynomial at a residual set of erasures in multiple iterations of the single-shot key equation solver, the residual set of erasures comprising evaluated candidate erasure locations that remain among the ordered list of candidate erasure locations after the least reliable candidate erasure locations have been removed from the ordered list of candidate erasure locations.

3. The system defined in claim 2 wherein the maximum number of zeros in the error evaluator polynomial at the residual set of erasures is a generalized minimum distance criterion that is used to update a best error locator index.

4. The system defined in claim 2 wherein the generalized minimum distance decoder counts a number of zeros in the error locator polynomial at a set of removed erasures in a last iteration of the single-shot key equation solver, and a best error locator polynomial has a maximum number of zero values when evaluated in the set of removed erasures, the set of removed erasures being the least reliable candidate erasure locations.

5. The system defined in claim 4 wherein the generalized minimum distance decoder computes the error evaluator polynomial at all erasure locations during an initialization process, the initialization process taking 2t cycles, where t is a number of correctable errors.

6. The system defined in claim 1 wherein the generalized minimum distance decoder solves the error locator polynomial and the error evaluator polynomial to generate error locations and error values, and uses the error locations and the error values to correct errors in the codeword in order to generate a corrected output codeword.

7. The system defined in claim 1 wherein the system is a hard disk drive, and the codeword is read from a magnetic disk in the hard disk drive.

8. A method for correcting errors in a codeword performed by a data storage device, the method comprising:

generating reliability numbers for symbols in the codeword;

sorting the reliability numbers to generate a sorted list of candidate erasure locations for the symbols in the codeword; and

iteratively processing the sorted list of candidate erasure locations and at least two syndromes of the codeword to generate an error locator polynomial and an error evaluator polynomial using a single-shot generalized minimum distance key equation solver,

wherein the reliability numbers are arranged such that the single-shot generalized minimum distance key equation solver processes the least reliable candidate erasure locations first within the sorted list of candidate erasure locations.

9. The method defined in claim 8 wherein iteratively processing the sorted list of erasure candidate locations and at least two syndromes of the codeword to generate the error locator polynomial and the error evaluator polynomial using the single-shot generalized minimum distance key equation solver further comprises counting a number of zeros in the error evaluator polynomial at a residual set of erasures in multiple iterations of the single-shot generalized minimum distance key equation solver, the residual set of erasures comprising evaluated candidate erasure locations that remain in the sorted list of candidate erasure locations after the least reliable candidate erasure locations have been removed from the sorted list of candidate erasure locations.

10. The method defined in claim 9 wherein the maximum number of zeros in the error evaluator polynomial at the residual set of erasures is a generalized minimum distance criterion that is used to update a best error locator index.

11. The method defined in claim 9 wherein iteratively processing the sorted list of candidate erasure locations and at least two syndromes of the codeword to generate the error locator polynomial and the error evaluator polynomial using the single-shot generalized minimum distance key equation solver further comprises counting a number of zeros in the error locator polynomial at a set of removed erasures in a last iteration of the single-shot key equation solver, and a best error locator polynomial has a maximum number of zero values when evaluated in the set of removed erasures, the set of removed erasures being the least reliable candidate erasure locations.

12. The method defined in claim 11 wherein iteratively processing the sorted list of candidate erasure locations and at least two syndromes of the codeword to generate the error locator polynomial and the error evaluator polynomial using the single-shot generalized minimum distance key equation solver further comprises computing the error evaluator polynomial at all erasure locations during an initialization process, the initialization process taking 2t cycles, where t is a number of correctable errors.

13. The method defined in claim 8 further comprising:

solving the error locator polynomial and the error evaluator polynomial to generate error locations and error values; and

using the error locations and the error values to correct errors in the codeword in order to generate a corrected codeword.

14. The method defined in claim 8 wherein the method is performed by a hard disk drive, and the codeword is read from a magnetic disk in the hard disk drive.

15. A hard disk drive that corrects errors in a codeword read from a magnetic disk, the hard disk drive comprising:

a channel that sorts reliability numbers of symbols in the codeword to create an ordered list of candidate erasure locations; and

a decoder using a single-shot generalized minimum distance key equation solver to iteratively process the ordered list of candidate erasure locations and at least two syndromes of the codeword to generate an error locator polynomial and an error evaluator polynomial,

wherein the single-shot generalized minimum distance key equation solver processes the least reliable candidate erasure locations first within the ordered list of candidate erasure locations.

16. The hard disk drive defined in claim 15 wherein the single-shot generalized minimum distance key equation solver evaluates the symbols and counts a number of zeros in the error evaluator polynomial at a residual set of erasures in multiple iterations of the single-shot generalized minimum distance key equation solver, the residual set of erasures being evaluated symbols that remain in the ordered list of candidate erasure locations after the least reliable candidate erasure locations have been removed from the ordered list of candidate erasure locations.

17. The hard disk drive defined in claim 16 wherein the maximum number of zeros in the error evaluator polynomial at the residual set of erasures is a generalized minimum distance criterion that is used to update a best error locator index.

18. The hard disk drive defined in claim 16 wherein the decoder counts a number of zeros in the error locator polynomial at a set of removed erasures in a last iteration of the single-shot generalized minimum distance key equation solver, and a best error locator polynomial has a maximum number of zero values when evaluated in the set of removed erasures, the set of removed erasures being the least reliable candidate erasure locations.

19. The hard disk drive defined in claim 18 wherein the decoder computes the error evaluator polynomial at all erasure locations during an initialization process, the initialization process taking 2t cycles, where t is a number of correctable errors.

20. The hard disk drive defined in claim 15 wherein the decoder solves the error locator polynomial and the error evaluator polynomial to generate error locations and error values, and uses the error locations and the error values to correct errors in the codeword in order to generate a corrected output codeword.