Exercises — Data link layer — framing, error detection (CRC computation), MAC

Read 11001 from the highest power down. Five bits → powers $x^4,x^3,x^2,x^1,x^0$: $1\cdot x^4+1\cdot x^3+0\cdot x^2+0\cdot x^1+1\cdot x^0=x^4+x^3+1.$ Highest power present is $x^4$, so $==r=4==$. Check bits $=r=4$. You append 4 zeros to the message (multiply $M(x)$ by $x^4$).

The stuffing rule: after every 5 consecutive 1s in the data, insert a 0. Scan the payload one bit at a time, keeping a count of consecutive 1s:

• 0 → count of ones resets to 0. Output so far: 0
• 1 1 1 1 1 → five consecutive ones. Output them, then the rule fires: insert a stuffed 0 and reset the count. Output so far: 011111 + 0 = 0111110
• remaining data 1 0 → the sixth original 1 (now the count starts fresh at 1), then 0. Output: 10

Final sent sequence $=011111010=011111010$ (9 bits — exactly one stuffed 0 added). This guarantees the flag 01111110 (six ones in a row) can never appear inside the payload, because a 0 always breaks up any run before it reaches six.

• MAC address = flat (no structure implying location), 48 bits, burned into the NIC. Used for local delivery on the one shared link.
• IP address = hierarchical (network part + host part), used for end-to-end routing across networks — see Network Layer (IP). The link layer delivers within a link using MAC; the network layer forwards between links using IP.

$G=101$ has 3 bits → $r=2$. Append 2 zeros: dividend $=$ 1011000. The method: scan the dividend left to right. Whenever the current leading bit is 1, XOR the 3-bit pattern 101 starting at that position (this is the "subtract $G$" step over GF(2)). Whenever it is 0, do nothing and move one position right. The final $r=2$ bits left over are the remainder.

Here is the full aligned walk (the moving 3-bit window is underlined by the 101 below it):

 1011000     leading bit 1 -> XOR 101
 101
 -----
 0001000     next leading 1 is at position 4
    101
    -----
 0000010     next leading 1 is at position 6
      10 1   -> but only 2 bits remain; window is 101
      101
      -----
 0000000  R = last 2 bits = 10

Reading the trailing $r=2$ bits gives remainder $R=10$. Let's sanity-check by re-tracing the three XOR events on the raw 7 bits 1011000:

1. Position 0 leading 1: 101⊕101 = 000. Stream → 0001000.
2. Position 3 leading 1: 100⊕101 = 001. Stream → 0000010.
3. Position 5 leading 1: 10⊕10 (last two bits, top of 101 aligned) leaves the final two bits 10.

So $R=10$ (this is confirmed by the machine check in =VERIFY=: $1011000\mathrm{mod}101=10$). Transmit $T=10110\underline{10}=1011010$.

The figure above lays the same division out as stacked XOR rows — follow the orange 101 rows (the parts we XOR) down to the plum remainder 10.

Divide 1011010 by 101. Since we constructed $T$ to be an exact multiple, the remainder is 00. Remainder $=0\Rightarrow$ accept (no detectable error).

The rule from the parent note: $L_{\min }\ge 2B\tau .$ Why: the sender must still be transmitting when the worst-case collision signal returns after a full round trip $2\tau$. $L_{\min }=2\times 10^7\times 25.6\times 10^{-6}=2\times 256=512\text{bits}=64\text{bytes}.$ This is exactly why classic Ethernet's minimum frame is 64 bytes.

An error is undetected iff $G(x)\mid E(x)$. Here $E(x)=x^i$. For $G(x)$ to divide $x^i$, since $x^i$ has only the factor $x$ repeated, $G$ would have to be a power of $x$ — i.e. $G$ would have to be 100...0 (only its top term). But $G=1011$ has more than one term ($x^3,x^1,x^0$). A polynomial with $\ge 2$ terms cannot divide $x^i$. Therefore no single-bit error is undetected — all single-bit errors are caught. ✅

Key tool — why substitute $x=1$? Over GF(2), plugging $x=1$ into a polynomial adds up all its coefficients mod 2. That sum $=$ the number of terms mod 2 $=$ the parity (odd/even) of how many bits are 1.

• Let $E(x)$ be an odd-weight error: it has an odd number of 1 coefficients, so $E(1)=1$.
• Suppose $(x+1)\mid G(x)$. If $G\mid E$, then $(x+1)\mid E$ too, meaning $E(x)=(x+1)K(x)$.
• Evaluate at $x=1$: $E(1)=(1+1)K(1)=0\cdot K(1)=0$.
• But we said $E(1)=1$. Contradiction! So $G$ cannot divide an odd-weight $E$ ⇒ every odd number of bit errors is detected. ✅ (This is exactly the trick a simple parity bit uses; CRC generalises it — compare with Hamming Code which goes further and corrects.)

A burst of length $L$ can be written $E(x)=x^{i}B(x)$ where $B(x)$ describes the run, $\mathrm{deg}B=L-1$, and $B$ has a nonzero constant term (its lowest bit is flipped).

• $G$ does not divide $x^i$ (assuming $G$ has $\ge 2$ terms, so $x\nmid G$).
• So detection fails only if $G\mid B(x)$. That needs $\mathrm{deg}B\ge \mathrm{deg}G$, i.e. $L-1\ge 8$, i.e. $L\ge 9$. Therefore every burst of length $L\le r=8$ is guaranteed detected. Bursts of length $\ge 9$ may slip through, but only a tiny fraction of them.

Order matters: CRC is computed over the frame contents, then the whole thing (contents + FCS) is bit-stuffed for framing, and flags are added last. Reverse order would corrupt the CRC when a stuffed 0 is inserted.

Step 1 — CRC. $M=0111110$, $r=2$, append 00 → dividend 011111000. Divide by 101 using the same XOR method as L2.1. The trailing $r=2$ bits give remainder $R=10$ (confirmed by the machine check in =VERIFY=: $011111000\mathrm{mod}101=10$). Frame contents $=0111110\underline{10}=011111010$.

Step 2 — bit-stuff 011111010: scan for five consecutive 1s. 0 11111 010 — after the five 1s insert a 0: $011111\underline{0}010=011111\underline{0}010.$ On-wire contents (between flags) $=0111110010$. The receiver un-stuffs first (remove the 0 after five 1s) to recover 011111010, then CRC-checks it. ✅

After $k=3$ collisions, the range is $[0,2^3-1]=[0,7]$ → possible waits $\{0,1,2,3,4,5,6,7\}$, that's $8$ equally-likely values. $P(\text{wait}=0)=\frac{1}{8}=\mathrm{0.125.}$ Why exponential? Each collision doubles the window, spreading contending stations further apart in time so a repeat collision becomes exponentially less likely — this stabilises a busy Ethernet segment.

Requirements → constraints on $G$:

• (i) all single-bit: $G$ must have $\ge 2$ terms. ✅ easy.
• (ii) all odd-weight: $G$ must have factor $(x+1)$.
• (iii) bursts up to length 4: need $r\ge 4$ (bursts of length $\le r$ are caught). So minimum degree $r=4$. Pick $G(x)$ of degree 4 that has $(x+1)$ as a factor and $\ge 2$ terms. Take $G(x)=(x+1)(x^3+x+1)$. Multiply over GF(2): $(x+1)(x^3+x+1)=x^4+x^2+x+x^3+x+1=x^4+x^3+x^2+(x+x)+1=x^4+x^3+x^2+1.$ ($x+x=0$ over GF(2).) So $G(x)=x^4+x^3+x^2+1$. Bit string (powers $x^4{x}^3{x}^2{x}^1{x}^0$): $11101$. Check: 4 terms → $\ge 2$ ✅; contains factor $(x+1)$ by construction ✅ ($G(1)=1+1+1+0+1=0$); degree 4 ✅.

(a) $\tau =\frac{\text{distance}}{\text{speed}}=\frac{2000}{2\times 10^8}=10^{-5}\text{s}=10\mu s.$ (b) $L_{\min }=2B\tau =2\times 10^7\times 10^{-5}=200$ bits $=25$ bytes. (c) 64 bytes $=512$ bits $>200$ bits, so the frame lasts far longer than one round trip $2\tau$ — the sender is guaranteed still transmitting when any collision echo returns. Safe. ✅

$G=11001$, what is $r$ and how many zeros are appended? $r=4$; append 4 zeros.

Compute CRC over payload first, then bit-stuff (payload+FCS), then add flags. Reverse breaks the check.

$(x+1)\mid G$ guarantee odd-weight detection? $E(1)=1$ for odd weight, but if $G\mid E$ then $(x+1)\mid E$ so $E(1)=0$ — contradiction.

$L_{\min }$ for $B=10^7$, $\tau =10\mu s$? $2B\tau =200$ bits $=25$ bytes.