Cyclic redundancy check

A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum, which is a small number of bits, from a large block of data, such as a packet of network traffic or a block of a computer file, in order to detect errors in transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards to confirm that no changes occurred. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.
Contents 
Introduction
CRCs are based on division in a commutative ring, namely the ring of polynomials over the integers modulo 2. In simpler terms, this is the set of polynomials where each coefficient is only one bit, and arithmetic operations wrap around. For example:
<math>(x^2 + x) + (x + 1) = x^2 + 2x + 1 = x^2 + 1<math>
Two becomes zero because 2 is 10 in binary, and we discard all bits except the last one. Multiplication is similar:
<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x = x^3 + x<math>
We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x^{3} + x^{2} + x by x + 1. We would find that
<math>x^3 + x^2 + x = (x + 1)(x^2 + 1)  1 = (x + 1)(x^2 + 1) + 1.<math>
In other words, the division yields a quotient of x^{2} + 1 with a remainder of 1, which, since it is odd, has a last bit of 1.
Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide by another fixed polynomial. The coefficients of the remainder polynomial are the CRC, and there are simple, efficient algorithms for computing this remainder, such as the one shown below. CRCs are often referred to as "checksums," but such designations are not strictly accurate since, technically, a checksum is calculated through addition, not division.
The main portion of the algorithm can be expressed in pseudocode as follows:
function crc(bit array bitString[1..len], int polynomial) { shiftRegister := initial value // commonly all 0 bits or all 1 bits for i from 1 to len { if most significant bit of shiftRegister xor bitString[i] = 1 shiftRegister := (shiftRegister left shift 1) xor polynomial else shiftRegister := shiftRegister left shift 1 } return shiftRegister }
Note: A common speedup uses a lookup table indexed by multiple mostsignificant bits of the shiftRegister
to process multiple bits at once. A 256entry lookup table is a particularly common choice.
There are two variations which can be applied to the above implementation; applying one or both gives a total of four equivalent ways to compute a checksum:
 The
shiftRegister
can be reversed, so its leastsignificant bit is tested and it is shifted to the right by 1 bit each step. This requires apolynomial
with its bits reversed, and produces a bitreversed result. This variant is actually the one most commonly in use.  Instead of changing multiple bits in the
shiftRegister
based on the xor of one bit of theshiftRegister
and one bit of thebitString
, it is possible to xor (compute the parity of) all the bits of theshiftRegister
selected by thepolynomial
and thebitString
and add that single bit to theshiftRegister
. With suitable adjustments to thepolynomial
, this also produces the same remainder. This variation is difficult in software, but used in some hardware implementations, and is often used when describing the close relative to a CRC, the linear feedback shift register.
The specific CRC is defined by the polynomial used. To produce an nbit CRC requires a degreen polynomial, of the form x^{n} + … + 1. This is naturally expressed as an n+1bit string, but the leading (x^{n}) term is normally implicit, leaving an nbit string Thus, depending on the bitorder convention used, the standard CRC16, x^{16}+x^{15}+x^{2}+1, will be represented as the hexadecimal number 0x8005 or as 0xa001.
One of the most commonly encountered is known as CRC32, used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. Its polynomial can be written 0x04C11DB7 or 0xEDB88320.
Polynomials and types
CRC8  x^{8} + x^{2} + x + 1 
CRCCCITT  x^{16} + x^{12} + x^{5} + 1 
CRC16 (IBM)  x^{16} +x^{15} + x^{2} + 1 
CRC32 (802.3)  x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^{8} + x^{7} + x^{5} + x^{4} + x^{2} + x + 1 
CRC32c (Castagnoli)  x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + 1 
CRCs and data integrity
While useful for error detection, CRCs cannot be safely relied upon to verify data integrity (that no changes whatsoever have occurred), since, because of the linear structure of CRC polynomials, it is extremely easy to intentionally change data without modifying its CRC. Cryptographic hash functions can be used to verify data integrity.
See also
External links
 The CRC Pitstop (http://www.ross.net/crc/)
 A Painless Guide to CRC Error Detection Algorithms (http://www.repairfaq.org/filipg/LINK/F_crc_v3.html)
 Understanding Cyclic Redundancy Check (http://www.4d.com/docs/CMU/CMU79909.HTM)
 Jacksum (http://www.jonelo.de/java/jacksum/index.html) (a program with various message verification functions)
 checksums, CRCs, and their source code http://www.netrino.com/Connecting/199911/, http://www.netrino.com/Connecting/199912/, http://www.netrino.com/Connecting/200001/de:Zyklische Redundanzprüfung
fr:Cyclic redundancy check nl:Cyclic Redundancy Check ja:巡回冗長検査 pl:CRC ru:CRC