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

The bit rate counts data bits carried per second; the baud rate counts transmitted signal elements per second. A signal element need not carry one whole data bit. In Manchester encoding, each data bit occupies two half-bit signal elements, one high and one low. For example, choose low–high for zero and high–low for one. The compulsory transition in the middle provides a timing reference for clock recovery.

If one data bit lasts $T$ seconds, the bit rate is $1/T$, while each half-bit signal element lasts $T/2$. With this binary signal-element convention,Thus a 10 Mbit/s Manchester encoding signal uses 20 million half-bit signal elements per second. This is not a count of observed voltage transitions: some bit boundaries also contain a transition and others do not. Calling a whole two-element pattern a symbol gives a different symbol-counting convention; the physical fact is two half-bit elements per data bit.

In differential Manchester encoding, every data bit still has a compulsory transition at its midpoint for clock recovery. The data value is specified by whether a transition occurs at the beginning of the bit, rather than by the direction of the midpoint transition. One convention is beginning transition for zero and no beginning transition for one; interchanging the meanings consistently also works.

Reversing the signal polarity exchanges high and low everywhere, but preserves both the presence and the absence of transitions. A receiver using differential Manchester encoding therefore decodes the same data after a polarity reversal, provided it has acquired the timing and boundary reference. Ordinary Manchester encoding with a fixed low–high/high–low interpretation would exchange the two data values. The advantage is

A block code for line coding divides the data into five-bit groups and assigns each of the $2^5=32$ possible groups a distinct eight-bit codeword. The receiver reverses that assignment after finding the eight-bit boundaries. There are $2^8=256$ candidate codewords, so the designer has substantial freedom to select 32 suitable ones and reserve other patterns for control or synchronization.

The choice can limit long runs of equal bits to help clock recovery, balance high and low levels to reduce a persistent offset, and distinguish control patterns from data. These properties must hold across adjacent codeword boundaries too: two individually acceptable words can concatenate into an unacceptable run. The unused patterns can also help error detection and correction: an invalid received pattern exposes some errors, and the Hamming distance between valid codewords determines stronger guarantees. Redundancy alone does not imply that all errors are detected or correctable. Circuit complexity and propagation of a synchronization error also matter.

Before any further line coding or framing overhead, the useful fraction and expansion areThe three extra bits per five input bits are 60% overhead relative to the input, or 37.5% of the encoded output.

A physical link can deliver a continuous stream of bits; the data link layer needs to identify where each separately meaningful unit begins and ends. Framing supplies those boundaries, so the receiver can separate the data-link frame header, data and checking information, associate an error detection and correction result with a particular data-link frame, and regain alignment after damaged input.

Timing the individual bits is insufficient: knowing where each bit begins does not tell the receiver which bit starts a new data-link frame. Thus

Reserve a frame delimiter that cannot occur inside encoded data-link frame contents. For a concrete bit stuffing rule, take the flag 01111110. Between flags the sender inserts a zero after every run of five consecutive one bits, including runs in the checking information. The receiver removes that zero when decoding. The flags themselves are transmitted without bit stuffing. For example, the six payload one bits 111111 are sent as 1111101, so they cannot imitate the flag's run of six ones.^[ref]

The receiver recognizes the flag before treating input as payload. After five ones, a following zero is a stuffed bit; a following one cannot be ordinary stuffed payload and requires the delimiter/error handling rules. Consequently a delimiter remains recognizable even if the unencoded data contained its exact pattern. Bit stuffing also applies at the end of the payload, so a run cannot spill into a boundary ambiguously.

The frame delimiter should be long and distinctive enough to support reliable synchronization in the presence of errors, but frequent flags and the run constraint cost capacity. For the usual family of flags with a longer run of ones, a longer forbidden run makes stuffing less frequent while making the delimiter itself longer. Valid stuffed data never contains an intact flag; false flags can arise when transmission errors damage that guarantee. Their likelihood depends on the error model, rather than merely on the raw frequency of the unencoded pattern.

The data-link frame length balances fixed header/flag/check overhead against network latency, receiver storage and the cost of a damaged data-link frame. If independent bit errors have probability $p$, an $N$-bit transmission has no such error with probability $(1-p{)}^N$. Longer data-link frames amortize fixed overhead, but have more opportunities for corruption and, when data retransmission is used, waste more work per failed attempt. They also delay delivery until the whole data-link frame is available. A maximum length limits storage requirements and the damage from a lost boundary. The design balance is

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.

All the following polynomial coefficients and sums lie in the field with two elements, so $a+a=0$. For the constant polynomial,For the linear polynomial, subtracting the leading multiple means adding it:For the quadratic polynomial, first cancel $a{x}^2$ using $ax(x+1)$, leaving $(a+b)x+c$; then cancel $(a+b)x$ using $(a+b)(x+1)$. ThusThe requested polynomial quotients and polynomial remainders are thereforeFor a general polynomial $P(x)={\sum }_{i=0}^n{p}_i{x}^i$, write $P=(x+1)Q+R$ with constant $R$. Since $1+1=0$, polynomial evaluation at $x=1$ gives $P(1)=R$. This is the polynomial remainder theorem with $-1=1$ in the field with two elements. HenceThe polynomial remainder is precisely the parity bit obtained by taking the exclusive or of all the polynomial coefficients.

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.