Cyclic redundancy check
Introduction
The Cyclic Redundancy Check (CRC) is a type of error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. CRCs are so called because the check (data verification) value is a redundancy (it expands the message without adding information) and the algorithm is based on cyclic codes. CRCs are popular because they are simple to implement in binary hardware, easy to analyze mathematically, and particularly good at detecting common errors caused by noise in transmission channels.
History
The concept of the CRC as an error-detecting code gets its name from the fact that the check (data verification) value is a redundancy (it expands the message without adding information) and the algorithm is based on cyclic codes. The CRC was invented by W. Wesley Peterson in 1961; the 32-bit polynomial used in the CRC function of Ethernet and many other standards is the work of several researchers and was published in 1975.
Mathematical background
A CRC is called an n-bit CRC when its check value is n bits long. The simplest error-detection system, the parity bit, is in fact a 1-bit CRC: it uses the generator polynomial x+1 (two terms), and has the name CRC-1.
CRC polynomials
The selection of the generator polynomial is the most important part of implementing the CRC algorithm. The polynomial must be chosen to maximize the error-detecting capabilities while minimizing overall collision probabilities. The most important attribute of the polynomial is its length (largest degree(exponent) of the terms with non-zero coefficients), because of its direct influence on the length of the computed check value.
CRC computation
The validity of a received message can easily be verified by performing the above described bit-wise exclusive OR operation again, this time with the check value added instead of zeroes. Depending on the nature and frequency of the errors expected on the transmission channel, the implementation of the CRC algorithm may require the check value to be sent in a different order than the order in which it was computed.
Applications
CRCs are used in numerous practical applications where digital data is sent or stored. CRCs are particularly easy to implement in hardware, and are therefore commonly used in digital networks and storage devices such as hard disk drives. Even if the data is protected by error correction code (ECC), it may still be necessary to use a CRC to protect against errors that the ECC cannot correct.
