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

1 Introduction 2 Polynomials and types 3 CRCs and data integrity 4 See also 5 External links

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³ + x² + 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² + 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 most-significant bits of the shiftRegister to process multiple bits at once. A 256-entry 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:

1. 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.
2. 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 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 n-bit CRC requires a degree-n polynomial, of the form xⁿ + … + 1. This is naturally expressed as an n+1-bit string, but the leading (xⁿ) term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the standard CRC-16, x¹⁶+x¹⁵+x²+1, 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, PKZIP, WinZip, and PNG. Its polynomial can be written 0x04C11DB7 or 0xEDB88320.

Polynomials and types

CRC-8	x8 + x2 + x + 1
CRC-CCITT	x16 + x12 + x5 + 1
CRC-16 (IBM)	x16 +x15 + x2 + 1
CRC-32 (802.3)	x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
CRC32c (Castagnoli)	x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18 + x14 + x13 + x11 + x10 + x9 + x8 + x6 + 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

• Error correcting code
• List of checksum algorithms
• Parity

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/1999-11/, http://www.netrino.com/Connecting/1999-12/, http://www.netrino.com/Connecting/2000-01/de:Zyklische Redundanzprüfung

fr:Cyclic redundancy check nl:Cyclic Redundancy Check ja:巡回冗長検査 pl:CRC ru:CRC