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

Before we start, two reminders — the arithmetic, and the name of the quotient.

XOR = "are these two bits different?" — 1 if they differ, 0 if they match. Keep that picture in mind for every division below.

---

The scenario matrix

Every CRC/framing/MAC question is one of these cells. Each worked example is tagged with the cell it fills.

#	Case class	What makes it tricky	Example
C1	Standard division — nonzero message, sender side	Get the long division right	Ex 1
C2	Receiver check, no error	Remainder must be exactly 000	Ex 2
C3	Single-bit flip in transit	Remainder ≠ 0 → detected	Ex 3
C4	Undetectable error ($E$ divisible by $G$)	The one case CRC MISSES	Ex 4
C5	Degenerate: all-zero message	Remainder is 000, sanity anchor	Ex 5
C6	Burst error of length ≤ r	Guaranteed caught — why?	Ex 6
C7	Framing overlap: bit stuffing	Different tool, same layer	Ex 7
C8	Exam twist: CSMA/CD min frame	Units, worst-case round trip	Ex 8

We reuse one running generator so the arithmetic stays familiar: $G=1011\iff G(x)=x^3+x+1,r=\mathrm{deg}G=3.$

Recall Why does

$G=1011$ mean $r=3$ and "append 3 zeros"? $G$ has 4 bits, so its highest power is $x^3$; the degree $r=3$. We multiply $M(x)$ by $x^r=x^3$ — appending $r=3$ zeros — to reserve 3 low slots for the check bits.

---

Ex 1 — Standard division (cell C1)

Forecast: guess now — will $R$ have 3 bits or 4? (It must have $r=3$ bits, since $\mathrm{deg}R<r$.)

1. Append $r=3$ zeros → dividend 1101000. Why this step? This is $M(x)\cdot x^3$: shift left to reserve 3 slots for the check bits, exactly as the parent's Step 1.

2. XOR-divide by 1011, aligning $G$ under each leading 1, bringing bits down otherwise. Figure s01 shows the full XOR long division of 1101000 by 1011: the dividend is the top white row; each red row is one XOR of $G$ against the current leading bits; each white row below a red row is the running result after that XOR; the final green row is the surviving remainder 001. Trace top-to-bottom: whenever the leading bit of the running result is 1 we XOR 1011 under it, then slide right. Why this step? Long division asks "how many copies of $G$ fit, position by position?" In GF(2) the only possible answers are 0 or 1, so at each slot we either XOR $G$ in (leading bit 1) or skip (leading bit 0). Repeating this from the top until fewer than $r+1$ bits remain is exactly what strips out every multiple of $G$, leaving only the remainder.

   

   Figure s01 — Ex 1 sender division: dividend 1101000 ÷ 1011, remainder 001 (green).

3. Read the last 3 bits that survive → $R=001$. Why this step? Division stops when what remains has fewer bits than $G$; that leftover is the remainder.

4. Build the frame $T=M\Vert R=1101001=1101001$. Why this step? $T(x)=M(x)x^3+R(x)$ — the appended 3 zeros are overwritten by the 3 check bits.

Verify: the concrete XOR steps in Figure s01 end in 001; and dividing 1101001 by 1011 must give remainder 000 (that is the whole point of appending $R$). We confirm both in Ex 2 and in the machine check below.

---

Ex 2 — Receiver check, clean frame (cell C2)

Forecast: if the parent's algebra is right, you should predict 000 before dividing.

1. Divide 1101001 by 1011 with the same XOR long division, shown explicitly in Figure s02 (top white dividend, red XOR rows, green all-zero remainder row). Why this step? The receiver runs the identical algorithm — it does not know $R$ separately; it just checks divisibility of the whole received string.

   

   Figure s02 — Ex 2 receiver division: clean frame 1101001 ÷ 1011, remainder 000 (green) → accept.

2. Trace it: the quotient bits fall out and the final remainder is 000. Why this step? Because $T(x)=Q(x)G(x)$ exactly — recall $M{x}^r=QG+R$, so $T=M{x}^r+R=QG+R+R=QG$ in GF(2) (since $R\oplus R=0$). $G$ divides $T$ with no leftover.

3. Decision: remainder 000 ⇒ accept. Why this step? A zero remainder means $T$ is a genuine multiple of $G$, which is the exact property the sender engineered; seeing it, the receiver has no detectable error to report, so it passes the frame up.

Verify: 1101001 mod 1011 = 000 — visible in Figure s02 and checked in =VERIFY=. A zero remainder is the anchor truth every later example is measured against.

---

Ex 3 — Single-bit flip in transit (cell C3)

Forecast: the error polynomial is $E(x)=x^i$ (a single power). The parent said single-bit errors are caught if $G$ has $\ge 2$ terms — and $1011$ has three terms. So predict detected (nonzero remainder).

1. Received string 1111001 $=T\oplus E$ where $E=0010000$ (a single 1 in the 3rd position from the left). Why this step? A flipped bit is literally XOR-ing a 1 into that position — that XOR is the error. Counting powers from the right (position 0 = rightmost), the 3rd-from-left bit of a 7-bit word sits at power $x^4$, so $E(x)=x^4$.

2. Divide 1111001 by 1011, worked out fully in Figure s03 (top white dividend, red XOR rows) — the surviving remainder row is nonzero, the alarm bell. Why this step? The receiver cannot know an error happened; it only trusts the remainder, so we must actually run the division.

   

   Figure s03 — Ex 3 division of the flipped frame 1111001 ÷ 1011, remainder 100 (red) ≠ 000 → detected.

3. Remainder = 100 ≠ 000 ⇒ error detected, discard the frame. Why this step? Undetected requires $G\mid E$; here $E(x)=x^4$ (a single term) and $G$ has three terms with nonzero constant, so $G\nmid x^4$ — the remainder is forced nonzero.

Verify: 1111001 mod 1011 = 100 — visible in Figure s03 and checked below. Note CRC only detected; it did not tell us which bit. Repair needs a Hamming Code, not CRC.

---

Ex 4 — The undetectable error (cell C4)

Forecast: danger — if $E(x)$ is a multiple of $G(x)$, the receiver sees another valid frame. Here $E(x)=G(x)$ exactly. Predict NOT detected.

1. Compute received $=T\oplus E=1101001\oplus 0001011=1100010$. Why this step? We deliberately choose $E$ divisible by $G$ to construct CRC's blind spot.

2. Divide 1100010 by 1011 → remainder 000. Why this step? Received $=T\oplus E=QG\oplus G=(Q\oplus 1)G$ — still an exact multiple of $G$ (here the quotient is just $Q(x)\oplus 1$), so the division leaves nothing.

3. Decision: remainder 000 ⇒ receiver wrongly accepts a corrupted frame.

Verify: 1100010 mod 1011 = 000 — checked below. This is why we pick a good $G$: to make such $E$ (multiples of $G$) statistically rare. It is also why CRC is detection, never a guarantee.

---

Ex 5 — Degenerate: all-zero message (cell C5)

Forecast: an all-zero dividend can never make a leading 1 appear, so guess $R=000$.

1. Append 3 zeros → dividend 0000000. Why this step? Same rule regardless of content: $M(x)x^3$.

2. Divide: every leading bit is 0, so we never XOR $G$ in; nothing changes. Why this step? XOR division only acts when the top bit is 1; all-zero input triggers zero operations.

3. Remainder $R=000$, so $T=0000000$. Why this step? When no XOR ever fires, the trailing 3 bits stay exactly as we appended them — all zeros — so this is the algorithm's fixed point and the cleanest test that our division routine is correct.

Verify: 0000000 mod 1011 = 000 — checked below. This is the sanity floor: $M(x)=0\Rightarrow M(x)x^r=0\Rightarrow R=0$. If your code ever returns nonzero here, your division is broken.

---

Ex 6 — Burst error of length ≤ r (cell C6)

Forecast: the parent claimed all bursts of length $\le r$ are detected. Predict remainder ≠ 0 for any nonzero burst up to 3 bits wide.

Part A — the general proof.

1. Write the burst as $E(x)=x^{i}B(x)$ where $B(x)$ has degree $<r=3$ and $B(0)=1$ (a burst starts and ends with the flipped edges). Why this step? A burst confined to a window is a low-degree $B(x)$ shifted left by $x^i$ into position — that factorisation is the key. In Figure s04 the white lane is the 7-bit frame, the red highlighted 3-cell window is $B(x)$, and the yellow arrow shows the $x^i$ shift that slides that window into place.

   

   Figure s04 — Ex 6: a burst as $x^i\cdot B(x)$; red window = $B(x)$ (width ≤ r), yellow arrow = the $x^i$ shift.

2. Ask: can $G\mid E$? $G(x)=x^3+x+1$ has constant term 1, so $G\nmid x^i$ (a power of $x$ shares no factor with a $G$ whose constant term is 1). Why this step? Divisibility of a product needs $G$ to divide one factor; it can't divide $x^i$.

3. So $G$ would have to divide $B(x)$ — impossible because $\mathrm{deg}B<\mathrm{deg}G$ and $B\ne 0$. Why this step? A smaller-degree nonzero polynomial can't be a multiple of a larger one.

4. Conclusion: since $G\nmid E$, the received word $T\oplus E$ is not a multiple of $G$, so the division leaves a nonzero remainder ⇒ every ≤3-bit burst is detected. Why this step? The receiver's verdict is exactly "remainder $=$ result of dividing $T\oplus E$ by $G$". We just proved $G$ cannot divide $E$ and it does divide $T$, so it cannot divide their XOR-sum — the remainder is forced nonzero, which is precisely the detection signal.

Part B — concrete numeric burst.

5. Take the burst $E=0000111$ (a 3-bit burst on the low end) hitting $T=1101001$: received $=T\oplus E=1101001\oplus 0000111=1101110$. Why this step? We instantiate the proof with real bits so you can watch the remainder come out nonzero.

6. Divide 1101110 by 1011, shown in Figure s05 (same colour convention) → remainder 010 ≠ 000 ⇒ detected, exactly as Part A guaranteed.

   

   Figure s05 — Ex 6 concrete burst: 1101110 ÷ 1011, remainder 010 (red) ≠ 000 → detected.

Verify: received $=1101110$ and 1101110 mod 1011 = 010 (nonzero) — checked below, matching the visual in Figure s05.

---

Ex 7 — Framing overlap: bit stuffing (cell C7)

Forecast: the rule inserts a 0 after every five consecutive 1s. There are six 1s in a row, so the count reaches five inside that run — predict exactly one stuffed 0, giving output length $8+1=9$ bits.

1. Scan left to right, counting consecutive 1s: 0 (count 0), then 1 1 1 1 1 — the count hits five. Figure s06 lays this out as a coloured tape: input cells on top, the run of 1s in yellow, and the single green stuffed 0 dropping into place after the fifth 1. Why this step? The rule triggers on the fifth consecutive 1, before the sixth is written.

   

   Figure s06 — Ex 7 bit stuffing: input 01111110 (8 bits, yellow run of six 1s) → output 011111010 (9 bits) with the green stuffed 0 after the fifth 1.

2. Insert a 0 right after the fifth 1: 0 11111 0 …. Why this step? This guarantees the reserved flag 01111110 can never form inside payload — a Physical Layer noise-free boundary marker.

3. Continue with the remaining 1 0: the counter reset to 0 at the insertion, so no more stuffing. Stuffed stream $=011111010=011111010$. Why this step? After the insertion the run-length counter resets; the leftover 1 0 never reaches five, so exactly one 0 was inserted — 8 input bits become 9 output bits.

Verify: input 8 bits → output 9 bits (exactly one 0 inserted); and the flag 01111110 does not occur as a substring of 011111010 — checked below.

Recall Why does bit stuffing belong on this same worked-examples page as CRC?

Both are data-link-layer jobs on the raw stream from the Physical Layer: framing marks boundaries, CRC checks integrity. An exam frame question often chains them — stuff, then CRC, then transmit toward Ethernet.

---

Ex 8 — Exam twist: CSMA/CD minimum frame (cell C8)

Forecast: the sender must still be transmitting when the farthest collision news returns — a full round trip $2\tau$. Predict $L_{\min }=2B\tau$.

1. Worst-case round trip $=2\tau =2(25.6\mu s)=51.2\mu s$. Why this step? Signal goes out ($\tau$) and the collision echo comes back ($\tau$); the sender needs to be mid-transmission the whole time to hear it.

2. Bits sendable in that time: $L_{\min }=B\cdot 2\tau$. Why this step? Bits = rate × time. This is the parent's inequality $\frac{L_{\min }}{B}\ge 2\tau$ solved for $L$.

3. Plug in units carefully: $B=10\times 10^6\text{bits/s}$, $2\tau =51.2\times 10^{-6}\text{s}$: $L_{\min }=10\times 10^6\times 51.2\times 10^{-6}=512\text{bits}.$ Why this step? The $10^6$ and $10^{-6}$ cancel, leaving pure bits — always sanity-check that seconds cancel.

4. Convert to bytes: $512/8=64\text{bytes}$. Why this step? Ethernet's famous 64-byte minimum frame is exactly this number — that's the "aha".

Verify: $L_{\min }=512$ bits $=64$ bytes — checked below. (This is why runt frames < 64 bytes are dropped.) Contrast with Stop-and-Wait & Sliding Window, where timing bounds reliability throughput rather than collision detection.

---

Active Recall

Recall Which single cell of the matrix is CRC's blind spot, and what characterises it?

Cell C4: any error pattern $E(x)$ that is a multiple of $G(x)$. Received $=(Q\oplus 1)G$ is still divisible, so remainder is 000 and the error passes.

Recall In Ex 8, why

$2\tau$ and not $\tau$? The sender needs the collision to reach the farthest node ($\tau$) AND the garbled echo to return ($\tau$) while it is still transmitting — a full round trip.

Recall Stuffed output of

01111110 (8 bits)? 011111010 (9 bits) — one 0 inserted after the fifth consecutive 1.