Mathematics of cyclic redundancy checks

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 divisible by (i.e. is a multiple of) an agreed-on generator polynomial. As an example, the message ${\displaystyle 101100}$ is thought of as ${\displaystyle x^{5}+x^{3}+x^{2}}$ (which is divisible by ${\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 ${\displaystyle M(x)}$ by appending an ${\displaystyle n}$-bit remainder polynomial ${\displaystyle R(x)}$ to produce ${\displaystyle W(x)=M(x)\cdot x^{n}+R(x)}$, where ${\displaystyle n}$ is the degree of the generator polynomial.

Although the separation of ${\displaystyle W(x)}$ into the message part ${\displaystyle M(x)}$ and the checksum part ${\displaystyle R(x)}$ is convenient for use of CRCs, the error-detection properties do not make a distinction; errors are detected equally anywhere within ${\displaystyle W(x)}$.