Typically, two CRC bytes are added to each block of data. These two added bytes are calculated using the user data block as the key. The mathematical model is to use polynomials with binomial coefficients. After the user data block is transmitted and read, the CRC bytes are also read and compared to freshly generated CRC bytes. The new CRC values are divided into the read block including the original CRC bytes. The division should result in a remainder of zero. This is more reliable than simple checksums, which rely on the assumption that only a single bit will be corrupted.

Here's how to calculate the CRC code for a given bitstring (ex. 1100):

First of all, for hand computation at least, bitstrings are represented by polynomials with binary coefficients. The data we want to create a CRC code for is referred to as the information polynomial:

i(x) = ik-1xk-1 + ik-2xk-2 + ... + i1x + i0 for k bits

For the example bitstring 1100,

i(x) = (1)x3 + (1)x2 + (0)x1 + (0)x0

     = x3 + x2
     

Next, you need an appropriate generator polynomial g(x), which can be obtained from a standardized list of polynomial codes (i.e. CRC-8, CRC-16, CRC-32, etc.). Generator polynomials are generally chosen for their error detecting capability, but it is considered to be a black art by mere mortals and trying to make your own is probably a very bad idea (unless you're a mathematician).

So for this example, we'll arbitrarily choose

g(x) = x3 + x + 1

Now that we have both our generator and information polynomials, we can begin our actual CRC calculation.

Step 1: Multiply i(x) by the highest-order term in g(x) to shift the bitstring the right number of bits to the left in order to make room for the CRC code which will be appended to it.

x3i(x) = x3(x3 + x2) = x6 + x5

So now our bitstring looks like: 1100000 (since, as implied by g(x), we will be generating 3 CRC bits after i(x)).

Step 2: Divide the product obtained in Step 1 by g(x). The remainder is our CRC string.

Recall modulo-2 arithmetic: 0+0=0, 0+1=1, 1+0=1, 1+1=0 (no carries)

             x3 + x2 + x
            _______________
 x3 + x + 1 ) x6 + x5 
             x6 +    + x4 + x3
             -----------------
                  x5 + x4 + x3
                  x5      + x3 + x2
                  -----------------
                       x4      + x2
                       x4      + x2 + x
                       ----------------
                                      x
                                                                

Remainder r(x) = x = 010 (we don't care about the quotient)

Therefore, the final transmitted codeword is:

b(x) = x3i(x) + r(x) = x6 + x5 + x = 1100010

where bits b₆ ... b₃ (1100) represent our data and bits b₂ ... b₀ (010) represent the corresponding CRC code.

And there you have it! Is that neat or what?

The cyclic redundancy check (CRC for short) computes a check word for a bit string by using multiplication and addition in a finite field of p = 2. CRC has more resistance to multiple errors than a simple sum of the bytes in the string; an n-bit CRC can detect all errors of up to n - 1 bits but cannot correct any error. However, because it is a linear function of the input string, it reveals more information about the source string than MD5 or SHA-1 does, and it should not be used for storing passwords. The state of the least significant bit after each step of a CRC given the sequence [1, 0, 0, 0, 0, 0, ...] is equivalent to the output of a linear feedback shift register.

The most commonly used polynomial for 32-bit CRC, used in such applications as PKZIP, Ethernet, and FDDI, is 0x04C11DB7.

As 0mnidirecti0nal Hal0 mentioned, computing a CRC is similar to long division:

 shiftreg = initial value (commonly 0)
 while bits remain in string:
   if MSB of shiftreg is set:
     shiftreg = (shiftreg shl 1) xor polynomial
   else:
     shiftreg = shiftreg shl 1
   xor next bit from the string into LSB of shiftreg
 output shiftreg

Use of a lookup table containing the CRC of all bytes allows an eight-fold speedup in the algorithm.

References

• http://www.4d.com/ACIDOC/CMU/CMU79909.HTM

we are the same, you and i        
,to the Cult of Mandelbrot who under stand       
Patterns at different magnifications(we all are                   
      full of these tiny planetary systems 
      & slowly we are Coming Apart          
      
WE ARE And it is for the greater good.           
PREPARED truly, these end times are marked 
TO DESTROY by the crying statues,the feet of trees       
YOU retracting from the poisoned soil      
and the loss of all of the meaning of all of our lives.    
      
      But I haven't been clear; time is meaninglesss to the prophet,
      who sees without sight, Who can know limitless,&future?        
      
      But I haven't been clear; we are all prophets,
      some who see clearer than others,those                   
      
      But I haven't clear;ed  meaning,time
      thi&esssse; time will be,[|this time will be different