cyclic redundancy check

[′sīk·lik ri′dən·dən·sē ‚chek] (computer science) A block check character in which each bit is calculated by adding the first bit of a specified byte to the second bit of the next byte, and so forth, spiraling through the block.

cyclic redundancy check

(algorithm)(CRC or "cyclic redundancy code") A number derivedfrom, and stored or transmitted with, a block of data in orderto detect corruption. By recalculating the CRC and comparingit to the value originally transmitted, the receiver candetect some types of transmission errors.

A CRC is more complicated than a checksum. It is calculatedusing division either using shifts and exclusive ORs ortable lookup (modulo 256 or 65536).

The CRC is "redundant" in that it adds no information. Asingle corrupted bit in the data will result in a one bitchange in the calculated CRC but multiple corrupted bits maycancel each other out.

CRCs treat blocks of input bits as coefficient-sets forpolynomials. E.g., binary 10100000 implies the polynomial:1*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1 + 0*x^0.This is the "message polynomial". A second polynomial, withconstant coefficients, is called the "generator polynomial".This is divided into the message polynomial, giving a quotientand remainder. The coefficients of the remainder form thebits of the final CRC. So, an order-33 generator polynomialis necessary to generate a 32-bit CRC. The exact bit-set usedfor the generator polynomial will naturally affect the CRCthat is computed.

Most CRC implementations seem to operate 8 bits at a time bybuilding a table of 256 entries, representing all 256 possible8-bit byte combinations, and determining the effect that eachbyte will have. CRCs are then computed using an input byte toselect a 16- or 32-bit value from the table. This value isthen used to update the CRC.

Ethernet packets have a 32-bit CRC. Many disk formatsinclude a CRC at some level.

cyclic redundancy check

cyclic redundancy check