Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-16
2002-08-20
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06438724
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to ensuring the integrity of transmitted or stored data, and in particular, to using cyclic redundancy check data to detect errors in Reed-Solomon encoded corrected data.
BACKGROUND OF THE INVENTION
A primary concern in the transfer of digital data is the integrity of the data. A data transfer may be from memory to a processor in a computer, from one computer to another computer over a local area network or telephone line, from a deep space probe to earth, or from storage media to a storage controller. Each type of data transfer has its own special requirements for data integrity, which depend on factors such as the inherent reliability of the transfer medium and the consequence of an error.
In some applications a simple parity check is deemed sufficient to ensure data integrity and data is simply re-sent or re-read if an error is detected. In other applications, more elaborate schemes are used to ensure data integrity, which include the ability to correct as well as to detect transmission errors. In applications, such as storage media, the increasing density of information storage requires the use of improved schemes to ensure data integrity.
A common scheme that is used to ensure data integrity is Reed-Solomon encoding. Reed-Solomon encoding provides error correction, as well as error detection. However, Reed-Solomon encoding is limited in that it cannot correct all errors. Further, a problem called miscorrection arises with Reed-Solomon encoding. When miscorrection occurs, the error correction scheme has failed to correct at least some of the errors, or has added additional errors, and incorrectly indicates that all errors have been corrected. The data is corrupt, yet it is indicated to be good. This is an unacceptable failure for a data integrity scheme. A need arises for a data integrity scheme that can detect that errors remain when miscorrection occurs.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for ensuring the integrity of data that can detect errors that remain when the data correction scheme fails to correct at least some of the errors, or has added additional errors. A block of data to be processed is received. The block of data comprises a data portion, cyclic redundancy check symbols, Reed-Solomon check symbols, and includes at least one error. The cyclic redundancy check symbols are generated using a cyclic redundancy check generator polynomial having a plurality of roots. The Reed-Solomon check symbols are generated using a Reed-Solomon generator polynomial having a plurality of roots At least one cyclic redundancy check syndrome is generated for the received block of data using the roots of the cyclic redundancy check generator polynomial. An attempt is made to correct the error in the block of data. The cyclic redundancy check syndrome is updated to correspond to the corrected block of data and it is determined whether the error has been corrected using the updated cyclic redundancy check syndrome.
The roots of the cyclic redundancy check generator polynomial meet the following conditions:
(a) the exponents of the roots are distinct values or all values modulo each prime factor of the cycle length of the underlying finite field,
(b) the roots do not overlap the roots of the Reed-Solomon generator polynomial, and
(c) at least one of the roots is a primitive element of the finite field.
In addition, in one embodiment of the present invention, the roots of the cyclic redundancy check generator polynomial further meet the following conditions:
(d) no root is a power of two of any other root, and
(e) the roots do not overlap any power of two of any root of the Reed-Solomon generator polynomial.
In order to update the cyclic redundancy check syndromes, the location and magnitude of the error within the received data is determined using the Reed-Solomon error correction data. The location of the error within the received data is translated to the location within the cyclic redundancy check error detection data. The translated error location is exponentiated by a root of the cyclic redundancy check polynomial, this is multiplied by the error value, and then added to the cyclic redundancy check syndromes.
The roots are further selected so that the exponentiation may be performed by a combination of exponentiations by powers of two and multiplications.
The Reed-Solomon check symbols are generated based on the data portion of the data block. In one embodiment of the present invention, a deterministically altered data stream is generated based on the data portion of the data block and the cyclic redundancy check symbols are generated based on the deterministically altered data stream. The deterministically altered data stream is generated by performing an operation on a symbol of the data portion based on the position of that symbol within the Reed-Solomon codeword.
REFERENCES:
patent: 4410989 (1983-10-01), Berlekamp
patent: 4564945 (1986-01-01), Glover et al.
patent: 4782490 (1988-11-01), Tenengolts
patent: 4847705 (1989-07-01), Weng et al.
patent: 5027357 (1991-06-01), Yu et al.
patent: 5157669 (1992-10-01), Yu et al.
patent: 5375127 (1994-12-01), Leak et al.
patent: 5383204 (1995-01-01), Gibbs et al.
patent: 5384786 (1995-01-01), Dudley et al.
patent: 5446745 (1995-08-01), Gibbs
patent: 5455814 (1995-10-01), Sako
patent: 5465260 (1995-11-01), Zook
patent: 5491701 (1996-02-01), Zook
patent: 5724368 (1998-03-01), Zook
Kovak et al. “ACE: A VLSI Chip for Galois Field GF (2m) Based Exponentiation” IEEE Transactions on Circuits and Systems, vol. 43, No. 4, Apr. 1996.
“Magneto-Optic Data Integrity Using CRC Checksum” IBM TDB, vol. 37, No. 3, Mar. 1994.
“Some Codes that Combine ECC with Modulation” IBM TDB, vol. 32, No. 12, May 1990.
Cox Charles Edwin
Hafner James Lee
Hassner Martin Aureliano
Koetter Ralph
Patel Arvind Motibhai
Baker Stephen M.
International Business Machines - Corporation
Morgan & Finnegan
Tran Khanh Q.
LandOfFree
Method and apparatus for deterministically altering cyclic... 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 deterministically altering cyclic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for deterministically altering cyclic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2936192