Other Definitions
cyclic redundancy check (dict)
|
Cyclic Redundancy CheckA cyclic redundancy check (CRC) is a type of hash function used to produce a checksum which is a small number of bits from a large block of data, such as a packet of network traffic or a block of a computer file, in order to detect errors in transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards to confirm that no changes occurred. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels. Introduction CRCs are based on division in a commutative ring, namely the ring of polynomials over the integers modulo 2. In simpler terms, this is the set of polynomials where each coefficient is only one bit, and arithmetic operations wrap around. For example: Two becomes zero because 2 is 10 in binary, and we discard all bits except the last one. Multiplication is similar: We can also divide polynomials mod 2 and find the quotient and remainder. For example, suppose we're dividing x3 + x2 + x by x + 1. We would find that In other words, the division yields a quotient of x2 + 1 with a remainder of -1, which, since it is odd, has a last bit of 1. Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and to find the CRC, we divide by another fixed polynomial. The coefficients of the remainder polynomial are the CRC, and there are simple, efficient algorithms for computing this remainder, such as the one shown below. CRCs are often referred to as "checksums," but such designations are not strictly accurate since, technically, a checksum is calculated through addition, not division. The main portion of the algorithm can be expressed in pseudocode as follows: function crc(bit array bitString1..len, int polynomial) { shiftRegister := initial value // commonly all 0 bits or all 1 bits for i from 1 to len { if most significant bit of shiftRegister xor bitStringi = 1 shiftregister := (shiftregister left shift 1) xor polynomial else shiftRegister := shiftregister left shift 1 } return shiftregister } Note: Use of a lookup table containing the CRCs of all 256 possible bytes allows for an increase in the speed of the algorithm. There are two variations which can be applied to the above implementation; applying one or both gives a total of four equivalent ways to compute a checksum: - The
shiftRegister can be shifted to the right 1 bit each step, using a polynomial with its bits reversed, to produce a result with its bits reversed, and - Instead of changing multiple bits in the
shiftRegister based on the xor of one bit of the shiftRegister and one bit of the bitString, it is possible to xor (compute the parity of) all the bits of the shiftRegister selected by the polynomial and the bitString and add that single bit to the shiftRegister. With suitable adjustments to the polynomial, this also produces the same remainder. This variation is often used when describing the close relative to a CRC, the linear feedback shift register. The specific CRC is defined by the polynomial used. To produce an n-bit CRC requires a degree-n polynomial, of the form xn + … + 1. This is naturally expressed as an n+1-bit string, but the leading (xn) term is normally implicit, leaving an n-bit string Thus, depending on the bit-order convention used, the standard CRC-16, x16+x15+x2+1, will be represented as the hexadecimal number 0x8005 or as 0xa001. One of the most commonly encountered is known as CRC-32, used by (among others) Ethernet, FDDI, PKZIP, WinZip, and PNG. Its polynomial can be written 0x04C11DB7 or 0xEDB88320. Polynomials and types | x8 + x2 + x + 1 | | RC-CCITT | x16 + x12 + x5 + 1 | | RC-16 (IBM) | x16 +x15 + x2 + 1 | | RC-32 (802.3) | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | | RC32c (Castagnoli) | x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18 + x14 + x13 + x11 + x10 + x9 + x8 + x6 + 1 | CRCs and data integrity While useful for error detection, CRCs cannot be safely relied upon to verify data integrity (that no changes whatsoever have occurred), since it's extremely easy to intentionally change data without modifying its CRC. Cryptographic hash functions can be used to verify data integrity. See also External links
|
 |