Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-01-06
2003-11-18
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06651214
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to error correction code decoding mechanisms and, more particularly, to the decoding of Reed-Solomon error correction codes.
The use of increasingly higher density storage media in digital computer systems has caused an increase in the potential for defect-related data errors. To reduce data loss as a result of such data corruption, error correction codes are employed to correct the erroneous data.
Prior to storing data on a storage device, such as a magnetic disk or tape, it is encoded to form redundancy symbols. The redundancy symbols are appended to the data symbols to form code words, which are then stored on the storage device. When the stored data is retrieved from the storage device for decoding, the redundancy symbols provide information which allows the decoder to recognize errors and, if possible, reconstruct the original code word. For a detailed description of decoding, see “Error-Correcting Codes,” Second Edition, by W. Wesley Peterson and E. J. Weldon, Jr. (MIT Press, 1972). One widely-used error correction code is the Reed-Solomon code.
To correct errors, a Reed-Solomon decoder must determine the locations and values (or magnitudes) of the detected errors. The decoder first computes error syndromes, which it then uses to generate an error locator polynomial. Once the error locator polynomial has been generated, each error location and value may be determined.
Error locations are determined by solving for the roots of the error locator polynomial &sgr;(x) of degree t or less, where t is the number of errors that can be corrected. The solution or roots of the equation &sgr;(x)=0 correspond to the locations of the errors. These roots are of the form x=&agr;
i
, where &agr; is the primitive element of the Galois Field GF(p
q
) used to encode the data. Once all t roots have been found, the corresponding error values are calculated using the well-known Forney algorithm. The data can then be corrected to produce an error-free data symbol.
Some storage devices, such as magnetic tape, are capable of being read in a forward direction or a reverse direction. Some tape drives, such as nine track tape drives, use vertical code “slices”, for which a forward and reverse read is the same. Forward and reverse reads for longitudinal codes, such as the Reed-Solomon codes, are not the same. That is, the ordering of the code word symbols is reversed, which, in turn, reverses the order in which code word symbols are provided to the decoder. Prior data storage systems which store Reed-Solomon code words on tape drives read as well as decode the code words unidirectionally, or more specifically, in a forward direction only. To date, in order to read an n-symbol code word stored at a location prior to the current location of the head, the data storage system must rewind the tape to the beginning of the code word (i.e., symbol 0) and perform a read in the forward direction from symbol 0 to symbol n−1. These symbols are provided to the Reed Solomon decoder in the order in which they are read. Other storage systems which are designed to execute a “reverse read” command also rewind to the beginning of the code word to be read, and then read as well as decode that code word in a forward direction.
SUMMARY OF THE INVENTION
In general, the invention relates to a class of longitudinal codes which can be decoded during reads in both a forward direction and a reverse direction.
In one aspect of the invention, processing a code word includes receiving from a storage device symbols of a code word in a reverse order from that in which the symbols are normally received and performing a decoding procedure on the reverse order symbols.
Embodiments of the invention may include one or more of the following features.
The code word is a Reed-Solomon code word.
Performing the decoding procedure on the reverse order symbols of the Reed-Solomon code word includes generating reverse directional syndrome values from the reverse order symbols and converting the reverse directional syndrome values to syndrome values that correspond to syndrome values that would be generated for the symbols if the symbols were received in the order in which the symbols are normally received.
The code word is an m-bit n-symbol code word having R redundancy symbols, and a value of L associated with the code word is defined as −(R−1)/2 for odd values of R and 2
(m−1)
−R/2 for even values of R. Converting includes multiplying a first one of the reverse directional syndrome values by a first Galois field element &agr; of a power (n−1)*L, storing the result as a product value, and, for each successive one of the reverse directional syndrome values, updating the product value by multiplying the product value by a second field element &agr; of a power n−1.
Alternatively, performing the decoding procedure on the reverse order symbols includes determining that an error has occurred in at least one of the reverse order symbols, determining an error location for the error and adjusting the error location for the at least one of the reverse order symbols to an error location that corresponds to an error location that would be determined if the symbols had been received in the order in which the symbols are normally received.
In yet another alternative, performing the decoding procedure on the reverse order symbols includes determining error locator polynomial coefficients from the reverse directional syndromes and reversing the order in which the error locator coefficients are applied to an error location computation unit.
Processing a code word further includes receiving from a storage device symbols of a code word in an order in which the symbols are normally received and performing a decoding operation on the symbols.
In another aspect of the invention, processing a code word stored on a storage device includes reading symbols of the code word from a storage device in an order in which the symbols are normally read or a in a reverse order from that in which the symbols are normally read, and decoding the code word. Processing the code word further includes determining that the symbols are read in a reverse order from that in which the symbols are normally read. If it is determined that the symbols are read in the reverse order, then performing a decoding procedure on the code word.
Among the advantages of the bidirectional decoding mechanism of the present invention are the following. For storage devices such as tape drives, the data transfer rate can be increased by reading data in both forward and backward directions. That is, the tape drive does not have to rewind to the beginning of a code word in order to read and decode that code word. The bidirectional read capability is made practical given the flexibility of decoding the data as it is read from the tape in one direction or the other. Additionally, the mechanism offers a way to share decoder circuitry for both directions without a significant increase in decoding complexity.
Other features and advantages of the invention will be apparent from the following detailed description and from the claims.
REFERENCES:
patent: 3800281 (1974-03-01), Devore et al.
patent: 3811108 (1974-05-01), Howell
patent: 3868632 (1975-02-01), Hong et al.
patent: RE30187 (1980-01-01), Hong et al.
patent: 4201976 (1980-05-01), Patel
patent: 4551840 (1985-11-01), Fujii et al.
patent: 4870645 (1989-09-01), Herron
patent: 4884274 (1989-11-01), Rather
patent: 5469448 (1995-11-01), Denissen et al.
patent: 5621578 (1997-04-01), Matsumi et al.
patent: 2018095 (1979-10-01), None
Hall Dana E.
Weng Lih-Jyh
Daly, Crowley & Mofford LLP
De'cady Albert
Maxtor Corporation
Torres Joseph D.
LandOfFree
Bi-directional decodable Reed-Solomon codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bi-directional decodable Reed-Solomon codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bi-directional decodable Reed-Solomon codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3128133