Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-30
2004-07-27
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C711S114000, C360S053000
Reexamination Certificate
active
06769088
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to data storage systems which use error correction codes to protect stored data from loss.
Error correction codes (ECC's) are often employed in data storage systems to detect and correct data corrupted as a result of a media defect. Before a string of data symbols is recorded, it is encoded to generate redundancy symbols. The redundancy symbols are appended to the data symbols to form code words. When the code words are retrieved from data storage devices, the code words are decoded to detect and, if possible, correct any errors in the data. This decoding is accomplished through manipulation of the redundancy symbols.
Data may be encoded using an (n,k) D distance Reed-Solomon code to protect data stored on k data sectors of k data storage devices using n−k (or “r”) redundant sectors of r redundant drives. When new data words are received for storage in designated sectors of the data storage devices, the redundancy information stored in corresponding sectors of the redundant drives is updated in order to provide error protection to the new data words. That is, when the new data words are stored in a designated data sector on a particular data storage device, such as a disk drive, the data words stored in the same sector location on each of the k−1 other data drives are retrieved. An encoder encodes, using a Reed-Solomon code, the corresponding symbols from each of the k−1 retrieved data words and the new data, and generates for each set of k symbols r redundancy symbols. The encoder thus encodes the first symbols from each of these words and generates a first set of r redundancy symbols, and next, encodes the second symbols from each of these words and generates a second set of r redundancy symbols, and so forth. Each set of r redundancy symbols and the associated k encoded symbols together form a Reed Solomon code word. This level of encoding is referred to as sector coding. The various sets of r redundancy symbols are written to the r redundant sectors, by writing one redundancy symbol from each set, that is, one symbol from each code, on each redundant sector.
If an error occurs in a sector or the drive on which the sector resides fails, the lost or erroneous data stored thereon can be regenerated using the associated Reed-Solomon code words. The data and redundancy symbols which form the associated code words are retrieved from the other sectors or drives. A decoder then manipulates the code words, using conventional error correcting techniques, to produce the otherwise lost symbols. A (n,k) Reed Solomon code of distance D can regenerate symbols even if errors or failures occur in up to D−1 sectors or drives simultaneously.
Although the above-described redundancy technique is quite robust, it requires extensive, time-consuming “read-after-write” operations. That is, each write operation requires that corresponding symbols from each of the data sectors be retrieved so that the retrieved symbols and the symbols to be recorded can be encoded to generate new redundancy symbols.
Another prior approach, described in U.S. Pat. No. 5,265,104, in the name of Lih-Jyh Weng, reduces the number of read-after-write operations by allowing a data storage system to perform up to [(n−k)/2]−1 write operations before it retrieves and encodes the corresponding data code word symbols, along with the new data to be recorded, to generate new redundancy symbols. The protection of the re-written data is maintained by recording a copy of that data over redundant symbols on a redundant sector. Consequently, each such write operation introduces two erasures (i.e., errors with known locations) to the code. While this coding scheme requires fewer retrieval and encoding steps, it loses some error correction capacity for each write operation performed without the retrieval and encoding steps. That is, the effective distance of the code is reduced by two during each write operation which writes new data to both a data sector and a redundant sector.
SUMMARY OF THE INVENTION
This invention features an efficient way of providing error protection for data that is to be stored in a data storage system of the kind in which data are stored in data sectors in a data storage area and redundant information that provides error protection for the data are stored in corresponding redundant sectors in a redundant storage area.
In one general aspect of the invention, new data that is written to a designated one of the data sectors, and that is not error protected by the redundant information, is received, and error correction information for the new data is selectively stored in an additional storage area to provide error protection for the new data instead of revising the redundant information to provide such error protection.
Embodiments of the invention may include one or more of the following features.
The selective storing of the error correction information may include determining if the error protection provided by the redundant information is sufficient to enable error correction of data in other data sectors if the redundancy information is not revised. Such determination may include determining if the additional storage area has enough capacity to store the error correction information. If it is determined that the additional storage area does not have enough capacity to store the error correction information, then the redundant information is revised. The redundant information is revised in a sector encoding operation.
The additional storage area may include a plurality of additional sectors. Determining if the additional storage area has enough capacity may include the following: determining if the designated data sector has been written since a previous sector encoding; and if the designated data sector has not been written since the previous sector encoding, determining how many other ones of the data sectors have been written since the previous sector encoding.
The selective storing may further include storing the error correction information on an available sector in the additional storage area if the number of other ones of the data sectors written since the previous sector encoding is less than the number of sectors in the additional storage area. The previous sector encoding corresponds to the last sector encoding operation in which the redundant information was generated from the data in the data sectors.
The selective storing may further include revising the redundancy information if the number of other ones of the data sectors written since the previous sector encoding is not less than the number of sectors in the additional storage area. The revising of the redundancy information may include performing a sector encoding to regenerate the redundant information in the redundant sectors by encoding the data in the data sectors and the new data stored in the additional storage area.
The error correction information stored in the additional storage area may include error correction code (ECC) associated with the new data. That error correction information may further include a copy of the new data.
Alternatively, a first portion of error correction code associated with the new data may be stored in the designated data sector and the error correction information may include a remaining second portion of error correction code associated with the new data. If the data sectors each store a Reed Solomon code word of k data symbols and r ECC symbols, the r ECC symbols being generated by symbol encoding the data, then the length of the first portion of the error correction code associated with the new data may be a first number of ECC symbols and the length of the remaining second portion of error correction code associated with the new data may be a second number of ECC symbols equal to r minus the first number of ECC symbols.
The redundant sectors can have redundant symbols and the corresponding data symbols in the data sectors and associated redundant symbols in the redundant sectors may form Reed
Dooley Matthew C.
Maxtor Corporation
LandOfFree
Sector-coding technique for reduced read-after-write operations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sector-coding technique for reduced read-after-write operations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sector-coding technique for reduced read-after-write operations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3244200