The Cyclic Redundancy Check (CRC) is used to verify data integrity.

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.

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                     

Log in or register to write something here or to contact authors.