CRC

9/28/96

Cyclic Redundancy Check (CRC) is an error detection technique that has largely replaced checksumming in most data processing applications. CRCs generate a value by a somewhat baffling sequence of shift and exclusive OR operations that are the mathematical equivalent of dividing the numeric value of the entire block of data added to a CRC constant by a polynomial expansion on the data. The CRC constant is selected such that the result will be zero.

A few specific polynomials when used this way have desirable error detection/detection properties:

1. They will detect all errors involving an odd number of bits.

2. They will detect all single or double bit errors.

3. They will detect error bursts up to the length of the CRC.

4. They will detect most error bursts greater than the CRC in length.

These properties are much more extensive than those of checksum or parity which are guaranteed only to catch single bit errors and may fail in stuck bit situations.

Four CRC polynomials are in common use:

CRC12 for 6 bit data (X^12 +X^11+X^3+X^2+X+1]
CRC16 for 8 bit data [X^16+X^15+X^2+1]
CRC-CITT also for 8 bit data [X^16+X^12+X^5+1]
CRC32 for networks [X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1]

Parity is effectively CRC1 and is not a particularly effective polynomial.