Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-10-29
2003-09-23
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S762000
Reexamination Certificate
active
06625774
ABSTRACT:
BACKGROUND OF THE INVENTION
Technical Field of the Invention
The present invention relates to locating errors in interleaved code words, and particularly to a system and method for providing additional error locating capability with relatively little overhead.
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 storage 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. Concerning long burst errors, a correlation exists between error locations in different interleaved code words. If all of the burst error locations can be identified and marked as erasures for the interleaved code words, error and erasure decoding can more successfully correct interleaved code words. Based upon the foregoing, there exists a need for a system and method for efficiently providing an error locating coding scheme that is tailored to locate errors typically encountered in a magnetic storage medium.
SUMMARY OF THE INVENTION
The present invention overcomes the shortcomings in prior systems and thereby satisfies a significant need for a system and method for efficiently locating errors in interleaved code words stored in a storage device. The system selectively provides additional check symbols to increase the power of uncorrectable interleaved code words without a substantial increase in overhead.
Conventional interleaved code words may be viewed as row codes wherein each interleaved code word includes a plurality of information symbols and a plurality of check symbols. In the preferred embodiments of the present invention, an error locating code word is created from selected columns of each interleaved code word. The error locating code word is stored with the corresponding interleaved code words in memory. The error locating code word is created in part by utilizing the same Reed-Solomon generator polynomial that is used in the formation of the interleaved code words.
The preferred embodiments of the present invention include software and hardware necessary for initially scrambling the symbols from the selected columns of the interleaved code words and creating column parity check symbols from the scrambled symbols. Each column parity check symbol, created using an operator such as an exclusive-OR boolean operator, is as wide as the width of a symbol extracted from the interleaved code word. The system software and hardware performs an operation on the high and low nibbles of each column parity check symbol to generate a plurality of reduced column parity check symbols, wherein each reduced column parity check symbol has a width that is half the width of each column parity check symbol. The software and hardware merges together pairs of the reduced column parity check symbols corresponding to two separate columns of the interleaved code words to create a plurality of merged column check symbols. The encoding operation is complete upon performing a Reed-Solomon encoding operation on the merged column check symbols to create error locating check symbols. The error locating code word is formed from the merged column check symbols and the error locating check symbols
Following retrieval of the interleaved code words and corresponding error locating check symbols from the storage device, the merged column check symbols are reconstructed from the symbols of the selected columns of the retrieved interleaved code words using the same encoding procedure used to generate the error locating code word. At around the same time the interleaved code words are decoded, the reconstructed merged column check symbols are used to compute the partial syndromes of the error locating code word. Upon the affirmative determination of the presence of error locations and patterns in a decoded interleaved code word, the partial syndromes of the error locating code word are modified accordingly.
The system software and hardware decodes the error locating code word upon the affirmative determination of any uncorrectable interleaved code words. A Reed-Solomon decoding operation is used to decode the error locating code word. Noting that a merged column check symbol corresponds to two selected columns in the interleaved code words, the column of the interleaved code word is identified for each error in the decoded error locating code word. The symbols in the identified columns of the previously uncorrectable interleaved code words are then marked as erasures. Error and erasure decoding of the uncorrectable interleaved code words is then performed a second time.
REFERENCES:
patent: 4185269 (1980-01-01), Hodges et al.
patent: 4317201 (1982-02-01), Sedalis
patent: 4541092 (1985-09-01), Sako et al.
patent: 5003539 (1991-03-01), Takemoto et al.
patent: 5392299 (1995-02-01), Rhines et al.
patent: 5450421 (1995-09-01), Joo et al.
patent: 5696774 (1997-12-01), Inoue et al.
patent: 5712861 (1998-01-01), Inoue et al.
patent: 5781565 (1998-07-01), Sako et al.
patent: 5809042 (1998-09-01), Nakamura et al.
patent: 5917836 (1999-06-01), Ichikawa et al.
patent: 6041431 (2000-03-01), Goldstein
patent: 6112324 (2000-08-01), Howe et al.
patent: 6115837 (2000-09-01), Nguyen et al.
“Error Control Systems” by Stephen Wicker (1995 Prentice-Hall).*
Sitaraman, R.K. and Jha, N.K.; Optimal design of checks for error detection and location in fault-tolerant multiprocessor systems; IEEE Transactions on Computers, vol.: 42 Issue: 7, Jul. 1993, pp.: 780-793.
De'cady Albert
Jorgenson Lisa K.
STMicroelectronics Inc.
Szuwalski Andre
Torres Joseph D.
LandOfFree
Redundancy system and method for locating errors in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Redundancy system and method for locating errors in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Redundancy system and method for locating errors in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3083383