Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-01
2001-08-14
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S762000
Reexamination Certificate
active
06275965
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and means for the detection and correction of multibyte errors in long byte strings formatted into a two-level block code structure. Each of the blocks comprises a plurality of subblocks of codewords and their check bytes from a linear error correction code and additional block check bytes derived from some linear attribute taken over all of the codewords. The block-level check bytes can be used to detect and correct errors in codewords when such errors exceed the check byte correction capacity of any single codeword.
DESCRIPTION OF RELATED ART
In the prior art as described in Patel et al., U.S. Pat. No. 4,525,838, “Multiple Byte Error Correcting System Involving a Two-level Code Structure”, there is disclosed an apparatus for detecting and correcting multiple bytes in error in long byte strings read back from a magnetic disk storage subsystem or the like. Prior to recording the byte strings on magnetic disk, the data bytes are formatted into a two-level block/subblock code structure. Thus, equal-length data words are mapped into codewords from a linear error correction code such as a Reed-Solomon (RS) code. A fixed number of these codewords, including their check bytes, are byte interleaved to form a subblock. In turn, a given number of subblocks are concatenated and check bytes taken over all of the subblocks are appended thereto to form a block.
In Patel, each subblock comprises at least two byte interleaved message words and check bytes. In order to correct t
1
errors in a codeword, 2t
1
check bytes must be calculated from the message word and appended to form the codeword. This means that each subblock can correct up to t
1
bytes in error. Also, each block consists of a predetermined number of subblocks and block check bytes. In this regard, the block check bytes are computed over all of the subblocks as a modulo 2 accumulation as specified by a pair of modulo 2 matrix equations. Thus, Patel does not use the same code process for generating the codewords and check bytes at the subblock level as is used to derive the block-level check bytes. This presents recovery difficulty if the block-level check bytes are themselves subject to error or erasure.
In Cox et al., copending application Ser. No. 08/971,798, filed Nov. 17, 1997, “Method and Means For Efficient Error Detection and Correction in Long Byte Strings Using Integrated Interleaved Reed-Solomon Codewords”, there is disclosed a method and means for enhancing error detection and correction capability obtained when equal-length data byte strings are encoded in a two-level block format. That is, data bytes are encoded into codewords of a linear block code. The codewords are then interleaved and mapped into a block codeword with additional redundancy. The advance in this case is realized by using the same coding regime for both levels of derived redundancy bytes. This is achieved by forming a logically combined datastring from copies of the (n−1) other datastrings and applying the combined string and the (n−1) other strings as input to a counterpart set of RS encoders and logically combining the encoded outputs and concatenating with the (n−1) other outputs. On readback from the disk, the codewords of a block and their logical sum are syndrome processed to resolve any identified errors within the correction capability of any single word. The syndrome processing also resolves any errors within the correction capability of any single word and block-level redundancy. Lastly, the syndrome processing provides signal indication when the correction capacity has been exceeded.
A number of scientific groups concerned with magnetic recording limits (the so-called superparamagnetic limit) are of the opinion that bits are going to disappear. What this means is that over time the recording size of bits in relationship to recording densities will become even more infinitesimal. One consequence is that random thermal motion at the molecular/atomic level will be sufficient to change or alter bits.
Currently, the worst bit error rate for disk recording is in the range of one error bit of 10
6
bits stored. This is expressed as a bit error rate of 10
−6
. The actual range lies between 10
−9
and 10
−6
with the latter representing the worst case. As may be recalled, when ECC and especially RS codewords are recorded, the RS decoder located in the DASD readback channel converts a nominal bit error rate from 10
−6
to 10
−13
.
Presently, magnetic disk recording of data uses a short sector format (512 bytes per sector) and requires an ECC redundancy of 4-5 percent. It is known from Shannon's Information Theory that block error correcting codes such as RS codewords that are very long are more communications efficient in that the percentage of ECC redundancy for a prescribed reliable error rate is reduced. However, the longer codewords increased the complexity of RS decoders. It is proposed to use a longer sector format in the order of 4096 bytes to reduce the ECC redundancy percentage.
The copending Cox application discloses the use of three-way interleaving on short sector formatted data (512 bytes/sector). In this case, a block-level check was obtained from the XORing of the three subblocks prior to first-level encoding. When the codeword or subblock error exceeds the subblock correction capacity, the Cox configuration is limited in that the block-level redundancy can only correct a single subblock badly in error (a so-called “bursty” subblock).
In this specification, the terms “subblock” and “codeword” are used synonymously. Also, the term “byte” of eight binary bits is used as a quantitative measure of data and information as a convenience. Any other measure, such as a “nibble” or “word”, if used consistently, would also operate as a quantitative measure.
Also in this specification, the term “bursty subblock” should be defined as any subblock or codeword subject to bytes in error exceeding its t
1
codeword correction capacity for any given two-level linear block error correction coding process.
SUMMARY OF THE INVENTION
It is an object of this invention to devise a method and means for enhancing the error detection and correction capability obtained when a plurality of data byte strings or vectors are interleaved and encoded in a two-level, block-formatted linear code using codeword (subblock) and block-level redundancy.
It is another object of this invention to devise a method and means for extending the number of interleaved subblocks and the number of correctable bursty subblocks in a method and means for detecting and correcting error in a two-level, block-formatted linear code using codeword (subblock) and block-level redundancy.
It is a more particular object to devise a method and means for enhancing a set of equal-length data byte messages formatted as a sector or a track, modifying them by way of logically combining and interleaving them, mapping them into ECC codewords, and modifying the ECC codewords by performing inverse logical operations thereon prior to storing or communicating them.
It is yet another particular object to devise a method and means responsive to possible noise-encrusted codewords of a two-level, block-formatted linear code and received from a communications path or read back from a storage subsystem for flexibly utilizing block-level redundancy in the detection and correction of error among multiple bursty codewords.
It was unexpectedly observed that an N×N sized matrix having nonzero minors with orders up to B could be used to secure the necessary integration interleaving among N data byte vectors to form modified data byte vectors. There are several purposes to be served by the interleaving method and pattern. First, selected patterns of interleaving ensure single-pass, two-level linear block error correction coding when the modified data vectors are applied to an ECC encoding arrangement. Second, the method and means are parameterized so as to either extend or reduce the number of bursty co
Cox Charles Edwin
Hassner Martin Aureliano
Patel Arvind
Trager Barry Marshall
Baker Stephen M.
Brodie R. Bruce
International Business Machines - Corporation
LandOfFree
Method and apparatus for efficient error detection and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for efficient error detection and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient error detection and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549051