Computing an error detection code syndrome based on a correction pattern

• US 8,086,941 B2
• Filed: 02/14/2008
• Issued: 12/27/2011
• Est. Priority Date: 04/05/2002
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Williamson, Clifton James, Vasiliev, Peter Igorevich
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US12/031,043
• Publication Number:
  US 20080215956A1
• Time in Patent Office: 1,412 Days
• Field of Search: 714/768, 714/782, 714784-785, 714/746, 714/758
• US Class Current: 714/785
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation

Abstract

The present invention is all error detection and correction scheme that enables the use of Horner'"'"'s algorithm for the computation of EDC syndromes from the computed error pattern. Specifically, “transformed” EDC syndromes are computed during the read back of data and parity from the medium. The transformed syndromes are values of the polynomial whose coefficients occur in reverse order from that of the EDC codeword polynomial. In essence, by reversing the order of the coefficients, the Chien search processes the terms in descending order which is the right direction for Horner evaluation.

Claims

1. A method comprising:

generating a correction pattern based on a received codeword; and

generating an error detection code (EDC) syndrome based on the correction pattern, wherein the EDC syndrome is generated simultaneously during the generation of the correction pattern, wherein the codeword comprises an error detection code (EDC) appended to user data.

2. The method of claim 1, wherein generating the EDC syndrome comprises performing at least one iteration of Horner'"'"'s algorithm during the generation of the correction pattern.

3. The method of claim 1, wherein generating the EDC syndrome comprises:

receiving an initial error value that corresponds to a last symbol of an EDC codeword; and

performing an initial iteration of Horner'"'"'s algorithm using the initial error value.

4. The method of claim 1, wherein the received codeword comprises an EDC codeword having symbols that correspond to coefficients of a first polynomial, and wherein the EDC syndrome is a value of a second polynomial having coefficients of the first polynomial in a reversed order.

5. The method of claim 1, wherein generating the EDC syndrome comprises:

receiving a sequence of error values having a last error value that corresponds to a first symbol in the received codeword; and

calculating the EDC syndrome for the received codeword using the sequence of error values, wherein the EDC syndrome is calculated using Horner'"'"'s algorithm and a first iteration of Horner'"'"'s algorithm is calculated prior to receiving the last error value.

6. The method of claim 1, wherein generating the correction pattern based on the received codeword comprises computing the correction pattern using a Chien search in conjunction with Forney'"'"'s algorithm.

7. The method of claim 1, wherein the EDC syndrome is a recomputed transformed EDC syndrome, the method further comprising:

comparing the recomputed transformed EDC syndrome to a transformed EDC syndrome; and

if the recomputed transformed EDC syndrome corresponds to the transformed EDC syndrome, transferring the user data.

8. The method of claim 1, wherein the correction pattern comprises error locations and error values.

9. The method of claim 1, wherein the EDC syndrome is a transformed EDC syndrome.

10. A decoder comprising:

an error correction unit that generates a correction pattern based on a received codeword; and

an error detection code (EDC) syndrome module that generates an EDC syndrome based on the correction pattern, wherein the EDC syndrome is generated simultaneously during the generation of the correction pattern, wherein the codeword comprises an error detection code (EDC) appended to user data.

11. The decoder of claim 10, wherein the EDC syndrome module performs at least one iteration of Horner'"'"'s algorithm during the generation of the correction pattern.

12. The decoder of claim 10, wherein the EDC syndrome module receives an initial error value that corresponds to a last symbol of an EDC codeword and performs an initial iteration of Horner'"'"'s algorithm using the initial error value.

13. The decoder of claim 10, wherein the received codeword comprises an EDC codeword having symbols that correspond to coefficients of a first polynomial and the EDC syndrome is a value of a second polynomial having coefficients of the first polynomial in a reversed order.

14. The decoder of claim 10, wherein the EDC syndrome module receives a sequence of error values having a last error value that corresponds to a first symbol in the received codeword and calculates the EDC syndrome for the received codeword using the sequence of error values, wherein the EDC syndrome is calculated using Horner'"'"'s algorithm and a first iteration of Horner'"'"'s algorithm is calculated prior to receiving the last error value.

15. The decoder of claim 10, wherein the error correction unit computes the correction pattern using a Chien search in conjunction with Forney'"'"'s algorithm.

16. The decoder of claim 10, wherein the EDC syndrome is a recomputed transformed error detection code (EDC) syndrome, and wherein the device further comprises a comparator that compares the recomputed transformed EDC syndrome to a transformed EDC syndrome and transfers the user data if the recomputed transformed EDC syndrome corresponds to the transformed EDC syndrome.

17. The decoder of claim 10, wherein the correction pattern comprises error locations and error values, and wherein the EDC syndrome is a transformed EDC syndrome.

18. The decoder of claim 10, wherein the decoder is a part of a channel.

19. A device comprising:

a receiver that receives a codeword from a communication channel; and

an integrated circuit that generates a correction pattern based on the codeword and generates an error detection code (EDC) syndrome based on the correction pattern,

wherein the EDC syndrome is generated simultaneously during the generation of the correction pattern, and the codeword comprises an error detection code (EDC) appended to user data.