Cyclic redundancy check (source code)

= Cyclic redundancy check
{title2=CRC}
{wiki}

= CRC
{c}
{synonym}

A <cyclic redundancy check> represents a bit string as a <polynomial> over the <field with two elements> and uses a <polynomial remainder> as checking information. Agree on a <monic polynomial> $G(x)$ of <polynomial degree> $r$ with constant term $1$. Under the basic systematic convention, a message <polynomial> $M(x)$ produces
$$
R(x)=x^rM(x)\bmod G(x),\qquad C(x)=x^rM(x)+R(x).
$$
Here $\deg R<r$, and addition equals subtraction over the <field with two elements>, so $G$ divides the transmitted <polynomial> $C$. The receiver tests the <polynomial remainder> on division by the same <CRC generator polynomial>.

For example, $G=x^3+x+1$ and $M=x^2+1$ give $R=x^2$ and $C=x^5+x^3+x^2=x^2G$. If an error <polynomial> $E$ changes $C$ to $C+E$, the error is undetected exactly when $G$ divides $E$. Thus the <CRC generator polynomial> controls which bit-error patterns the <cyclic redundancy check> detects. This basic convention fixes the mathematics; implementations can additionally specify initial register contents and bit-order conventions.