Each division step "subtracts" G(x), but over GF(2) subtraction is just XOR (bitwise, no borrows). The table below shows why the two operations coincide.
Left panel: ordinary binary addition carries (1+1=10). Right panel: GF(2) addition wraps (1+1=0) — no carry, so add = subtract = XOR. That is the only arithmetic CRC long division ever uses.
The full XOR long division of 1101000 ÷ 1011: at each row, wherever the leading bit is 1 we XOR (subtract) 1011; where it is 0 we do nothing and slide down. The final three bits 001 are the remainder R we append — read the red arrows top to bottom.
A bit-level timeline: the sender's run of five 1s triggers a stuffed 0 (coral); the receiver's rule "after five 1s, drop the next bit" removes exactly that same 0, so payload is restored and the flag 01111110 can never appear inside data.
Here is the worst case, walked through with the diagram below.
The setup. Node A starts sending. Its signal takes one-way delay τ (seconds) to crawl down the cable to the far node B. Suppose B — hearing nothing yet, because A's signal has not arrived — begins transmitting an instant before A's front reaches it. The two signals collide right at B.
Why 2τ, not τ. That collision's "news" is itself just a signal, and it must travel all the way back from B to A: another τ. So A only learns of the collision at time τ+τ=2τ after it began. To detect the collision, A must still be transmitting at that instant — if A had already finished, it would have nothing to compare against.
Turning "still transmitting for 2τ" into a bit count. A transmits at bandwidth B bits per second. In time 2τ seconds it emits
L=B[secbits]×2τ[sec]=2Bτ[bits]
The seconds cancel, leaving a pure number of bits. Since A must not finish before 2τ, its frame must be at least this many bits long:
Lmin≥2Bτ
Space–time diagram — read the axes first: the horizontal axis is position along the cable (node A on the left, far node B on the right); the vertical axis is time, increasing downward. The lavender line is A's frame front travelling A→B over time τ. The collision (coral dot) happens at B, the moment A's front arrives. The coral line is the collision news travelling B→A, taking another τ. The green bracket on A's side marks the total 2τ A must stay transmitting to catch it. (Same round-trip logic underlies Stop-and-Wait & Sliding Window timing.)
True or false: A byte-count framing scheme is safe as long as the payload never contains the flag byte.
False — byte-count has no flag; its danger is the count field itself getting corrupted, after which the receiver misjudges the boundary and loses sync for all following frames.
True or false: Bit stuffing inserts a 0 after every five 1s including the 1s inside the real flag 01111110.
False — stuffing is applied to the payload only, before the flags are attached. The genuine flag is added afterward and is never stuffed, which is exactly why it stays unique.
True or false: If a CRC check gives remainder 0, the frame is guaranteed error-free.
False — remainder 0 only means the received polynomial is divisible by G(x). An error pattern E(x) that is itself a multiple of G(x) slips through, so it is "assume OK", never "guaranteed OK".
True or false: CRC arithmetic is ordinary binary arithmetic with carries.
False — CRC uses GF(2): addition and subtraction are both XOR, so 1+1=0 with no carry (see the two-panel figure above). That is what lets us implement division with simple XOR gates.
True or false: A larger generator polynomial G(x) always detects more errors.
Mostly true in spirit — a higher degree r catches all bursts up to length r and more error classes, but detection power depends on G's structure (e.g. having factor (x+1) or ≥2 terms), not degree alone.
True or false: In CSMA/CD, once a node hears the medium is idle it may transmit and forget about listening.
False — the "CD" stands for Collision Detection: it must keep listening while transmitting. If it stopped listening it could never learn a distant collision happened.
True or false: Wi-Fi uses CSMA/CD just like wired Ethernet.
False — radios can't reliably hear their own signal drowned by a collision, so Wi-Fi uses CSMA/CA (avoidance): random backoff plus ACKs, not collision detection.
True or false: A MAC address is hierarchical like an IP address, so routers use it to find networks.
False — MAC is flat (a burned-in 48-bit ID with no network structure). It's used for delivery on the local link only; hierarchical routing is the job of IP addresses.
True or false: Making Ethernet's cable longer lets you keep the same minimum frame size.
False — longer cable means larger one-way delay τ, and Lmin≥2Bτ grows with τ. A longer segment forces a larger minimum frame (or lower bandwidth) to keep collisions detectable.
Spot the error: "We append the CRC remainder because XOR-ing it in cancels the message."
Wrong cause — appending R doesn't cancel the message, it cancels the leftover remainder. Since Mxr=QG+R (where Q is the discarded quotient), adding R gives QG+R+R=QG, killing the remainder so the total is a clean multiple of G.
Spot the error: "We append r+1 zeros to the message before dividing, where r=degG."
Wrong count — we append exactly r zeros (multiply by xr), reserving r slots for the check bits. G has r+1bits but that's the divisor's length, not the number of appended zeros.
Spot the error: "During XOR long division, whenever the leading bit is 0 we still XOR with G."
Wrong rule — a leading 0 means we XOR with 000 (i.e. do nothing) and just bring the next bit down. We only XOR the actual G when the leading bit is 1 (see the division figure).
Spot the error: "CRC can correct a flipped bit by locating it from the remainder."
Wrong capability — CRC only detects. It gives a nonzero syndrome but no reliable pointer to which bit. Correction needs a code like Hamming; a failed CRC triggers discard/retransmit.
Spot the error: "In byte stuffing we prefix ESC only before flag bytes in the data."
Incomplete — you must also escape a data byte that equals ESC itself (ESC → ESC ESC), otherwise the receiver can't tell a real escape from a data ESC and unstuffing breaks.
Spot the error: "Binary exponential backoff picks a fixed wait time that doubles each collision."
Wrong — the wait is a random number of slots drawn from [0,2k−1] after the k-th collision (recall k is the collision counter). The range doubles; the actual wait is random within it, which is what de-synchronises colliding nodes.
Why can't we just reserve the flag pattern and skip stuffing entirely?
Because random payload data will eventually produce the exact flag pattern, creating a false boundary. Stuffing guarantees the reserved pattern can never occur inside data.
Why does adding the factor (x+1) to G(x) let it catch all odd-numbered bit errors?
An error polynomial with an odd number of terms evaluates to 1 at x=1; a multiple of (x+1) evaluates to 0 there. So an odd-weight E(x) can't be a multiple of G and is always detected.
Why must the sender still be transmitting when the collision signal returns in CSMA/CD?
Collision detection compares what it hears to what it sends. Once it stops sending it has nothing to compare against, so a late-arriving collision would go unnoticed — hence the Lmin≥2Bτ floor (see the space–time figure).
Why is the worst-case collision round trip 2τ and not just τ?
A bit travels to the far end (τ) where a collision occurs, and the collision news must travel all the way back (τ). The last-to-learn node therefore needs 2τ of airtime. See Stop-and-Wait & Sliding Window for related round-trip timing.
Why does CRC treat bits as polynomial coefficients rather than just as a number?
The polynomial view turns "shift, divide, remainder" into clean GF(2) algebra, where divisibility of E(x) by G(x)exactly characterises which errors escape — a property plain integer arithmetic can't express so neatly.
Why does the data link layer exist at all if the Physical Layer already moves bits?
The physical layer moves raw bits with no notion of message boundaries or bit-flips. The link layer adds framing, error detection, and access control to turn a dumb bit-pipe into a usable frame-delivery service.
Edge case: The payload ends with exactly five 1s and nothing after — does bit stuffing still insert a 0?
Yes — the rule fires after any run of five consecutive 1s regardless of what follows (even end of data). The receiver's matching de-stuffing rule expects and removes that stuffed 0.
Edge case: What happens in CRC if the message M(x) is all zeros?
The dividend M(x)xr is all zeros, so the remainder is 0 and the frame is all zeros — perfectly divisible by G. It's valid, but a valid all-zeros frame carries no information, which is why real links avoid it.
Edge case: An error burst of length exactlyr+1 hits the frame — is it guaranteed caught?
Not guaranteed — CRC guarantees only bursts of length ≤r. A burst of length r+1 can coincide with a multiple of G and slip through, though the probability is small.
Edge case: Two Ethernet nodes on a zero-length cable (τ=0) collide — is a minimum frame size still needed?
In the idealised τ=0 case Lmin≥2Bτ=0, so no size floor is forced. Real cables always have τ>0, and Ethernet fixes 64 bytes to cover its maximum legal segment length.
Edge case: A single-bit error hits a frame but G(x) has only one term (say G=x3). Is it caught?
No — a single-bit error is E=xi, and xi is divisible by x3 whenever i≥3. A generator must have ≥2 terms to guarantee catching all single-bit errors.
G(x) guarantees all single-bit errors are caught?
G must have at least two terms; then no single term xi is a multiple of G.
Recall Restate the minimum-frame inequality and name each symbol.
Lmin≥2Bτ: Lmin = min frame bits, B = bandwidth (bits/sec), τ = one-way propagation delay (sec). The seconds cancel, leaving bits.
Recall In backoff, what is
k and what does it control?
k is the collision counter (k=1,2,3,…) for the current frame; it sets the backoff window [0,2k−1] slots, which doubles each collision.
