Past exam of the computer science course of the University of Oxford / 2015 / Computer networks / 1 / f

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 obtainReplace the appended zeros by the $r$ bits of the polynomial remainder $R$, retaining leading zeros when necessary. The transmitted polynomial isThe 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\mathrm{mod}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.