Cyclic redundancy check
A cyclic redundancy check (CRC) is a type of hash function used to produce a small integer from a large block of data, such as network traffic or computer files, in order to detect errors in transmission or duplication. CRCs are calculated before and after transmission or duplication, and compared to confirm that they are the same. The most widely used CRC calculations are constructed in ways such that certain types of errors, such as those due to noise in transmission channels, are almost always detected.
The essential mathematical operation in the calculation of a CRC is modulo 2 division, and the remainder from the division determines the CRC. CRC's are often referred to as "checksums," but such designations are not accurate since, technically, a checksum is calculated through addition, not division. The main portion of the algorithm in pseudocode is as follows:
function crc(bit array bitString[1..len]) {
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: Use of a lookup table containing the CRC's of all 256 possible bytes allows for an eight-fold increase in the speed of the algorithm.
CRC types are often identified by "polynomial," which is the number used as the divisor (given in hexadecimal format). One of the most commonly encountered of the CRC types is that used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. It uses the polynomial 0x04C11DB7, and is known as CRC-32.
Polynomials and Types
| CRC-8 | x^8 + x^2 + x + 1 |
| CRC-CCITT | x^16 + x^12 + x^5 + 1 |
| IBM-CRC-16 | x^16 + x^15 + x^2 + 1 |
| 802.3-Frames | 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 |
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 it's possible to intentionally change data without modifying its CRC. Cryptographic hash functions can be used to verify data integrity.
See also
External Links and Resources
- A Painless Guide to CRC Error Detection Algorithms
- A Painless Guide to CRC Error Detection Algorithms
- Understanding Cyclic Redundancy Check
- Jacksum (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/