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.