Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-29
2002-05-14
Decady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06389573
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to error correction.
Present day storage systems employ a number of different approaches to minimize the number of errors that may occur during a data readback process. In one approach, a storage system rereads the data when uncorrectable errors are detected. Each time the reread operation is performed, the operating conditions are varied slightly, for example, by offsetting the transducer from the center of the track. The reread operations repeat until either the erroneous data are corrected or a predetermined number of reread operations has been performed, at which point the reread process may be terminated in accordance with preset system parameters.
One well-known error correction code that may be used to detect and, if possible, correct the errors which occur in the read data is the Reed-Solomon code. It may be expressed as an (n,k) code where the length of the code word is n symbols and the number of data symbols in the code word is k. The number of redundant symbols corresponds to a check symbol portion r, where r=n−k and the minimum code distance, d, is d=(n−k)+1.
In the prior systems which employ conventional Reed-Solomon decoding techniques during the reread or “read retrial” process to correct and detect errors in the read data, the same decoding algorithm that was used to decode the data in the initial read is also used during the read retrial process. That is, during a read retrial, the system performs an error correction decoding algorithm, used to correct t symbol errors, where t=(d−1)/2, for each reread operation. If each read contains more than t errors, the correction code is unable to recover the data correctly.
SUMMARY OF THE INVENTION
This invention features a read retrial process for rereading and decoding stored code words, the read retrial process converting errors to erasures to enhance error correction capability during decoding.
Generally, in one aspect of the invention, the read retrial process reads at least two copies of a code word, compares corresponding symbols in the read code word copies to determine which corresponding symbols are unequal, and performs a decoding operation to decode one of the copies using symbol locations for the unequal corresponding symbols.
Embodiments of the invention may include one or more of the following features.
The code word read by the process may be an (n,k) Reed-Solomon code word of a minimum code distance d. Such a Reed-Solomon code word is capable of correcting any combination of errors and erasures (i.e., errors with known locations) as long as the sum of the number of erasures and twice the number of errors is less than the minimum distance d of the code word. Thus, the code word copies are processed as having “erasures”—errors at the symbol locations for the unequal corresponding symbols—by a decoding operation that includes an error-erasure decoding operation. By converting errors to erasures, the error-erasure decoding operation can correct as many as 2t erasures if there are no errors.
The symbol locations may be erasure pointers.
The reads may be consecutive reads.
If the error-erasure decoding operation fails, the other of the read copies may be decoded. If the decoding operations for one or both copies fail, then one or more additional copies may be read and used to produce new erasure pointers.
The read retrial scheme of the invention is quite advantageous in that it tolerates almost twice as many symbol errors as prior read retrial approaches by allowing errors to be processed as erasures by a decoding operation. Thus, the error correction capability of a code word that is read back as part of a read retrial process is increased by increasing the total number of correctable errors from t=(d−1)/2 to as many as d−1.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.
REFERENCES:
patent: 5715262 (1998-02-01), Gupta
Stevens, On decoding unequal error protection product codes, IEEE, pp. 880-895, Jul. 1990.*
Patapoutian et al. The effects of a reread on data reliability, IEEE, pp. 2710-2713, Sep. 1997.*
Peterson et al. Error correcting codes, The MIT Press, pp. 305-308, 1972.
Chase Shelly A
De'cady Albert
Maxtor Corporation
LandOfFree
Enhanced read retrial scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced read retrial scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced read retrial scheme will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2915170