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 <firstname.lastname@example.org> May 2002.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 3 August 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "cyclic redundancy check", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 3 August 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cyclicRedundancyCheck.html