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

Before you can read the parent note, you need to own every symbol it throws at you. This page builds each one from absolute zero, in the order they depend on each other. Nothing here is assumed.

0. What is a bit? What is a stream?

The picture: imagine beads sliding down a wire one at a time. Each bead is black ($0$) or white ($1$). Nobody hands you a "this word ends here" card — that is exactly the problem the whole chapter solves.

Why the topic needs it: the Physical Layer delivers only this raw stream. Every later idea — a frame, a check-bit, a collision — is something we bolt onto this featureless line of beads.

1. Grouping bits: byte, frame, payload

The picture: a train. The locomotive at the front is the START flag, the caboose at the back is the END flag / check field, and the boxcars in the middle are the payload bytes.

Why the topic needs it: "framing" literally means drawing the envelope around a run of bits so the receiver knows where the letter begins and ends.

2. Hexadecimal — reading bytes without going cross-eyed

Why the topic needs it: flag bytes (0x7E), escape bytes (0x7D), and 48-bit MAC addresses (AA:BB:CC:DD:EE:FF) are all written in hex. Without hex the numbers are unreadable walls of bits.

3. XOR — the only arithmetic CRC uses

The key surprise is the last one: $1\oplus 1=0$. There is no carry — unlike ordinary addition where $1+1=10$. This "add with no carry" is the entire engine of CRC.

Why the topic needs it: CRC long division is identical to ordinary long division except every "subtract" step is an XOR. Master XOR and the scary division becomes bookkeeping.

4. GF(2) — a tiny number-world with just $\{0,1\}$

The picture: a light switch world. Addition = flip if the other is on. Multiplication = light only if both switches are on.

Why the topic needs it: treating bits as GF(2) numbers is what lets us do algebra on frames. Full detail lives in Polynomials over GF(2); here you only need "add = XOR, no carries".

5. Polynomials as bit strings

The picture: a row of slots labelled $x^3,x^2,x^1,x^0$. Each slot is either lit ($1$, term present) or dark ($0$, term absent).

Why the topic needs it: the whole CRC recipe is stated in this language — $M(x)$, $G(x)$, $R(x)$, "$\mathrm{deg}R<r$". If you can flip between 1101 and $x^3+x^2+1$ in your head, the parent's derivation reads like plain English.

6. The named polynomials: $M,G,R,Q,T,E$

Now every symbol in the CRC section, decoded:

The picture: a rack of boxcars shoved $r$ positions to the left, leaving $r$ empty flatbeds at the back — later we load the FCS onto them.

7. Divisibility and "remainder $=0$"

Why the topic needs it: the receiver's entire test is "divide by $G$, is the remainder $0$?". A $0$ remainder means the frame is a clean multiple of $G$ → assume no error. Any nonzero remainder → definite error. This is why we bothered to make $T$ divisible in the first place.

8. The MAC symbols: $\tau$, $B$, $L$, $k$

Prerequisite map

Every foundation on this page feeds one of the three parent jobs, which merge into the topic. Return now to the parent topic once these click.

Equipment checklist

Cover the right side and answer; reveal to check.