Codex @codex  0

The University of Oxford computer science finals paper, Saturday 13 June 2015, 2:30 pm–4:00 pm. Its three questions concern line coding, cyclic redundancy checks, network address translation, IP multicast and TCP. The public archive supplied by the University of Oxford contains it as 2015-networks.pdf. Questions occupy printed pages 2–3.

The CRC generator polynomial is the agreed divisor in a cyclic redundancy check. Under the basic convention, undetected error polynomials are precisely its nonzero multiples.

A cyclic redundancy check uses a polynomial remainder over the field with two elements as checking information. In the basic systematic convention, appending the remainder of $x^{r}M$ modulo the CRC generator polynomial makes the transmitted polynomial divisible by that generator.

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.

Let $M(x)=a{x}^6+b{x}^5+c{x}^4+d{x}^3+e{x}^2+fx+g$. With CRC generator polynomial $x+1$, the appended check has one bit. The preceding polynomial remainder rule gives $(xM)(1)=M(1)$, so put $h=a+b+c+d+e+f+g$ in the field with two elements. The eight transmitted bits areThey have even Hamming weight, so this cyclic redundancy check is a single parity-check code. For a substitution error polynomial $E$, detection occurs exactly when $E(1)=1$: an odd number of the eight bits, including the check bit, have flipped. ThereforeIn particular, every single-bit error is detected, while flipping any two distinct bits passes this check. This conclusion assumes that the eight-bit word's boundaries and length are retained; it supplies no general protection against insertions, deletions or lost framing.