Cyclic redundancy check
A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents.
On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for error correction (see bitfilters). CRCs are so called because the check (data verification) value is a redundancy (it expands the message without adding information) and the algorithm is based on cyclic codes.
CRCs are popular because they are simple to implement in binary hardware, easy to analyze mathematically, and particularly good at detecting common errors caused by noise in transmission channels. Because the check value has a fixed length, the function that generates it is occasionally used as a hash function. \operatorname{CRC}(x \oplus y) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y) \oplus c where c depends on the length of x and y . This can be also stated as follows, where x , y and z have the same length \operatorname{CRC}(x \oplus y \oplus z) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y) \oplus \operatorname{CRC}(z); as a result, even if the CRC is encrypted with a stream cipher that uses XOR as its combining operation (or mode of block cipher which effectively turns it into a stream cipher, such as OFB or CFB), both the message and the associated CRC can be manipulated without knowledge of the encryption key; this was one of the well-known design flaws of the Wired Equivalent Privacy (WEP) protocol.
1011 The algorithm acts on the bits directly above the divisor in each step. The result for that iteration is the bitwise XOR of the polynomial divisor with the bits above it. The bits not above the divisor are simply copied directly below for that step.
The divisor is then shifted right to align with the highest remaining 1 bit in the input, and the process is repeated until the divisor reaches the right-hand end of the input row. Here is the entire calculation: 11010011101100 000 Since the leftmost divisor bit zeroed every input bit it touched, when this process ends the only bits in the input row that can be nonzero are the n bits at the right-hand end of the row.
These n bits are the remainder of the division step, and will also be the value of the CRC function (unless the chosen CRC specification calls for some postprocessing). The validity of a received message can easily be verified by performing the above calculation again, this time with the check value added instead of zeroes.
The remainder should equal zero if there are no detectable errors. 11010011101100 100 The following Python code outlines a function which will return the initial CRC remainder for a chosen input and polynomial, with either 1 or 0 as the initial padding.
This code works with string inputs rather than raw numbers: def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler): """Calculate the CRC remainder of a string of bits using a chosen polynomial. initial_filler should be '1' or '0'. """ polynomial_bitstring = polynomial_bitstring.lstrip("0") len_input = len(input_bitstring) initial_padding = (len(polynomial_bitstring) - 1) * initial_filler input_padded_array = list(input_bitstring + initial_padding) while "1" in input_padded_array[:len_input]: cur_shift = input_padded_array.index("1") for i in range(len(polynomial_bitstring)): input_padded_array[cur_shift + i] \ = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i])) return "".join(input_padded_array)[len_input:] def crc_check(input_bitstring, polynomial_bitstring, check_value): """Calculate the CRC check of a string of bits using a chosen polynomial.""" polynomial_bitstring = polynomial_bitstring.lstrip("0") len_input = len(input_bitstring) initial_padding = check_value input_padded_array = list(input_bitstring + initial_padding) while "1" in input_padded_array[:len_input]: cur_shift = input_padded_array.index("1") for i in range(len(polynomial_bitstring)): input_padded_array[cur_shift + i] \ = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i])) return ("1" not in "".join(input_padded_array)[len_input:]) >>> crc_remainder('11010011101100', '1011', '0') '100' >>> crc_check('11010011101100', '1011', '100') True The advantage of choosing a primitive polynomial as the generator for a CRC code is that the resulting code has maximal total block length in the sense that all 1-bit errors within that block length have different remainders (also called syndromes) and therefore, since the remainder is a linear function of the block, the code can detect all 2-bit errors within that block length.
If r is the degree of the primitive generator polynomial, then the maximal total block length is 2 ^ {r} - 1 , and the associated code is able to detect any single-bit or double-bit errors. However, if we use the generator polynomial g(x) = p(x)(1 + x) , where p is a primitive polynomial of degree r - 1 , then the maximal total block length is 2^{r - 1} - 1 , and the code is able to detect single, double, triple and any odd number of errors.
A polynomial g(x) that admits other factorizations may be chosen then so as to balance the maximal total blocklength with a desired error detection power. The BCH codes are a powerful class of such polynomials. They subsume the two examples above.
Regardless of the reducibility properties of a generator polynomial of degree r, if it includes the "+1" term, the code will be able to detect error patterns that are confined to a window of r contiguous bits. These patterns are called "error bursts".
0x3 = 0b0011, representing x^4 + (0x^3 + 0x^2 + 1x^1 + 1x^0) (MSB-first code) 0xC = 0b1100, representing (1x^0 + 1x^1 + 0x^2 + 0x^3) + x^4 (LSB-first code) 0x9 = 0b1001, representing (1x^4 + 0x^3 + 0x^2 + 1x^1) + x^0 (Koopman notation) In the table below they are shown as:
CRC catalogues
Catalogue of parametrised CRC algorithms CRC Polynomial Zoo
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376750802 under CC BY-SA 4.0; modifications have been made.