Method and apparatus for error detection
View Patent ↗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.
1. A method comprising steps of:
calculating a transformed error detection code syndrome from data having an error detection code appended to user data, wherein the transformed error detection code syndrome is calculated using a second polynomial;
calculating a recomputed transformed error detection code syndrome, wherein the recomputed transformed error detection code syndrome is calculated using a first polynomial and a correction pattern for the data;
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.
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 Forney'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-transformed error detection code syndrome.
5. 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.
6. The method of claim 5 wherein if the transformed EDC syndrome is zero, then the transmitted data is transmitted to the host.
7. The method of claim 1 , wherein the error detection code includes a first portion with a first symbol size and a second portion with a second symbol size, wherein the second symbol size is different from the first symbol size.
8. The method of claim 1 , wherein the second polynomial has coefficients of the first polynomial in a reversed order.
9. A method of detecting an error in error correction code (ECC) interleave encoded data comprising steps of:
receiving ECC interleave encoded data, the ECC interleave encoded data comprising user data and an error detection code (EDC);
calculating a transformed error detection code syndrome using the ECC interleave encoded data and a second polynomial;
generating a recomputed transformed error detection syndrome using a first polynomial and a computed correction pattern for the ECC interleave encoded data; and
comparing the transformed EDC syndrome with the recomputed transformed error detection syndrome.
10. The method of claim 9 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.
11. The method of claim 10 wherein the locating step comprises performing a Chien search using the received data and the evaluating step comprises performing Forney's algorithm.
12. The method of claim 9 , 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.
13. The method of claim 12 , 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.
14. The method of claim 9 further comprising steps of:
generating an error correction code (ECC) syndrome from the received data in an ECC syndrome generator.
15. The method of claim 14 wherein the ECC syndrome generator is connected to a comparator trough an error correction unit.
16. The method of claim 15 wherein the error correction unit is connected to the comparator through an EDC syndrome recomparator.