Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2001-01-25
2003-10-07
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S752000, C360S053000
Reexamination Certificate
active
06631485
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to apparatus and methods for storing data on magnetic media and in particular to such apparatus and methods which implement at least two levels of error correction.
BACKGROUND OF THE INVENTION
There is a continually increasing demand for magnetic data storage devices capable of storing large volumes of digital data, such as computer data on magnetic tape by means of the DDS (Digital Data Storage) Format. In a DDS read/write mechanism using the above format, data are recorded in helical scan fashion on an elongate recording media, comprising a tape coated with a magnetic medium, by a rotating drum carrying one or more electromagnetic heads. The tape is moved by a motor-driven capstan along a path extending between two spools or reels and wrapped partially around the drum. The plane of rotation of the heads of the drum is disposed at an angle to the plane of movement of the tape, so that each head traverses the tape along successive tracks extending across the width of the tape at an angle to its centre line. The mechanism includes appropriate circuitry for encoding data into signals suitable for recording onto tape, including error-detection and correction codes, and for conditioning those signals into a form optimally matched to the characteristics of the recording media. For data retrieval, additional circuitry is provided for detecting magnetic field variations stored on the tape, deriving corresponding signals, conditioning those signals into a form for subsequent processing, decoding the encoded data and detecting and correcting errors.
A recent development has been the DDS3 format (defined in ECMA Standard ECMA-236 dated June 1996 “3,81 mm Wide Magnetic Tape Cartridge for Information Interchange—Helical Scan Recording—DDS-3 Format using 125 m Length Tapes”, the entire contents of which are incorporated herein by reference). In DDS3, error checking and detection is achieved by using a multilevel interleaved Reed-Solomon code providing at least two levels (C
1
, C
2
) and optionally a third level (C
3
) of error correction coding (ECC). In addition, to provide a final data check on reading, track checksums are generated corresponding to each track of data to be written on tape, and stored in the fragment headers, several of which are incorporated in each track. Thus on reading, the track checksum algorithm is applied to the data bytes retrieved from the tape and if this tracksum does not agree with that calculated and stored when the tape was recorded, the track is rejected.
SUMMARY OF THE INVENTION
It is desirable that the track checksum operates to reject as large a proportion as possible of failed tracks (that is ones containing either uncorrectable or miscorrected codewords—as to be described below). Although the existing track checksum operates reasonably well, the Applicant has discovered that there is an unexpected yet significant flaw in this system, such that the track checksum does not identify a large proportion of miscorrections. The Applicant's analysis has revealed that, in a miscorrected codeword in which the “corrections” occur in the data bytes only of the codeword, the track checksum will not reveal this failure. This phenomenon arises because the codewords are constructed to have the inherent property that the result of XORing all the bytes together (both data and parity) is zero. Also in DDS3 the track checksums are calculated by XORing the data bytes of the relevant track.
Given that the bytes of a good (or miscorrected) codeword XOR to zero, if the parity bytes of a particular good or miscorrected codeword XOR to, say, a binary value A, the data bytes must also XOR to the same value A (so that the data bytes and parity bytes together XOR to zero). In a miscorrection of this particular codeword, in which the “corrections” are contained in the data bytes only, the parity bytes will XOR to A as previously because they are unchanged. Even though the data bytes have changed, the data bytes will still XOR to A to fulfil the requirement that the miscorrection XORs to zero. However, the data bytes all contribute to the same checksum (also the result of an XOR operation) the track checksum will remain unchanged, and so, for this type of miscorrection, due to the correlation between the inherent XOR property of the codeword and the operation used to calculate the checksum, the track checksum will not reveal a miscorrected codeword in which all the “corrections” appear in the data bytes.
The Applicants have determined that modifying the track checksum algorithm so that is does not correlate with the XOR operation provides a reliable method for detecting miscorrections in the previous codeword. The ability to detect miscorrections reliably also has important beneficial consequences when third level C
3
correction is implemented.
In the past the Applicants have attempted to use the track checksum to identify C
2
codeword failures and mark them accordingly. Because of the interleaved and multi-level structure of the error correction coding, if a codeword fails at the C
1
or C
2
levels (in a three level system), knowing the position of that codeword in the array identifies in the codewords of the next level the locations of a number of bytes which are suspect. The structure of the error correction coding means that the bytes in a particular codeword map to positions in the subsequent codewords according to a known mapping. Thus a failed codeword at the C
2
stage can be used to flag particular bytes in the C
3
codeword to the C
3
correction algorithm so that these are treated as “erasures” rather than errors.
Thus when a complete C
2
codeword is marked as a failure, the corresponding data byte locations making up the codeword may be determined so that o the next, C
3
, level the location of the errors is known. A Reed-Solomon code having N parity bytes is capable of correcting ‘e’ errors and ‘v’ erasures, where 2e+v≦N, and an erasure is a bad byte in a known location. A typical C
3
correction codeword has just two parity bytes (i.e. N=2) and so the C
3
correction algorithm can either correct a single error (e=1) or two erasures (v=2). Where two corrections are made this is referred to as double error correction. Thus the ability reliably to mark miscorrected C
2
codewords as erasures would mean that the C
3
algorithm could perform double error correction. Until now, the absence of a reliable method of detecting miscorrections has meant that it has not been realistic to attempt double error correction at the C
3
stage.
Accordingly, the Applicants have provided a method and apparatus in which the track checksum provides considerably more reliable checking of miscorrections in one aspect this invention provides apparatus for storing a stream of data records on magnetic media, said apparatus including:
group formatting means for grouping said data records into groups of data bytes;
sub-group processing means for dividing each of said groups into subgroups, wherein each subgroup comprises data bytes corresponding to one or more data tracks;
track checksum calculating means for calculating one or more checksums for the or each data track,
means for transforming each subgroup into at least one respective array, each corresponding to a data track,
first error correction coding encoding means for encoding columns of the or each array to provide first (C
1
) ECC codewords comprising data bytes and parity bytes;
second error correction coding encoding means for encoding rows of the or each array to provide second (C
2
) ECC codewords comprising data bytes and parity bytes;
wherein said track checksum calculating means calculates a respective track checksum for the or each track such that, on decoding of said ECC codewords, a miscorrected codeword in which the miscorrections are in the data bytes only has no more than a substantially random probability of providing the same contribution to the corresponding track checksum as the corresponding original codeword.
It is emphasized that the
Hirose Toshiyuki
Morley Stephen
Osaki Shinya
Watkins Mark Robert
Williams Robert
Chung Phung M.
Hewlett-Packard Development Company L.C.
LandOfFree
Methods and apparatus for data storage on magnetic media... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for data storage on magnetic media..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for data storage on magnetic media... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158647