Cyclic Redundancy Check Article Index for
Cyclic 		Website Links For
Cyclic 		 

Information About

Cyclic Redundancy Check
  CATEGORIES ABOUT CYCLIC REDUNDANCY CHECK
   
checksum algorithms
   
finite fields
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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 represent 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 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:

:(x^3 + x) + (x + 1) = x^3 + 2x + 1 \equiv x^3 + 1

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

:(x^2 + x)(x + 1) = x^3 + 2x^2 + x \equiv x^3 + x

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

:(x^3 + x^2 + x)/(x+1) = (x^2 + 1) - 1/(x+1)

In other words,

:(x^3 + x^2 + x) = (x^2 + 1)(x + 1) - 1

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, after first multiplying by x^{n} where n is the Degree of the fixed polynomial. The coefficients of the remainder polynomial are the CRC.

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

In general form:

  • x^{n} = Q(x) --- K(x) + R (x)


  • x^{n} 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 M(x) --- x^{n} - R(x) is divisible by K(x). If it is, then the receiver assumes the received message bits are correct. Note that M(x) --- x^{n} - R(x) is exactly the string of bits the sender sent; this string is called the ''codeword''.


CRCs are often referred to as " Checksum s," 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 Code s, which allow the correct message to be reconstructed in the face of transmission errors. These codes are based on closely related mathematical principles.


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 {Link without Title} , ''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 {Link without Title} = 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 .