Cyclic redundancy check

A cyclic redundancy check (CRC) is the result of a type of calculation made upon data, such as network traffic or computer files, in order to detect errors in transmission or duplication. CRC's are calculated before and after transmission or duplication, and compared to confirm that they are the same. The most widely used CRC calculations are constructed in ways such that anticipated types of errors, e.g., due to noise in transmission channels, are almost always detected. CRC's cannot, however, be safely relied upon to verify data integrity--i.e., that no changes whatsoever have occurred--since through intentional modification it is possible to cause changes that will not be detected through the use of a CRC; cryptographic hash functions must be used to verify data integrity.

The essential mathematical operation in the calculation of a CRC is binary division, and the remainder from the division determines the CRC. The main portion of the algorithm in pseudocode is as follows:

 shiftregister = initial value (commonly 0x0000... or 0xFFFF...)
 while bits remain in string:
   if MSB of shiftregister is set:
     shiftregister = (shiftregister leftshift 1) xor polynomial
     ("leftshift" assumes big-endian architecture)
   else:
     shiftregister = shiftregister leftshift 1
   xor next bit from the string into LSB of shiftregister
 output shiftregister

Note: Use of a lookup table containing the CRC's of all 256 possible bytes allows for an eight-fold increase in the speed of the algorithm.

CRC types are often identified by "polynomial," which is the number used as the divisor (given in hexadecimal format). One of the most commonly encountered of the CRC types is that used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. It uses the polynomial 0x04C11DB7, and is known as "CRC-32."

CRC's are often referred to as "checksums," but such designations are not accurate since, technically, a checksum is calculated through addition, not division.

External Links and Resources

• A Painless Guide to CRC Error Detection Algorithms, http://www.ross.net/crc/
• Understanding Cyclic Redundancy Check, http://www.4d.com/ACIDOC/CMU/CMU79909.HTM