Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-01-08
2003-06-03
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S781000
Reexamination Certificate
active
06574774
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to error detection and/or correction. More particularly, the invention relates to a physical or logical block address (PBA or LBA) transfer and recovery system and method for interleaved Reed-Solomon (RS) codes that can distinguish between a block address error and an uncorrectable data error and that permits recovery of the actual block address in the event of a physical or logical block address error.
BACKGROUND OF THE INVENTION
Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The current trend is to store greater amounts of digital data in smaller areas on the storage medium. This trend increases the probability of errors. To correct the errors, error correction coding is used. There are various error correction coding techniques. One class of such error correction codes is the well-known Reed Solomon (RS) codes. The Reed Solomon (RS) encoding technique appends to each block of b user data symbols 2t redundancy symbols to create a codeword (where t represents the designed symbol error correcting capacity of the code). There are b+2t symbols in a RS codeword. The RS codewords are transmitted to and from the storage medium with a certain error probability. During the decoding phase, certain error patterns introduced from the transmission of the data from the storage medium can be detected and the original data reconstructed by analyzing the received data. See, for example, the reference “Error Control Systems for Digital Communication and Storage, by Stephen B. Wicker published 1995 by Prentice Hall, Inc., Englewood Cliffs, N.J. 07632, ISBN 0-13-200809-2, which is hereby incorporated by reference, for a discussion of some conventional error detection and control systems and methods.
Often errors occur in bursts rather than in random patterns, so that several consecutive bytes or symbols are in error. (In this description a symbols are used synonymously with bytes and it is understood that where the term byte is used, the number of bits is arbitrary and is not restricted to 8-bits, 16-bits or the like, but may take on any number of bits, for example 10 bits, 12 bits or other numbers.) If all the errors in such a burst are confined to a single codeword, the error correction coding technique may not be able to correct these errors, since the coding technique's capacity is limited to correcting a predefined number of errors and the error burst may exceed this capacity. Interleaving is often used to overcome this problem. Interleaving is a technique that distributes user data symbols over several codewords so that the symbols from any given codeword are well separated during transmission. When the codewords are reconstructed during the decoding process, error bursts introduced during the transmission are broken up and spread across several codewords. The distribution of the errors in this manner is done so that the number of errors present in a codeword is more likely to be within the capacity of the error correction technique.
Encoded data is stored at a certain physical block address (PBA) on the storage medium. The PBA may also be associated with a particular Logical Block Address (LBA) so that references to PBAs in this discussion also apply to LBAs. Normally, each location on a recording media has a physical block address; however, since recording media such as magnetic discs, magneto-optical discs, magnetic tapes, and the like may have at least some imperfections, the media associated with some physical block addresses may be remapped to some different physical block addresses. Each of the available (error-free) physical block addresses is identified by a logical block address. In traditional systems and devices, the PBA (or LBA) can be used in the encoding/decoding process in such a way that if encoded data is decoded using a different PBA (or LBA), then the decoding process will fail, that is, the data will appear to have uncorrectable errors.
In one traditional approach, a disc drive computer system
100
having a host computer
102
, a rotatable magnetic disc drive
104
having one or more discs for storing data thereupon, and a error correction code encoder/decoder unit (ECC encoder/decoder)
106
is provided as illustrated in
FIG. 1
for the write or encoder operation. (A corresponding block diagram
101
for the readback or decoder operation is illustrated in FIG.
2
and described in greater detail hereinafter. ECC encoder/decoder
106
provides a first path between host
102
and disc
104
for user data D(x)
105
with only a multiplexer or switch
108
interposed between host
102
and disc
104
, for selecting either data D(x)
105
or parity P(x)
107
as the information
109
to be written to disc
104
. The manner in which data and parity are written to disc drive storage is well known in the art and not described further here. It is also understood that an actual implementation may include buffers, registers, clock signals, and other logic to implement the circuit, but being conventional are not described in order not to obscure the invention or its differences from traditional systems, devices, or methods.
A second path from host
102
to disc
104
is defined through syndrome/parity generator
110
which receives the output of exclusive-or (XOR) circuit
112
formed by the XOR of data D(x) and the output
113
of randomizer
116
. Randomizer
116
receives the actual PBA (or LBA)
117
as a seed to generate a pseudo-random sequence output as is known in the art. Parity/syndrome generator
110
generates parity P(x) on the basis of the sum signal output by XOR
112
. Multiplexer
108
selects or passes either data D(x) or parity P(x) in response to the state of a data/parity select control signal
119
.
Randomizer unit
116
is important in the operation of the traditional ECC encoder/decoder unit
106
and is seeded with the intended or actual PBA value for writing (encoding) and with the expected or predicted PBA value
111
for readback (decoding). As described previously, the predicted or estimated PBA (or LBA)
111
may for example be a 4-byte value that specifies the location on the storage media, for example the track and sector on a magnetic disc, where the information is expected to be written to or read from. Seeding refers to a procedure for encoding or decoding in which the randomizer is preset with the value of the PBA (or LBA) prior to generating the pseudo-random sequence. The use of a seed to generate a pseudo-random sequence is well known in the art and not described further here.
The output sequence
113
of randomizer
116
is XOR'ed by XOR circuit
112
with the write data D(x)
105
arriving from host
102
for the parity generation during writing, and XOR'ed by XOR
112
with the read data D(x)
105
for the syndrome generation during readback (See
FIG. 2
for readback configuration). In the read or readback mode of operation, data D(x) arrives from the disc
104
and is communicated to host
102
as illustrated in FIG.
2
. The readback or decoder mode also employs an error correction unit (ECU)
120
which receives syndromes
121
generated by syndrome/parity generator
110
generates an uncorrectable error signal or indication
121
if the actual PBA (or LBA) is not equal to the expected PBA (or LBA) determines whether an error has occurred, but does not require the multiplexer
108
as the host has no need for parity and only receives the data D(x).
Unfortunately, if the seed values (in this case the PBA or LBA) used by randomizer
116
for write and readback operations of the same data are different, then the write output randomizer sequence and read output randomizer sequences will also be different and will not match or cancel each other as expected. Seeding values will be different, for example, if the estimated PBA (or LBA) is different from the actual PBA. When an error is detected, ECU
120
merely identifies that an uncorrectable error has
Berger Derek J.
Cesari Kirk A.
Seagate Technology LLC
Tu Christine T.
LandOfFree
Physical block address recovery apparatus system and method... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Physical block address recovery apparatus system and method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Physical block address recovery apparatus system and method... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129995