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 <email@example.com> May 2002.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 3 August 2009.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "cyclic redundancy check", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 3 August 2009. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/cyclicRedundancyCheck.html