Cyclic redundancy check

From Free net encyclopedia

Current revision

A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is 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. The checksum is used to detect and correct 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. Correction can also be done if information lost is lower than information held by the checksum - See Error-correcting code. 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.

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 <math>n</math>, which represent the coefficients of a polynomial. Before the division, <math>n</math> zeros are appended to the message stream.

CRCs are based on division in the ring of polynomials over the finite field GF(2) (the integers modulo 2). In simpler terms, this is the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around. For example:

<math>(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1</math>

Two becomes zero because addition of coefficients is performed modulo 2. Multiplication is similar:

<math>(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x</math>

We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x³ + x² + x by x + 1. We would find that

<math>(x^3 + x^2 + x)/(x+1) = (x^2 + 1) - 1/(x+1)</math>

In other words,

<math>(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1</math>

The division yields a quotient of x² + 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 <math>x^{n}</math> where <math>n</math> is the degree of the fixed polynomial. The coefficients of the remainder polynomial are the CRC.

In the above equations, <math>x^2+x+1</math> represents the original message bits 111, <math>x+1</math> acts as the key, and the remainder <math>1</math> (equivalently, <math>x^0</math>) is the CRC. The degree of the key is 1, so we first multiplied the message by <math>x^1</math> to get <math>x^3 + x^2 + x</math>.

In general form:

<math>M(x) * x^{n} = Q(x) * K(x) + R (x) </math>

Here M(x) is the original message polynomial. K(x) is the key polynomial, with degree <math>n</math>. The bits of <math>M(x) * x^{n}</math> are the original message with <math>n</math> zeros added at the end. R(x) is the remainder polynomial, which is the CRC 'checksum'. In communication, the sender attaches the <math>n</math> 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 <math>M(x) * x^{n} - R(x)</math> is divisible by <math>K(x)</math>. If it is, then the receiver assumes the received message bits are correct. Note that <math>M(x) * x^{n} - R(x)</math> is exactly the string of bits the sender sent; this string is called the codeword.

CRCs are often referred to as "checksums," 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.

Implementation

There are simple, efficient algorithms for computing the CRC of a block of data, such as those shown below.

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 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
 }

Another common algorithm uses a lookup table indexed by multiple most-significant bits of the shiftRegister 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 shiftRegister based on the xor of one bit of the shiftRegister and one bit of the bitString, it is possible to xor (compute the parity of) all the bits of the shiftRegister selected by the polynomial and the bitString and add that single bit to the shiftRegister. With suitable adjustments to the polynomial, 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.

The specific CRC produced is defined by the polynomial used. To produce an n-bit CRC requires a degree-n polynomial, of the form <math>x^n + \ldots + 1 </math>. This is naturally expressed as an (n + 1)-bit string, but the leading <math>x^n</math> term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the CRC-16-IBM polynomial <math>x^{16} + x^{15} + x^2 + 1</math>, will be represented as the hexadecimal number 0x8005 or as 0xA001.

One of the most commonly encountered is known as CRC-32, used by (among others) Ethernet, FDDI, ZIP and other archive formats, and PNG 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 includes an appendix with a short and simple table-driven implementation in C of CRC-32.

Variations

There are several variations on CRCs

• The shiftRegister 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 polynomial with its bits reversed, and produces a bit-reversed result. 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, to preserve the CRC's burst error 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 <math>M(x) * x^{n} - R(x) = Q(x) * K(x)</math>, which is always divisible by <math>K(x)</math>.

• The shift register may be initialized with ones instead of zeroes. Equivalently, the first <math>n</math> 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 <math>\sum_{i=n}^{2n-1} x^{i}</math> by <math>K(x)</math>. This result is called the check polynomial <math>C(x)</math>, and its hexadecimal representation is sometimes called a magic number.

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 <math>C(x) = x^{31} + x^{30} + x^{26} + x^{25} + x^{24} + x^{18} + x^{15} + x^{14} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1</math>.

Reversed representations and reciprocal polynomials

Polynomial representations

All the well-known CRC polynomials of degree <math>n</math> have two common hexadecimal representations:

• A hexadecimal number with <math>n</math> bits, the least significant bit of which is always 1, the most significant bit representing the <math>x^{n-1}</math> coefficient and the least significant bit representing the <math>x^{0}</math> coefficient.

• A hexadecimal number with <math>n</math> bits, the most significant bit of which is always 1, the most significant bit representing the <math>x^{0}</math> coefficient and the least significant bit representing the <math>x^{n-1}</math> 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 <math>x^{n}</math> coefficient is omitted and understood to be 1.

There is a third representation in use, from a paper by P. Koopman and T. Chakravarty [1].

• A hexadecimal number with <math>n</math> bits, the most significant bit of which is always 1, the most significant bit representing the <math>x^n</math> coefficient and the least significant bit representing the <math>x^1</math> coefficient. The <math>x^{0}</math> 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.

Reciprocal polynomials

A reciprocal polynomial is created by assigning the <math>x^{n}</math> through <math>x^{0}</math> coefficients of one polynomial to the <math>x^{0}</math> through <math>x^{n}</math> coefficients of a new polynomial. Example: The reverse of <math>x^{16} + x^{15} + x^{2} + 1</math> is <math>x^{16} + x^{14} + x^{1} + 1</math>. 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 — i.e., 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 <math>x^{16} + x^{15} + x^{2} + 1</math> 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.

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" <math>E(x)</math> 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.
• All single bit errors will be detected by any polynomial with at least two terms with non-zero coefficients. The error polynomial is <math>x^k</math>, and <math>x^k</math> is divisible only by polynomials <math>x^i</math> where <math>i \le k</math>.
• All two bit errors separated by a distance less than the order of the polynomial will be detected. The error polynomial in the two bit case is <math>E(x) = x^i + x^k = x^k * (x^{i-k} + 1), \; i > k</math>. As noted above, the <math>x^k</math> term will not be divisible by the CRC polynomial, which leaves the <math>x^{i-k} + 1</math> term. By definition, the smallest value of <math>{i-k}</math> such that a polynomial divides <math>x^{i-k} + 1</math> is the polynomial's order. The polynomials with the largest order are called primitive polynomials, and for polynomials of degree <math>n</math> with binary coefficients, have order <math>2^n - 1</math>.
• All errors in an odd number of bits will be detected by a polynomial which is a multiple of <math>x+1</math>. This is equivalent to the polynomial having an even number of terms with non-zero coefficients.
• All burst errors of length <math>n</math> will be detected by any polynomial of degree <math>n</math> or greater which has a non-zero <math>x^0</math> term.

(as an aside, there is never reason to use a polynomial with a zero <math>x^0</math> 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 <math>x^0</math> term always has <math>x</math> as a factor. So if <math>K(x)</math> is the original CRC polynomial and <math>K(x) = x * K'(x)</math>, then

<math>M(x) * x^{n-1} = Q(x) * K'(x) + R(x)</math>

<math>M(x) * x^n = Q(x) * x * K'(x^n) + x * R(x)</math>

<math>M(x) * x^n = Q(x) * K(x^n) + x * R(x)</math>

That is, the CRC of any message with the <math>K(x)</math> polynomial is the same as that of the same message with the <math>K'(x)</math> polynomial with a zero appended. It's 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 <math>n-1</math> and <math>x+1</math> (which detects all odd numbers of bit errors, and has half the two-bit error detection ability of a primitive polynomial of degree <math>n</math>).

Polynomial CRC key specifications [ITU-IEEE syntax]

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

General category

• Error correcting code
• List of checksum algorithms
• Parity

Specific Technological References

• Adler-32
• Fletcher's checksum

External links

• Tutorial and C++ implementation 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
• A Painless Guide to CRC Error Detection Algorithms
• Understanding Cyclic Redundancy Check
• Fast CRC32 in Software — Algorithm 4 is used in Linux and info-zip's zip and unzip.
• checksums, CRCs, and their source code http://www.netrino.com/Connecting/1999-11/, http://www.netrino.com/Connecting/1999-12/, http://www.netrino.com/Connecting/2000-01/
• http://www.codeproject.com/cpp/crc32.asp
• Serversniff.net Online-Tool to compute common CRCs (8/16/32/64) from strings
• Online CRC calculator
• Online CRC Tool: Generator of synthesizable CRC functions
• Online Char (ASCII), HEX, Binary, Base64, etc... Encoder/Decoder with MD2, MD4, MD5, SHA1+2, CRC, etc. hashing algorithmscs:CRC

de:Zyklische Redundanzprüfung fr:Contrôle de redondance cyclique ko:순환 중복 검사 id:CRC it:Cyclic redundancy check nl:Cyclic Redundancy Check ja:巡回冗長検査 pl:CRC pt:CRC ru:CRC fi:CRC sv:Cyclic Redundancy Check