NIST

cyclic redundancy check

(algorithm)

Definition: (1) A method to detect and correct errors by adding bits derived from a block or string of bits to the block. (2) An algorithm to compute bits characteristic of a block based on the algebra of polynomials over the integers, modulo 2. (3) The characteristic bits of a block.

Also known as CRC.

Note: Large blocks may be probabilistically compared by precalculating the CRC for each block, then comparing their CRCs. If the CRCs are different, the blocks are different. If the CRCs match, there is a small chance that the blocks are actually different. This probability may be made arbitrarily smaller with more CRC bits.

Many transmission errors may be detected, and some corrected, by recalculating the CRC and comparing it with the transmitted CRC.

Contributed by Arvind <uk_arvind@mail.utexas.edu> May 2002.

Author: PEB

More information

tutorial


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 3 August 2009.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "cyclic redundancy check", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 3 August 2009. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/cyclicRedundancyCheck.html