Jump to content

Cyclic redundancy check

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 205.188.209.77 (talk) at 01:33, 17 January 2003 (Re-worded paragraph on "polynomial."). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 pseudo-code is as follows: 

shiftreg = initial value (commonly 0)
while bits remain in string:
  if MSB of shiftreg is set:
    shiftreg = (shiftreg shl 1) xor polynomial
  else:
    shiftreg = shiftreg shl 1
  xor next bit from the string into LSB of shiftreg
output shiftreg

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, and WinZip. It uses the polynomial 0x04C11DB7, and is often referred to 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.

On the Web

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&oldid=601650"