Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-07-07
2003-04-22
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06553536
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data storage, and particularly to systems and methods employing a soft error correction algebraic decoder. More specifically, according to this invention, byte reliability numbers from a maximum likelihood (ML) decoder as well as a parity check success/failure from inner modulation code symbols are combined by a Reed-Solomon decoder in an iterative manner, such that the ratio of erasures to errors is maximized, for the purpose of minimizing the number of required check bytes.
BACKGROUND OF THE INVENTION
The use of cyclic error correcting codes in connection with the storage of data in storage devices is well established and is generally recognized as a reliability requirement for the storage system. Generally, the error correcting process involves the processing of syndrome bytes to determine the location and value of each error. Non-zero syndrome bytes result from the exclusive-ORing of error characters that are generated when data is written on the storage medium.
The number of error correction code (ECC) check characters employed depends on the desired power of the code. As an example, in many present day ECC systems used in connection with the storage of 8-bit bytes in a storage device, two check bytes are used for each error to be corrected in a codeword having a length of at most 255 byte positions. Thus, for example, six check bytes are required to correct up to three errors in a block of data having 249 data bytes and six check bytes. Six distinctive syndrome bytes are therefore generated in such a system. If there are no errors in the data word comprising the 255 bytes read from the storage device, then the six syndrome bytes are the all zero pattern. Under such a condition, no syndrome processing is required and the data word may be sent to the central processing unit. However, if one or more of the syndrome bytes are non-zero, then syndrome processing involves the process of identifying the location of the bytes in error and further identifying the error pattern for each error location.
The underlying mathematical concepts and operations involved in normal syndrome processing operations have been described in various publications. These operations and mathematical explanations generally involve first identifying the location of the errors by use of what has been referred to as the “error locator polynomial”. The overall objective of the mathematics involved employing the error locator polynomial is to define the locations of the bytes in error by using only the syndrome bytes that are generated in the system.
The error locator polynomial has been conventionally employed as the start of the mathematical analysis to express error locations in terms of syndromes, so that binary logic may be employed to decode the syndrome bytes into first identifying the locations in error, in order to enable the associated hardware to identify the error patterns in each location. Moreover, error locations in an on-the-fly ECC used in storage or communication systems are calculated as roots of the error locator polynomial.
Several decoding techniques have been used to improve the decoding performance. One such technique is minimum distance decoding whose error correcting capability relies only upon algebraic redundancy of the code. However, the minimum distance decoding determines a code word closest to a received word on the basis of the algebraic property of the code, and the error probability of each digit of the received word does not attribute to the decoding. That is, the error probability of respective digits are all regarded as equal, and the decoding becomes erroneous when the number of error bits exceeds a value allowed by the error correcting capability which depends on the code distance.
Another more effective decoding technique is the maximum likelihood decoding according to which the probabilities of code words regarded to have been transmitted are calculated using the error probability of each bit, and a code word with the maximum probability is delivered as the result of decoding. This maximum likelihood decoding permits the correction of errors exceeding in number the error correcting capability. However, the maximum likelihood decoding technique is quite complex and requires significant resources to implement. In addition, the implementation of the maximum likelihood decoding technique typically disregards valuable data such as bit reliability information.
However, in conventional decoding schemes the Reed Solomon code is not optimized to create the maximum number of erasures for given reliability/parity information, mainly due to the fact that such information is largely unavailable to the Reed Solomon decoder. Furthermore, the key equation solvers implemented in conventional decoders are not designed to solve a weighted rational interpolation problem.
Thus, there is still a need for a decoding method that reduces the complexity and resulting latency of the likelihood decoding technique, without significantly affecting its performance, and without losing bit reliability information.
Attempts to render the decoding process more efficient have been proposed. Reference is made to N. Kamiya, “On Acceptance Criterion for Efficient Successive Errors-and-Erasures Decoding of Reed-Solomon and BCH Codes,” IEEE Transactions on Information Theory, Vol. 43, No. Sep. 5, 1997, pages 1477-1488. However, such attempts generally require multiple recursions to calculate the error locator and evaluator polynomials, thus requiring redundancy in valuable storage space. In addition, such attempts typically include a key equation solver whose function is limited to finite field arithmetic, thus requiring a separate module to perform finite precision real arithmetic, which increases the implementation cost of the decoding process.
Therefore, there is still an unsatisfied need for a more efficient decoding algorithm that provides most likely erasure and error locator polynomials from a set of candidate erasures generated by a full Generalized Minimum Distance (GMD) decoding algorithm, without locating the roots of all candidate error locator polynomials, and which is implementable with minimal redundancy in the storage space.
SUMMARY OF THE INVENTION
In accordance with the present invention, a soft error correction algebraic decoder and an associated method use erasure reliability numbers to derive error locations and values. More specifically, symbol reliability numbers from a maximum likelihood (ML) decoder as well as a parity check success/failure from inner modulation code symbols are combined by a Reed-Solomon decoder in an iterative manner, such that the ratio of erasures to errors is maximized.
According to one feature of the present invention the decoder requires one recursion to calculate the error locator and evaluator polynomials, by calculating both of these polyonimals sequentially, thus minimizing the redundancy in the storage space.
The above and other features of the present invention are realized by a soft error correction (ECC) algebraic decoder and associated method for decoding Reed Solomon codes using a binary code and detector side information. The Reed Solomon codes are optimally suited for use on erasure channels. One feature of the present invention is to employ a key equation solver capable of performing both finite field arithmetic and finite precision real arithmetic to reduce the implementation cost of the decoding process.
According to one feature of the invention, a threshold adjustment algorithm qualifies candidate erasures based on a detector error filter output as well as modulation code constraint success/failure information, in particular parity check or failure as current modulation codes in disk drive applications use parity checks. This algorithm creates fixed erasure inputs to the Reed Solomon decoder.
A complementary soft decoding algorithm of the present invention teaches the use of a key equation solver algorithm that calculates error patterns obtained as a solution to a weighted
Hassner Martin Aureliano
New Richard Michael Hamilton
Patel Arvind Motibhai
Tamura Tetsuya
Trager Barry Marshall
Kassatly Samuel A.
Tu Christine T.
LandOfFree
Soft error correction algebraic decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Soft error correction algebraic decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft error correction algebraic decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3013167