Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-10-29
2003-08-12
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06606727
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to a Reed-Solomon error correction code, and particularly to a system and method for providing an interleaved error correction code having selectively variable redundancy.
2. Background of the Invention
Existing data storage devices, such as disk drives, utilize Reed-Solomon error correcting codes to perform burst error correction and to achieve higher areal densities. The capability to correct multiple error bursts in near real time is necessary to minimize error recovery time and avoid the interruption of data flow.
Because magnetic data storage devices tend to generate errors in bursts, data stored on magnetic storage devices is typically arranged in an interleaved format. Interleaving is often used to spread the consecutive error bits or symbols into different interleaves which can each be corrected individually. Because interleaving allows the same hardware decoder core to process multiple interleaves repeatedly, interleaving is a cost effective technique to effectively combat burst errors.
Conventional interleaved coding techniques, however, are not without their shortcomings. For instance, interleaved code words have the same number of redundant check symbols and thus possess the same error correction capability. It has been observed that random errors may concentrate in one or two interleaves instead of substantially all interleaves. This concentration of random errors serves to defeat the effectiveness of providing redundant check symbols in each interleaved code word. Based upon the foregoing, there exists a need for a system and method for efficiently providing an error correction coding scheme that is tailored to correcting errors typically encountered in a magnetic storage medium.
SUMMARY OF THE INVENTION
The present invention overcomes shortcomings in prior systems and satisfies a significant need for providing an error correction code having a selectively variable redundancy. The system selectively provides additional check symbols to increase the power of uncorrectable interleaved code words without a substantial increase in overhead.
With conventional variable redundancy Reed-Solomon error correction techniques, only some of the check symbols that are generated form part of an interleaved code word and thus provide redundancy. Unused check symbols are typically discarded. In a preferred embodiment of the present invention, a programmable number of extended check symbols are generated from the unused check symbols. Each extended check symbol is formed by performing a Reed-Solomon encoding operation on each unused check symbol in a column of the unused check symbols. Extended check symbols are organized into one or more sets of extended check symbols. The number of sets of extended check symbols is based upon the order of the Reed-Solomon generator polynomial utilized in forming the extended check symbols. The number of extended check symbol sets is limited both by the amount of additional overhead available and by the number of unused check symbols per interleave. The one or more sets of the extended check symbols are stored in memory with the corresponding interleaved code words.
In addition to the preferred embodiments of the present invention including system software and associated hardware for encoding the extended check symbols, the preferred embodiments of the present invention also selectively decode the extended check symbols as needed based upon the identification of uncorrectable interleaved code words during a conventional decode operation of the interleaved code words. In particular, following the conventional interleave decoding operation, the extended check symbols are selectively decoded upon the affirmative determination that the number of uncorrectable interleaved code words is less than or equal to the number of sets of extended check symbols. The decoding recovers the unused check symbols that were used to generate the extended check symbols. The unused check symbols, when added to the previous uncorrectable interleaved code words, increase the number of check symbols available for correcting the previously uncorrectable errors therein. Following modification of partial syndromes to take into account the unused check symbols, the previously uncorrectable interleaved code words are decoded a second time with the recovered unused check symbols now being part of the uncorrectable interleaved code words. In this iterative decoding technique, the check symbols of the uncorrectable interleaved code words are selectively increased so as to increase the error correcting capability of the previously uncorrectable interleaved code words, without a significant increase in overhead.
Instead of generating a single layer of extended check symbols, in a second preferred embodiment of the present invention two or more layers of extended check symbols are created. The number of sets of extended check symbols in each layer of extended check symbols may be distinct. Further, the extended check symbols in each layer of extended check symbols are generated from different columns of the unused check symbols. In decoding the interleaved code words, the system software and associated hardware will sequentially decode the extended check symbols from different layers of extended check symbols until all of the uncorrectable interleaved code words which can be corrected due to the extended check symbols have been corrected.
REFERENCES:
patent: 4849976 (1989-07-01), Schilling et al.
patent: 5285455 (1994-02-01), Tong et al.
patent: 5392299 (1995-02-01), Rhines et al.
patent: 5778011 (1998-07-01), Blaum et al.
patent: 5838696 (1998-11-01), Mons
patent: 5872798 (1999-02-01), Baggen et al.
patent: 6041431 (2000-03-01), Goldstein
patent: 6378105 (2002-04-01), Chiang
Saxena, N.R. McCluskey, E.J.; Analysis of checksums, extended-precision checksums, and cyclic redundancy checks; IEEE Transactions on Computers, vol.: 39 Issue: 7, Jul. 1990 pp.: 969-975.*
Rankin, D. and Gulliver, T.A.; Randomly interleaved single parity check product codes; 1999 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp.: 420-423.*
Roth, R.M. and Seroussi, G.; Reduced-redundancy product codes for burst error correction; IEEE Transactions on Information Theory, vol.: 44 Issue: 4, Jul. 1998 pp.: 1395-1406.
Gill, III John T.
Yang Honda
De'cady Albert
Jorgenson Lisa K.
STMicroelectronics Inc.
Szuwalski Andre
Torres Joseph D.
LandOfFree
System and method for providing error correction coding with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for providing error correction coding with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for providing error correction coding with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115377