Method and apparatus for error detection

• US 20040010742A1
• Filed: 07/10/2003
• Published: 01/15/2004
• Est. Priority Date: 04/05/2002
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Vasiliev, Peter Igorevich, Williamson, Clifton James
• Granted Patent: US 7,421,642 B2
• Time in Patent Office: Days
• US Class Current: 714/746
• 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 an 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 of detecting errors in transferred data comprising steps of:

receiving transferred data having an error detection code with a first symbol size and an error correction code having a second symbol size different from the first symbol size appended to user data;

calculating a transformed error detection code syndrome;

calculating a recomputed error detection code syndrome;

comparing the recomputed transformed error detection code syndrome to the transformed error detection code syndrome; and

if the recomputed transformed error detection code syndrome corresponds to the transformed error detection code syndrome, transferring the data to a host.

2. The method of claim 1 further comprising steps of:

if the recomputed transformed error detection code syndrome does not correspond to the transformed error detection code syndrome, receiving the data again.

3. The method of claim 1, wherein the transformed error detection code syndrome recomputation step comprises steps of:

computing a correction pattern using a Chien search in conjunction with Fomey'"'"'s algorithm

recomputing the transformed error detection code syndrome using Homer'"'"'s algorithm.

4. The method of claim 1, wherein the transformed error detection code syndrome calculating step comprises steps of:

generating an error detection code multiplier;

generating a non-transformed error detection code syndrome; and

multiplying the error detection code multiplier by the non-transformned error detection code syndrome.

6. The method of claim 1 wherein the step of calculating a recomputed transformed error detection code syndrome is performed only if the transformed EDC syndrome is nonzero.

7. The method of claim 6 wherein if the transformed EDC syndrome is zero, then the transmitted data is transmitted to the host.

8. A method of detecting an error in error correction code (ECC) interleave encoded data comprising steps of:

receiving ECC interleave encoded data;

transforming the data in a transformed error detection code (EDC) syndrome generator into a transformed error detection code syndrome;

receiving the ECC interleave encoded data in a recomputed transformed error detection syndrome generator;

generating a recomputed transformed error detection syndrome associated with a computed correction pattern in the ECC interleave encoded data; and

comparing the transformed EDC syndrome with the recomputed transformed error detection syndrome.

9. The method of claim 8 further comprising a step of:

locating errors either in the received data using an error locator; and

correcting errors in the received data using an error evaluator.

10. The method of claim 9 wherein the locating step comprises performing a Chien search using the received data and the evaluating step comprises performing Forney'"'"'s algorithm.

11. The method of claim 8, wherein the transforming step comprises:

generating a non-transformed EDC syndrome;

computing an EDC multiplier; and

multiplying the non-transformed EDC syndrome by the EDC multiplier to generate the transformed EDC syndrome.

12. The method of claim 11, wherein the step of generating a non-transformed EDC syndrome generator comprises:

receiving the data;

providing clocked flip-flops;

multiplying an output of the flip-flops with a value associated with the error detection code in the received data; and

logically adding the multiplied output to the received data.

13. The method of claim 8 further comprising steps of:

generating an error correction code (ECC) syndrome from the received data in an ECC syndrome generator.

14. The method of claim 13 wherein the ECC syndrome generator is connected to a comparator through an error correction unit.

15. The method of claim 14 wherein the error correction unit is connected to the comparator through an EDC syndrome recomparator.

16. A method for encoding data with an error correction code and error detection code comprising:

generating an error correction code for data using a first symbol size; and

generating an error detection code for the data using a second symbol size different from the first symbol size.

17. The method according to claim 16 wherein the first symbol size is h-bits and the second symbol size (g-bits) is twice the first symbol size.