The cyclic redundancy check (CRC) is a check of the remainder after division in the ring of polynomials over GF(2) (the finite field of integers modulo 2). That is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around. Any string of bits can be interpreted as the coefficients of a polynomial of this sort, and a message has a valid CRC if it is divisible by (i.e. is a multiple of) an agreed-on generator polynomial. As an example, the message 101100 {\displaystyle 101100} is thought of as x 5 + x 3 + x 2 {\displaystyle x^{5}+x^{3}+x^{2}} (which is divisible by x 2 {\displaystyle x^{2}} , see Polynomial arithmetic modulo 2 below for more details). CRCs are convenient and popular because they have good error-detection properties and such a multiple may be easily constructed from any message polynomial M ( x ) {\displaystyle M(x)} by appending an n {\displaystyle n} -bit remainder polynomial R ( x ) {\displaystyle R(x)} to produce W ( x ) = M ( x ) ⋅ x n + R ( x ) {\displaystyle W(x)=M(x)\cdot x^{n}+R(x)} , where n {\displaystyle n} is the degree of the generator polynomial. Although the separation of W ( x ) {\displaystyle W(x)} into the message part M ( x ) {\displaystyle M(x)} and the checksum part R ( x ) {\displaystyle R(x)} is convenient for use of CRCs, the error-detection properties do not make a distinction; errors are detected equally anywhere within W ( x ) {\displaystyle W(x)} .
Formulation In general, computation of CRC corresponds to Euclidean division of polynomials over GF(2):
M ( x ) ⋅ x n = Q ( x ) ⋅ G ( x ) + R ( x ) . {\displaystyle M(x)\cdot x^{n}=Q(x)\cdot G(x)+R(x).}
Here M ( x ) {\displaystyle M(x)} is the original message polynomial and G ( x ) {\displaystyle G(x)} is the degree- n {\displaystyle n} generator polynomial. The bits of M ( x ) ⋅ x n {\displaystyle M(x)\cdot x^{n}} are the original message with n {\displaystyle n} zeroes added at the end. The CRC 'checksum' is formed by the coefficients of the remainder polynomial R ( x ) {\displaystyle R(x)} whose degree is strictly less than n {\displaystyle n} by the properties of Euclidean division. The quotient polynomial Q ( x ) {\displaystyle Q(x)} is of no interest. Using modulo operation, it can be stated that
R ( x ) = M ( x ) ⋅ x n mod G ( x ) . {\displaystyle R(x)=M(x)\cdot x^{n}\,{\bmod {\,}}G(x).}
In communication, the sender attaches the n {\displaystyle n} bits of R after the original message bits of M, which is equivalent to sending out W ( x ) = M ( x ) ⋅ x n + R ( x ) {\displaystyle W(x)=M(x)\cdot x^{n}+R(x)} (the codeword). This equivalence can be seen because we know that R ( x ) {\displaystyle R(x)} has degree strictly less than n {\displaystyle n} , and the binary message M ( x ) ⋅ x n {\displaystyle M(x)\cdot x^{n}} corresponds to is the original message bit shifted left n {\displaystyle n} times. Thus appending the n {\displaystyle n} bits of R (possibly with leading zeros) to the message by just adding the polynomials. Writing W ( x ) {\displaystyle W(x)} this way demonstrates that W ( x ) mod G ( x ) = 0 {\displaystyle W(x){\bmod {\,}}G(x)=0} as
… excerpt ends here. Continue reading the full article.
