cyclic redundancy check
<algorithm> (CRC or "cyclic redundancy code") A number derived from, and
stored or transmitted with, a block of data in order to detect corruption. By
recalculating the CRC and comparing it to the value originally transmitted, the
receiver can detect some types of transmission errors.
A CRC is more complicated than a checksum. It is calculated using division
either using shifts and exclusive ORs or table lookup (modulo 256 or 65536).
The CRC is "redundant" in that it adds no information. A single corrupted bit in
the data will result in a one bit change in the calculated CRC but multiple
corrupted bits may cancel each other out.
CRCs treat blocks of input bits as coefficientsets for polynomials. 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,
with constant coefficients, is called the "generator polynomial". This is
divided into the message polynomial, giving a quotient and remainder. The
coefficients of the remainder form the bits of the final CRC. So, an order33
generator polynomial is necessary to generate a 32bit CRC. The exact bitset
used for the generator polynomial will naturally affect the CRC that is
computed.
Most CRC implementations seem to operate 8 bits at a time by building a table of
256 entries, representing all 256 possible 8bit byte combinations, and
determining the effect that each byte will have. CRCs are then computed using an
input byte to select a 16 or 32bit value from the table. This value is then
used to update the CRC.
Ethernet packets have a 32bit CRC. Many disk formats include a CRC at some
level.
(19970802)
Nearby terms:
cycle drought « cycle of reincarnation « cycle
server «
cyclic redundancy check » cyclic redundancy code
» Cyclo » cyclomatic complexity
