Cyclic redundancy check
From Wikipedia, the free encyclopedia
Jump to: navigation (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#column-one), search (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#searchInput)
<!-- start content --> A cyclic redundancy check (CRC) is a type of hash function (http://en.wikipedia.org/wiki/Hash_function) used to produce a checksum (http://en.wikipedia.org/wiki/Checksum) – a small, fixed number of bits – against a block of data, such as a packet of network traffic or a block of a computer file (http://en.wikipedia.org/wiki/Computer_file). The checksum is used to detect errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by recipient to confirm that no changes occurred on transit. CRCs are popular because they are simple to implement in binary hardware (http://en.wikipedia.org/wiki/Computer_hardware), are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.
<table id="toc" class="toc" summary="Contents"> <tbody><tr> <td> Contents
[hide (javascript:toggleToc())]
1 Introduction (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Introduction)
2 Implementation (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Implementation)
3 Variations (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Variations)
4 Reversed representations and reciprocal polynomials (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Reversed_representations_a nd_reciprocal_polynomials)
4.1 Polynomial representations (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations )
4.2 Reciprocal polynomials (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Reciprocal_polynomials)
5 Error detection strength (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Error_detection_strength)
6 CRC polynomial specifications (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC_polynomial_specificati ons)
7 CRCs in common use (in ITU-IEEE syntax) (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRCs_in_common_use_.28in_I TU-IEEE_syntax.29)
8 CRCs and data integrity (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRCs_and_data_integrity)
8.1 When CRCs collide (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#When_CRCs_collide)
8.2 Designing CRC polynomials (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_CRC_polynomials)
9 See also (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#See_also)
10 References (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#References)
11 External links (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#External_links)
</td> </tr> </tbody></table> <script type="text/javascript"> //<![CDATA[ if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } //]]> </script>
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=1)]
Introduction
A CRC "checksum" is the remainder of a binary division with no bit carry (XOR used instead of subtraction), of the message bit stream, by a predefined (short) bit stream of length n, which represents the coefficients of a polynomial. Before the division, n zeros are appended to the message stream.
CRCs are based on division in the ring of polynomials (http://en.wikipedia.org/wiki/Polynomial_ring) over the finite field (http://en.wikipedia.org/wiki/Finite_field) GF(2) (the integers modulo 2 (http://en.wikipedia.org/wiki/Modular_arithmetic)). In simpler terms, this is the set of polynomials where each coefficient is either zero or one (A.K.A binary or base 2 numbers), and arithmetic operations wrap around. For example:
<dl><dd>http://upload.wikimedia.org/math/4/5/6/456eb698ca7db3a8a331ace23913de8d.png</dd></dl> Two becomes zero because addition of coefficients is performed modulo 2. Multiplication is similar:
<dl><dd>http://upload.wikimedia.org/math/e/7/7/e77b9b6eb9f43431f8d413c20d5a5f89.png</dd></dl> We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x<sup>3</sup> + x<sup>2</sup> + x by x + 1. We would find that
<dl><dd>http://upload.wikimedia.org/math/8/d/a/8dabf57b25020c30de2f7c4ad31c54bc.png</dd></dl> In other words,
<dl><dd>(x<sup>3</sup> + x<sup>2</sup> + x) = (x<sup>2</sup> + 1)(x + 1) − 1</dd></dl> The division yields a quotient of x<sup>2</sup> + 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, after first multiplying by x<sup>n</sup> where n is the degree (http://en.wikipedia.org/wiki/Degree_of_a_polynomial) of the fixed polynomial. The coefficients of the remainder polynomial are the CRC.
In the above equations, x<sup>2</sup> + x + 1 represents the original message bits <code>111</code>, x + 1 acts as the key, and the remainder 1 (equivalently, x<sup>0</sup>) is the CRC. The degree of the key is 1, so we first multiplied the message by x<sup>1</sup> to get x<sup>3</sup> + x<sup>2</sup> + x.
In general form:
<dl><dd>http://upload.wikimedia.org/math/5/e/2/5e2c3dd663744534afa89240dc45f0c9.png</dd></dl> Here M(x) is the original message polynomial. K(x) is the key polynomial, with degree n. The bits of http://upload.wikimedia.org/math/2/a/c/2ac3d9564048dfb5e49283f823189d36.png are the original message with n zeros added at the end. R(x) is the remainder polynomial, which is the CRC 'checksum'. In communication, the sender attaches the n bits of R after the original message bits of M and sends them out (in place of the zeros). The receiver takes M and R and checks whether http://upload.wikimedia.org/math/a/9/9/a997af4f5f5e9a204b486d8d4d833bd4.png is divisible by K(x). If it is, then the receiver assumes the received message bits are correct. Note that http://upload.wikimedia.org/math/a/9/9/a997af4f5f5e9a204b486d8d4d833bd4.png is exactly the string of bits the sender sent; this string is called the codeword.
CRCs are often referred to as "checksums (http://en.wikipedia.org/wiki/Checksum)," but such designations are not strictly accurate since, technically, a checksum would be calculated through addition, and not through division as is the case with CRCs.
Closely related to CRCs are error-correcting codes (http://en.wikipedia.org/wiki/Error-correcting_code), which allow the correct message to be reconstructed in the face of transmission errors. These codes are based on closely related mathematical principles.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=2)]
Implementation
There are simple, efficient algorithms for computing the CRC of a block of data, such as those shown below. (Warning, this algorithm is wrong, go look inside the discussion to discuss about it)
One common bitwise algorithm is based on a shift register which has a size in bits equal to the degree of the chosen polynomial. The main portion of the algorithm can be expressed in pseudocode (http://en.wikipedia.org/wiki/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 (http://en.wikipedia.org/wiki/Most_significant_bit) of shiftRegister = 1 {
// Shift left, place data bit as LSB, then divide
shiftRegister := shiftRegister left shift 1
shiftRegister := shiftRegister or bitString
shiftRegister := shiftRegister xor (http://en.wikipedia.org/wiki/XOR) polynomial
} else {
// shiftRegister is not divisible by polynomial yet.
// Just shift left and bring current data bit onto LSB of shiftRegister
shiftRegister := shiftRegister left shift 1
shiftRegister := shiftRegister or bitString
}
}
return shiftRegister
}
</pre> Another common algorithm uses a lookup table (http://en.wikipedia.org/wiki/Lookup_table) indexed by multiple most-significant bits of the <code>shiftRegister</code> to process multiple bits at once. A 256-entry lookup table is a particularly common choice.
Another implementation uses a shift register, but instead of changing multiple bits in the <code>shiftRegister</code> based on the xor of one bit of the <code>shiftRegister</code> and one bit of the <code>bitString</code>, it is possible to xor (compute the parity (http://en.wikipedia.org/wiki/Parity) of) all the bits of the <code>shiftRegister</code> selected by the <code>polynomial</code> and the <code>bitString</code> and add that single bit to the <code>shiftRegister</code>. With suitable adjustments to the <code>polynomial</code>, this also produces the same remainder. This algorithm is usually inefficient 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 (http://en.wikipedia.org/wiki/Linear_feedback_shift_register).
The specific CRC produced is defined by the polynomial used. To produce an n-bit CRC requires a degree-n polynomial, of the form http://upload.wikimedia.org/math/2/c/f/2cf4a5049832668a824f3cfee61d08c6.png. This is naturally expressed as an (n + 1)-bit string, but the leading x<sup>n</sup> term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the CRC-16-IBM polynomial x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1, will be represented as the hexadecimal (http://en.wikipedia.org/wiki/Hexadecimal) number 0x8005 or as 0xA001.
One of the most commonly encountered CRC algorithms is known as CRC-32, used by (among others) Ethernet (http://en.wikipedia.org/wiki/Ethernet), FDDI (http://en.wikipedia.org/wiki/FDDI), ZIP (http://en.wikipedia.org/wiki/ZIP_%28file_format%29) and other archive formats (http://en.wikipedia.org/wiki/Archive_formats), and PNG (http://en.wikipedia.org/wiki/PNG) image format (http://en.wikipedia.org/wiki/Image_format). Its polynomial can be written 0x04C11DB7, or 0xEDB88320 by reversing the bit string derived from the polynomial as explained above. The W3C webpage on PNG (http://en.wikipedia.org/wiki/PNG) includes an appendix with a short and simple table-driven implementation (http://www.w3.org/TR/PNG-CRCAppendix.html) in C of CRC-32. Despite the popular acclaim, it is important to notice that the polynomial in question was arbitrarily chosen and generally exhibits very poor error detection properties (in terms of Hamming distance (http://en.wikipedia.org/wiki/Hamming_distance) per given block size) compared to polynomials selected by algorithmic means<sup id="_ref-cast93_0" class="reference">[1] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-cast93)</sup> <sup id="_ref-koop02_0" class="reference">[2] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-koop02)</sup>.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=3)]
Variations
There are several variations on CRCs
The <code>shiftRegister</code> can be reversed, so its least-significant bit is tested and it is shifted to the right by 1 bit each step. This requires a <code>polynomial</code> with its bits reversed, and produces a bit-reversed result. [i]This variant is actually the one most commonly in use.
The data bits may be read into the shift register either most significant first, or least significant bit first. When used in communication protocols, the CRC is usually calculated in the order the bits are sent over the physical layer (http://en.wikipedia.org/wiki/Physical_layer), to preserve the CRC's burst error (http://en.wikipedia.org/wiki/Error_burst) detection characteristics.
To check the CRC, instead of calculating the CRC on the message and comparing it to the CRC, a CRC calculation may be run on the entire codeword. If the result is zero, the check passes. This works because the codeword is http://upload.wikimedia.org/math/2/b/6/2b6d1780c1ef541df6af14635fafc365.png, which is always divisible by K(x).
The shift register may be initialized with ones instead of zeroes. Equivalently, the first n bits of the message may be inverted before feeding them into the algorithm. The reason to do this is because an unmodified CRC does not distinguish between two messages which differ only in the number of leading zeros. When this inversion is done, the CRC does distinguish between such messages.
The CRC may be inverted before being appended to the message stream. When this is done, the CRC may be checked either by the straightforward method of computing the CRC on the message, inverting it, and comparing with the CRC in the message stream, or by calculating the CRC on the entire message. In the latter method, the result for a correct message will not be zero, but instead will be the result of dividing http://upload.wikimedia.org/math/8/d/b/8db68d0cfd06dd25da535c47cff1e91b.png by K(x). This result is called the check polynomial C(x), and its hexadecimal representation is sometimes called a magic number (http://en.wikipedia.org/wiki/Magic_number_%28programming%29).
When using the CRC-32 polynomial and the CRC-16-CCITT polynomial, by convention both inversions are performed. The check polynomial for CRC-32 is C(x) = x<sup>31</sup> + x<sup>30</sup> + x<sup>26</sup> + x<sup>25</sup> + x<sup>24</sup> + x<sup>18</sup> + x<sup>15</sup> + x<sup>14</sup> + x<sup>12</sup> + x<sup>11</sup> + x<sup>10</sup> + x<sup>8</sup> + x<sup>6</sup> + x<sup>5</sup> + x<sup>4</sup> + x<sup>3</sup> + x + 1.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=4)]
Reversed representations and reciprocal polynomials
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=5)]
Polynomial representations
All the well-known CRC polynomials of degree n have two common hexadecimal representations:
A hexadecimal number with n bits, the least significant bit of which is always 1, the most significant bit representing the x<sup>n − 1</sup> coefficient and the least significant bit representing the x<sup>0</sup> coefficient.
A hexadecimal number with n bits, the most significant bit of which is always 1, the most significant bit representing the x<sup>0</sup> coefficient and the least significant bit representing the x<sup>n − 1</sup> coefficient.
The first of these is the normal representation, and gives the correct results when used in a CRC algorithm using a left shift. The second is called the reversed representation, because it is the bitwise reverse of the normal representation. When used in a CRC algorithm using a right shift, the reverse representation gives the bitwise reverse of the results that using the left shift algorithm with the normal representation does.
Using the normal representation in the right shift algorithm or the reversed one in the left shift algorithm gives incorrect results.
In both these representations the x<sup>n</sup> coefficient is omitted and understood to be 1.
There is a third representation in use, from a paper by P. Koopman and T. Chakravarty <sup id="_ref-koop02_1" class="reference">[2] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-koop02)</sup><sup id="_ref-koop04_0" class="reference">[3] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-koop04)</sup>
A hexadecimal number with n bits, the most significant bit of which is always 1, the most significant bit representing the x<sup>n</sup> coefficient and the least significant bit representing the x<sup>1</sup> coefficient. The x<sup>0</sup> coefficient is omitted and understood to be 1.
This representation (call it Koopman) has the advantage that (like the normal representation) the coefficients are retained in their usual mathematical order, and (like the reversed representation) the order of the polynomial can be determined directly from the representation. Unfortunately, it will not produce correct results in either the left- or right- shift versions of the CRC algorithm.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=6)]
Reciprocal polynomials
A reciprocal polynomial is created by assigning the x<sup>n</sup> through x<sup>0</sup> coefficients of one polynomial to the x<sup>0</sup> through x<sup>n</sup> coefficients of a new polynomial. Example: The reverse of x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1 is x<sup>16</sup> + x<sup>14</sup> + x<sup>1</sup> + 1. The most interesting property of reciprocal polynomials, when used in CRCs, is that they have the exact same error-detecting strength as the polynomials they are reciprocals of. The reciprocal of a polynomial generates the same codewords — that is, the bit strings consisting of a valid CRC appended to a message — as the original polynomial, only bit reversed. But the reciprocal polynomial is not the same as the original polynomial, and the CRCs generated using it are not the same (even modulo bit reversal) as those generated from the original polynomial.
Another interesting property of reciprocal polynomials is related to their representation. Consider again the CRC-16-IBM polynomial x<sup>16</sup> + x<sup>15</sup> + x<sup>2</sup> + 1 and its reciprocal. These are its representations
Normal original: 0x8005
Reversed original: 0xA001
Koopman original: 0xC002
Normal reciprocal: 0x4003
Reversed reciprocal: 0xC002
Koopman reciprocal: 0xA001
Note that the Koopman representation of the reciprocal polynomial is the same as the reversed representation of the original polynomial. This means that if you mistakenly use the Koopman representation of a polynomial in a right-shift algorithm, you get a CRC that is just as strong as (but different from) the one you intended. This holds only for polynomials with a degree which is a multiple of 4.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=7)]
Error detection strength
The error-detection ability of a CRC depends on the degree of its key polynomial and on the specific key polynomial used. The "error polynomial" E(x) is the exclusive-or of the received message codeword and the correct message codeword. An error will go undetected by a CRC algorithm if and only if the error polynomial is divisible by the CRC polynomial.
Because a CRC is based on division, no polynomial can detect errors consisting of a string of zeros prepended to the data, or of missing leading zeros. However, see Variations (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Variations).
All single bit errors will be detected by any polynomial with at least two terms with non-zero coefficients. The error polynomial is x<sup>[i]k</sup>, and x<sup>k</sup> is divisible only by polynomials x<sup>i</sup> where http://upload.wikimedia.org/math/5/7/b/57bac0ff89002fde847fb1d62dd2eb41.png.
All two bit errors separated by a distance less than the order (http://en.wikipedia.org/w/index.php?title=Polynomial_order&action=edit) of the polynomial will be detected. The error polynomial in the two bit case is http://upload.wikimedia.org/math/f/f/4/ff460d10bacbd6c1bc93dad00fafffe0.png. As noted above, the x<sup>k</sup> term will not be divisible by the CRC polynomial, which leaves the x<sup>i − k</sup> + 1 term. By definition, the smallest value of i − k such that a polynomial divides x<sup>i − k</sup> + 1 is the polynomial's order. The polynomials with the largest order are called primitive polynomials (http://en.wikipedia.org/wiki/Primitive_polynomial), and for polynomials of degree n with binary coefficients, have order 2<sup>n</sup> − 1.
All errors in an odd number of bits will be detected by a polynomial which is a multiple of x + 1. This is equivalent to the polynomial having an even number of terms with non-zero coefficients.
All burst errors (http://en.wikipedia.org/wiki/Error_burst) of length n will be detected by any polynomial of degree n or greater which has a non-zero x<sup>0</sup> term.
(as an aside, there is never reason to use a polynomial with a zero x<sup>0</sup> term. Recall that a CRC is the remainder of the message polynomial times x^n divided by the CRC polynomial. A polynomial with a zero x<sup>0</sup> term always has x as a factor. So if K(x) is the original CRC polynomial and http://upload.wikimedia.org/math/f/9/4/f9496e9cedc62ba910becf96c1b7c4e9.png, then
http://upload.wikimedia.org/math/4/5/6/456a25d38b0cb80bbeb0baf414b32869.png
http://upload.wikimedia.org/math/2/2/3/223f55fe06adf10407dd31552add0c7d.png
http://upload.wikimedia.org/math/d/2/3/d2373ce4d1ed41fde89656e7fa3dcc99.png
That is, the CRC of any message with the K(x) polynomial is the same as that of the same message with the K'(x) polynomial with a zero appended. It is just a waste of a bit.)
The combination of these factors means that good CRC polynomials are often primitive polynomials (which have the best 2-bit error detection) or polynomials whose factors are a primitive polynomial of degree n − 1 and x + 1 (which detects all odd numbers of bit errors, and has half the two-bit error detection ability of a primitive polynomial of degree n)<sup id="_ref-koop02_2" class="reference">[2] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-koop02)</sup>.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=8)]
CRC polynomial specifications
The following table below omits "Initial value", "Reflected value" and "Final XOR value".
These hex values are important for some more complicated checksums (like most forms of CRC-32 and CRC-64). CRCs less than CRC-16 do not tend to use these values.
Very often custom versions of checksums are created by changing these values, as it does not alter the mechanics of the checksum algorithm.
CRC standardization issues
The definition of CRC-12 is disputed, as there are 3 forms of CRC-12 in common use.
Both forms of CRC-8 in use have notable weaknesses mathematically.
It is assumed that at least 10 forms of CRC-16 and CRC-32 exist, but no form of CRC-16 or CRC-32 is mathematically optimal.
CCITT CRCs differ from ITU CRCs (of the same size), as the same entitiy has standardized checksums more than once but in different eras.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=9)]
CRCs in common use (in ITU-IEEE syntax)
<table class="wikitable"> <tbody><tr> <th>Name</th> <th>Polynomial</th> <th>Representations: Normal or Reverse (Normal of Reciprocal)</th> </tr> <tr> <td>CRC-1</td> <td>x + 1
(use: hardware, also known as parity bit (http://en.wikipedia.org/wiki/Parity_bit))</td> <td>0x1 or 0x1 (0x1)</td> </tr> <tr> <td>CRC-5-CCITT</td> <td>x<sup>5</sup> + x<sup>3</sup> + x + 1 (ITU (http://en.wikipedia.org/wiki/ITU) G.704 standard)</td> <td>0x15 (0x??)</td> </tr> <tr> <td>CRC-5-USB</td> <td>x<sup>5</sup> + x<sup>2</sup> + 1 (use: USB (http://en.wikipedia.org/wiki/USB) token packets)</td> <td>0x05 or 0x14 (0x9)</td> </tr> <tr> <td>CRC-7</td> <td>x<sup>7</sup> + x<sup>3</sup> + 1 (use: telecom systems)</td> <td>0x09 or 0x48 (0x11)</td> </tr> <tr> <td>CRC-8-ATM</td> <td>x<sup>8</sup> + x<sup>2</sup> + x + 1 (use: ATM HEC)</td> <td>0x07 or 0xE0 (0xC1)</td> </tr> <tr> <td>CRC-8-CCITT (http://en.wikipedia.org/wiki/CCITT)</td> <td>x<sup>8</sup> + x<sup>7</sup> + x<sup>3</sup> + x<sup>2</sup> + 1 (use: 1-Wire (http://en.wikipedia.org/wiki/1-Wire) bus (http://en.wikipedia.org/wiki/Bus))</td> <td>
</td> </tr> <tr> <td>CRC-8-Dallas (http://en.wikipedia.org/wiki/Dallas_Semiconductor)/Maxim (http://en.wikipedia.org/wiki/Maxim_IC)</td> <td>x<sup>8</sup> + x<sup>5</sup> + x<sup>4</sup> + 1 (use: 1-Wire (http://en.wikipedia.org/wiki/1-Wire) bus (http://en.wikipedia.org/wiki/Bus))</td> <td>0x31 or 0x8C</td> </tr> <tr> <td>CRC-8</td> <td>x<sup>8</sup> + x<sup>7</sup> + x<sup>6</sup> + x<sup>4</sup> + x<sup>2</sup> + 1</td> <td>0xEA(0x??)</td> </tr> <tr> <td>CRC-10</td> <td>x<sup>10</sup> + x<sup>9</sup> + x<sup>5</sup> + x<sup>4</sup> + x + 1</td> <td>0x233 (0x????)</td> </tr> <tr> <td>CRC-12</td> <td>x<sup>12</sup> + x<sup>11</sup> + x<sup>3</sup> + x<sup>2</sup> + x + 1
(use: telecom systems)</td> <td>0x80F or 0xF01 (0xE03)</td> </tr> <tr> <td>CRC-16-Fletcher</td> <td>See Fletcher's checksum (http://en.wikipedia.org/wiki/Fletcher%27s_checksum)</td> <td>Used in Adler-32 (http://en.wikipedia.org/wiki/Adler-32) A & B CRCs</td> </tr> <tr> <td>CRC-16-CCITT</td> <td>x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1 (X25 (http://en.wikipedia.org/wiki/X25), V.41 (http://en.wikipedia.org/w/index.php?title=V.41&action=edit), Bluetooth (http://en.wikipedia.org/wiki/Bluetooth), PPP (http://en.wikipedia.org/wiki/PPP), IrDA (http://en.wikipedia.org/wiki/IrDA))</td> <td>0x1021 or 0x8408 (0x0811)</td> </tr> <tr> <td>CRC-16-IBM (http://en.wikipedia.org/wiki/IBM)</td> <td>x<sup>16</sup> +x<sup>15</sup> + x<sup>2</sup> + 1</td> <td>0x8005 or 0xA001 (0x4003)</td> </tr> <tr> <td>CRC-16-BBS (http://en.wikipedia.org/wiki/BBS)</td> <td>x<sup>16</sup> + x<sup>15</sup> + x<sup>10</sup> + x<sup>3</sup> (Use: XMODEM (http://en.wikipedia.org/wiki/XMODEM) protocol)</td> <td>0x8408 (0x????)</td> </tr> <tr> <td>CRC-32-Adler</td> <td>See Adler-32 (http://en.wikipedia.org/wiki/Adler-32)</td> <td>See Adler-32 (http://en.wikipedia.org/wiki/Adler-32)</td> </tr> <tr> <td>CRC-32-MPEG2</td> <td>See IEEE 802.3 (http://en.wikipedia.org/wiki/IEEE_802.3)</td> <td>See IEEE 802.3 (http://en.wikipedia.org/wiki/IEEE_802.3)</td> </tr> <tr> <td>CRC-32-IEEE 802.3 (http://en.wikipedia.org/wiki/IEEE_802.3)</td> <td>x<sup>32</sup> + x<sup>26</sup> + x<sup>23</sup> + x<sup>22</sup> + x<sup>16</sup> + x<sup>12</sup> + x<sup>11</sup> + x<sup>10</sup> + x<sup>8</sup> + x<sup>7</sup> + x<sup>5</sup> + x<sup>4</sup> + x<sup>2</sup> + x + 1</td> <td>0x04C11DB7 or 0xEDB88320 (0xDB710641)</td> </tr> <tr> <td>CRC-32C (Castagnoli)<sup id="_ref-cast93_1" class="reference">[1] (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_note-cast93)</sup></td> <td>x<sup>32</sup> + x<sup>28</sup> + x<sup>27</sup> + x<sup>26</sup> + x<sup>25</sup> + x<sup>23</sup> + x<sup>22</sup> + x<sup>20</sup> + x<sup>19</sup> + x<sup>18</sup> + x<sup>14</sup> + x<sup>13</sup> + x<sup>11</sup> + x<sup>10</sup> + x<sup>9</sup> + x<sup>8</sup> + x<sup>6</sup> + 1</td> <td>0x1EDC6F41 or 0x82F63B78 (0x05EC76F1)</td> </tr> <tr> <td>CRC-64-ISO</td> <td>x<sup>64</sup> + x<sup>4</sup> + x<sup>3</sup> + x + 1
(use: ISO 3309)</td> <td>0x000000000000001B or 0xD800000000000000 (0xB000000000000001)</td> </tr> <tr> <td>CRC-64-ECMA (http://en.wikipedia.org/wiki/Ecma_International)-182</td> <td>x<sup>64</sup> + x<sup>62</sup> + x<sup>57</sup> + x<sup>55</sup> + x<sup>54</sup> + x<sup>53</sup> + x<sup>52</sup> + x<sup>47</sup> + x<sup>46</sup> + x<sup>45</sup> + x<sup>40</sup> + x<sup>39</sup> + x<sup>38</sup> + x<sup>37</sup> + x<sup>35</sup> + x<sup>33</sup> + x<sup>32</sup> + x<sup>31</sup> + x<sup>29</sup> + x<sup>27</sup> + x<sup>24</sup> + x<sup>23</sup> + x<sup>22</sup> + x<sup>21</sup> + x<sup>19</sup> + x<sup>17</sup> + x<sup>13</sup> + x<sup>12</sup> + x<sup>10</sup> + x<sup>9</sup> + x<sup>7</sup> + x<sup>4</sup> + x + 1
(as described in ECMA-182 (http://www.ecma-international.org/publications/standards/Ecma-182.htm) p.63)</td> <td>0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)</td> </tr> <tr> <td>CRC-128</td> <td>IEEE-ITU Standard. Use superseded by hashes MD5 (http://en.wikipedia.org/wiki/MD5) & SHA-1 (http://en.wikipedia.org/wiki/SHA-1)</td> <td>
</td> </tr> <tr> <td>CRC-160</td> <td>IEEE-ITU Standard. Use superseded by hashes MD5 (http://en.wikipedia.org/wiki/MD5) & SHA-1 (http://en.wikipedia.org/wiki/SHA-1)</td> <td>
</td> </tr> </tbody></table> [edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=10)]
CRCs and data integrity
While useful for error detection (http://en.wikipedia.org/wiki/Error_detection), CRCs cannot be safely relied upon to verify data integrity (http://en.wikipedia.org/wiki/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, as demonstrated by CRC and how to Reverse it (http://www.woodmann.com/fravia/crctut1.htm). Message authentication codes (http://en.wikipedia.org/wiki/Message_authentication_code) can be used to verify data integrity.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=11)]
When CRCs collide
As with all hash functions, CRCs tend to have collision rates nearing 100% after a certain number of collision tests. Each additional bit added to a CRC (ie: CRC-20 vs CRC-21) cuts the number of collisions down by nearly 50%.
The theoretical collision rate for CRC64 is around one collision every 18×10<sup>18</sup> CRCs.
A properly designed CRC (using fewer bits) can be as effective as a poorly designed CRC using more bits due to the irreducable polynomial property of CRCs. In this case CRC-32 can perform nearly as well as CRC-40.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=12)]
Designing CRC polynomials
The selection of generator polynomial is the most important part of implementing the CRC algorithm. The polynomial must be chosen to maximize the error detecting capabilities while minimizing overall collision probabilites. The most important attribute of the polynomial is its length (the number of the highest nonzero coefficient), because of its direct influence of the length of the computed checksum.
The most commonly used polynomial lengths are
9 bits (CRC-8)
17 bits (CRC-16)
33 bits (CRC-32)
65 bits (CRC-64)
When creating a new CRC polynomial or improving an existing CRC the general mathematical advice is to use an irreducible polynomial that satisfies all polynomical irreducibility constraints from modular arithmetics.
Irreducibility in this case means that the polynomial cannot be divided by any polynomial except itself and 1 with zero remainder.
The properties of the generator polynomial can be derived from the algorithm definition
CRCs with more than one nonzero coefficients are able to detect all single bit errors in the input message.
CRCs can be used to detect all double bit errors in the input message shorter than 2k, where k is the length of the longest irreducible part of the polynomial.
If the CRC polynomial is divided by x + 1 then no polynomial with odd number of nonzero coefficients can be divided by it. Hence, it can be used to detect odd number of errors in the input message (like single bit parity function).
CRC polynomials detect (single) burst errors shorter than the number of the position of the highest polynomial coefficient.
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=13)]
See also
General category
Error correcting code (http://en.wikipedia.org/wiki/Error_correcting_code)
List of checksum algorithms (http://en.wikipedia.org/wiki/List_of_checksum_algorithms)
Parity (http://en.wikipedia.org/wiki/Parity_%28telecommunication%29)
Specific Technological References
Adler-32 (http://en.wikipedia.org/wiki/Adler-32)
Fletcher's checksum (http://en.wikipedia.org/wiki/Fletcher%27s_checksum)
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=14)]
References
^ <sup>a</sup> (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-cast93_0) <sup>b</sup> (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-cast93_1) <cite style="font-style: normal;">Castagnoli, G. and Braeuer, S. and Herrman, M. (June 1993). "Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits". IEEE Transactions on Communications 41 (6).</cite> - Castagnoli's et al. work on algorithmic selection of CRC polynomials
^ <sup>a</sup> (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-koop02_0) <sup>b</sup> (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-koop02_1) <sup>c</sup> (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-koop02_2) <cite style="font-style: normal;">Koopman, P. (June 2002). "32-Bit Cyclic Redundancy Codes for Internet Applications (http://citeseer.ist.psu.edu/koopman02bit.html)". The International Conference on Dependable Systems and Networks.</cite> - verification of Castagnoli's results by exhaustive search and some new good polynomials
^ (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#_ref-koop04_0) <cite style="font-style: normal;">Koopman, P. and Chakravarty, T. (2004). "Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks (http://citeseer.ist.psu.edu/koopman04cyclic.html)". The International Conference on Dependable Systems and Networks.</cite> - analysis of short CRC polynomials for embedded applications
[edit (http://en.wikipedia.org/w/index.php?title=Cyclic_redundancy_check&action=edit§ion=15)]
External links
Tutorial and C++ implementation (http://www.relisoft.com/science/CrcMath.html) of CRC
Cyclic redundancy check - a simple guide to what it means for your data, CD and DVD discs. http://www.softwarepatch.com/tips/cyclic-redundancy.html
The CRC Pitstop (http://www.ross.net/crc/)
Williams, R. (1993-09) 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)
Black, R. (1994-02) Fast CRC32 in Software (http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.html) — Algorithm 4 is used in Linux and info-zip's zip and unzip.
Barr, M. (1999-11 (http://www.netrino.com/Connecting/1999-11/), 1999-12 (http://www.netrino.com/Connecting/1999-12/), 2000-01 (http://www.netrino.com/Connecting/2000-01/)) checksums, CRCs, and their source code. Embedded Systems Programming
CRC32: Generating a checksum for a file (http://www.codeproject.com/cpp/crc32.asp), C++ implementation by Brian Friesen
Online Tool to compute common CRCs (8/16/32/64) from strings (http://serversniff.net/hash.php)
Online CRC calculator (http://www.zorc.breitbandkatze.de/crc.html)
Online CRC Tool: Generator of synthesizable CRC functions (http://www.easics.com/webtools/crctool)
Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithms (http://www.paulschou.com/tools/xlate/)
CRC16 to CRC64 collision research (http://apollo.backplane.com/matt/crc64.html)
Reversing CRC – Theory and Practice. (http://sar.informatik.hu-berlin.de/research/publications/index.htm#SAR-PR-2006-05)