Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-02-10
2001-04-24
DeCady, Albert (Department: 2184)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000, C714S807000
Reexamination Certificate
active
06223320
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to the field of error detection in digital communication systems and, in particular, to methods for generating and checking a cyclic redundancy check (CRC) in a message transferred over a digital communication system.
2. Related Art
Cyclic redundancy check (CRC) is an important error detection tool used in communication systems and data processing systems. CRC is a kind of checksum that is transmitted with data.
In a communication system wherein data is communicated between a source node and a target node over a communication link, the source node calculates the CRC of data to be transferred over the link using a predetermined polynomial. The source node then transmits the data along with the CRC over the link target node. The target node receives the data, independently generates the CRC of the received data using the predetermined generating polynomial, and compares the independently generated CRC with the CRC received from the source node. If the two CRC values match, no error is assumed to have occurred during the transmission. If the two CRC values do not match, an error is assumed to have occurred during the transmission. In this case, the target node may utilize error correction techniques to correct errors that have occurred during transmission and/or request re-transmission of the data by the source node.
In a data processing systems wherein data is transferred via an I/O bus from a storage device to memory for access by devices of the data processing system, the storage device calculates the CRC of data to be transferred over the I/O bus using a predetermined polynomial. The storage device then transmits the data along with the CRC over the I/O bus to memory. A processing unit independently generates the CRC of the received data using the predetermined generating polynomial, and compares the independently generated CRC with the CRC received from the storage device. If the two CRC values match, no error is assumed to have occurred during the transmission. If the two CRC values do not match, an error is assumed to have occurred during the transmission. In this case, the processing unit may utilize error correction techniques to correct errors that have occurred during transmission and/or request re-transmission of the data by the storage device.
A more detailed description of the use of CRC for error detection may be found in Ritter, T., February 1986, “Great CRC Mystery. Dr. Dobb's Journal of Software Tools”, 11(2), pgs 26-34, 76-83, herein incorporated by reference in its entirety.
The basic CRC generation algorithm for a W-bit CRC can be written as the following pseudo-code:
1. CRC=0 (Initialization)
2. Augment message by W zeros
3. pop=top bit of CRC
4. shift CRC left by 1 bit, read in 1 bit from the message
5. If pop=1, CRC=XOR (CRC, polynomial)
6. If more message bits, goto step 3.
This algorithm is very time consuming since it operates on 1 bit at time.
This simple algorithm can be speeded up by grouping the operations on a number of bits. The most convenient grouping is 8 bits (or 1 byte) as shown in R. N. Williams, “A Painless Guide to CRC Error Detection Algorithms”, Version 3, Aug. 19, 1993, ftp://ftp.rocksoft.corn/clients/rocksoft/papers/crc-v3.txt, herein incorporated by reference in its entirety. In this example, step 3 is modified to pop the top byte of the CRC and step 4 is modified to shift the CRC by 8 bits and read in 8 bits of the message. In addition step 5 is modified as follows: the top byte of the CRC identified in step 3 and the 8 bits of the message identified in step 4 are combined using an XOR operation, and the result is used an index into a table. The table contains the 256 entries storing the 256 precomputed CRCs for the range of 8 bit values (00-FF). The resultant CRC read from the table is then combined with the CRC shifted by 8 bits in step 4 using an XOR operation to form the new updated CRC value, and the operation continues to step 5.
Note that such table driven algorithms require a large table (i.e., 256 W-bit entries) and utilize a single table look-up per iteration.
SUMMARY OF THE INVENTION
The above-stated problems and related problems of the prior art are solved with the principles of the present invention, efficient CRC generation utilizing parallel table lookup operations wherein relevant data in the data stream is identified and partitioned into a plurality of intervals. A CRC value is determined for each interval by partitioning the interval into a plurality of chunks, loading from persistent storage a table of CRC values for a range of chunks, determining a CRC value for each of the chunks with parallel table lookup operations on the table, and combining the CRC values for the chunks. The CRC values for each of the intervals is combined to generate the CRC for the relevant data. The parallel table look operation is preferably a vector permute instruction that is executed by a SIMD-style vector unit.
REFERENCES:
patent: 5537421 (1996-07-01), Dujari et al.
patent: 5619516 (1997-04-01), Li et al.
patent: 5778013 (1998-07-01), Jedwab
patent: 5959786 (1999-09-01), Bellenger
patent: 6029186 (2000-02-01), DesJardines et al.
Abbott et al. Broadband Algorithms with the MicroUnity Mediaprocessor, IEEE, p. 349-354, 1996.*
Griffiths et al., The Tea-Leaf Reader Algorithm: An efficient Implementation of CRC-16 and CRC-32, ACM, p. 617-620, Jul. 1987.*
Ramabadran et al., A Tutorial on CRC Computations, IEEE, p. 62-75, 1988.*
Albertengo et al., Parallel CRC Generation, IEEE, p. 63-71, Oct. 1990.*
Sarwate, Computation of Cyclic Redundancy Checks via Table Look-Up, ACM p. 1008-1013, Aug. 1988.*
“A Painless Guide to CRC Error Detection/Algorithms”, R.N. Williams, Aug. 19, 1993, ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt.
“The Great CRC Mystery”, T. Ritter, 1986, Dr. Dobb's Journal of Software Tools, Feb. 11(2):26-34, 76-83, http://www.io.com/~ritter/ARTS/CRCMYST.HTM.
Dubey Pradeep Kumar
Joshi Sanjay Mukund
Kaplan Marc Adam
Chase Shelly A
De'cady Albert
International Business Machines - Corporation
LandOfFree
Efficient CRC generation utilizing parallel table lookup... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient CRC generation utilizing parallel table lookup..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient CRC generation utilizing parallel table lookup... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2518003