= Solution
Represent the data <bits>, most significant first, by a <polynomial> $M(x)$ whose <polynomial coefficients> lie in the <field with two elements> $\mathbb F_2$. Here <addition> and <subtraction> are both <exclusive or>, with no carries. Choose a fixed <CRC generator polynomial> $G(x)$ of <polynomial degree> $r$, with leading and constant <polynomial coefficients> one. Both <endpoints> know $G$ and the <bit> ordering.
Multiply $M$ by $x^r$, which appends $r$ zero <bits>. Use <polynomial division> to obtain
$$
x^rM(x)=Q(x)G(x)+R(x),\qquad R=0\ \text{or}\ \deg R<r.
$$
Replace the appended zeros by the $r$ <bits> of the <polynomial remainder> $R$, retaining leading zeros when necessary. The transmitted <polynomial> is
$$
\boxed{T(x)=x^rM(x)+R(x),\qquad T(x)\bmod G(x)=0.}
$$
The last equality holds because adding $R$ cancels the existing <polynomial remainder> in the <field with two elements>. It is the simple systematic <cyclic redundancy check> convention used here; practical variants can add agreed initialization and final transformations.
The receiver divides the entire received <polynomial> by $G$. A nonzero <polynomial remainder> detects corruption. If the received word is $T+E$, where the ones in the error <polynomial> $E$ mark flipped <bits>, its <polynomial remainder> is $E\bmod G$. Thus the undetected nonzero errors are exactly the multiples of $G$; a zero result does not prove that transmission was error-free. Operationally, <polynomial long division> repeatedly cancels a leading one using a shifted copy of $G$, implemented with <exclusive or> operations.
Back to article page
