CRC and multiple access math
This is an optional deep dive. Link layer services and error detection describes what a CRC guarantees, and Multiple access protocols describes the protocols. Here the arithmetic is worked out so the numbers are not taken on trust.
CRC by hand
Section titled “CRC by hand”Real CRCs use a 32-bit generator. A 4-bit generator shows the same mechanics.
Setup. The data D is 101110 (6 bits). The agreed generator G is 1001 (4 bits, so r = 3 check bits). Arithmetic is modulo 2: addition and subtraction are both XOR, with no carries.
Goal. Choose R, a 3-bit value, so that the frame D followed by R is exactly divisible by G.
Method. Shift D left by r places (append three zeros), divide by G, and use the remainder as R.
Dividend: 101110000. Divisor: 1001.
| Step | Working bits | XOR with 1001 | Remainder so far |
|---|---|---|---|
| 1 | 1011 | 0010 | 010 |
| 2 | 0101 (bring down next bit) | leading 0, skip | 101 |
| 3 | 1010 (bring down) | 0011 | 011 |
| 4 | 0110 (bring down) | leading 0, skip | 110 |
| 5 | 1100 (bring down) | 0101 | 101 |
| 6 | 1010 (bring down) | 0011 | 011 |
The final remainder is 011, so R = 011 and the transmitted frame is 101110 followed by 011: 101110011.
Check at the receiver. Divide 101110011 by 1001 the same way. The last step gives 1001 XOR 1001 = 0000, a zero remainder, so the frame is accepted. Flip any single bit and the remainder becomes nonzero. For example, 101111011 leaves a nonzero remainder, and the frame is rejected.
The polynomial view
Section titled “The polynomial view”Treat the bits as the coefficients of a polynomial. G = 1001 is x^3 + 1, and D = 101110 is x^5 + x^3 + x^2 + x. The division is polynomial division over a field with two elements. This view explains the guarantees:
- A burst of
bconsecutive bad bits is the error polynomialx^i (some polynomial of degree b-1). Ifb <= r, its degree is lower thanG’s, andGhas a constant term, soGcannot divide it. The error cannot hide. Every burst ofrbits or fewer is detected. - A generator that has
(x + 1)as a factor catches any odd number of flipped bits. The small example above does:x^3 + 1factors as(x + 1)(x^2 + x + 1). The 32-bit Ethernet generator does not have that factor, so it does not promise the odd-count property. It is chosen instead for its behavior at real frame sizes, where it detects every error of 1, 2, or 3 flipped bits in addition to every burst up to 32 bits. - For a longer burst, the chance that the error polynomial happens to be divisible by
Gis about0.5^r. Forr = 32that is about 1 in 4.3 billion.
The same 32-bit generator is used unchanged across Ethernet and Wi-Fi. In hardware the division is a shift register with a few XOR gates, so each bit is processed as it arrives.
ALOHA efficiency
Section titled “ALOHA efficiency”Efficiency means the long-run fraction of slots (or time) that carry a successful transmission.
Slotted ALOHA
Section titled “Slotted ALOHA”N nodes each transmit in a slot with probability p. A particular node succeeds if it transmits and the other N - 1 do not:
P(node i succeeds) = p (1 - p)^(N-1)P(some node succeeds) = N p (1 - p)^(N-1)Maximize over p. Setting the derivative to zero gives p* = 1/N. Substituting:
efficiency = N (1/N) (1 - 1/N)^(N-1) = (1 - 1/N)^(N-1)As N grows large, (1 - 1/N)^(N-1) approaches 1/e.
efficiency = 1/e = 0.368At the optimum, about 37% of slots succeed, 37% are empty, and 26% collide. The empty slots and the collided slots are both wasted, and tuning p only trades one for the other.
Pure ALOHA
Section titled “Pure ALOHA”With no slots, a frame sent at time t0 collides with any other frame that starts in (t0 - 1, t0 + 1), where time is measured in frame lengths. That window is two frame times long, so the other N - 1 nodes must all stay quiet through twice as much time:
P(node i succeeds) = p (1 - p)^(2(N-1))Maximizing over p and letting N grow gives:
efficiency = 1/(2e) = 0.184The price of removing synchronization is exactly half of the throughput.
CSMA/CD details
Section titled “CSMA/CD details”The slot time and the minimum frame
Section titled “The slot time and the minimum frame”The backoff unit is 512 bit times. At 10 Mbit/s one bit takes 0.1 microseconds, so 512 bit times is 51.2 microseconds. This is not arbitrary. A sender must still be transmitting when news of a collision comes back from the farthest point on the network. If the round-trip propagation time across the whole network is below 51.2 microseconds, a 512-bit transmission is always long enough for the sender to hear the collision before it finishes. That is why Ethernet has a 64-byte minimum frame (512 bits). A frame shorter than that could finish sending before the collision signal returned, and the sender would wrongly believe it was delivered.
This is also why shorter frames are padded, and why each higher speed that kept CSMA/CD had to shrink the maximum network diameter (or extend short frames) in proportion.
Backoff windows
Section titled “Backoff windows”After the nth collision of a frame the adapter picks K uniformly from {0, ..., 2^n - 1}, with n capped at 10.
| Collisions | Choices for K | Chance two colliding adapters pick the same K | Longest wait at 10 Mbit/s |
|---|---|---|---|
| 1 | 0 to 1 | 1 in 2 | 51.2 µs |
| 2 | 0 to 3 | 1 in 4 | 153.6 µs |
| 3 | 0 to 7 | 1 in 8 | 358.4 µs |
| 10 | 0 to 1023 | 1 in 1024 | about 52 ms |
Each collision doubles the window, so each retry halves the chance that the same pair collides again. The delay is adaptive. A lightly loaded network resolves a collision after about one slot, and a heavily loaded one spreads the contenders over a long window.
Efficiency
Section titled “Efficiency”Define d_prop as the maximum propagation delay between two adapters, and d_trans as the time to send a maximum-size frame. The standard approximation is:
efficiency = 1 / (1 + 5 d_prop / d_trans)Take a 10 Mbit/s network with 1,500-byte frames and half of the 51.2 µs slot time as one-way delay:
d_trans = 12,000 bits / 10 Mbit/s = 1.2 msd_prop = 25.6 µsefficiency = 1 / (1 + 5 x 0.0256 / 1.2) = 1 / 1.107 = 0.90
About 90% of the channel carries useful frames. Two limits make sense of the formula. When propagation delay shrinks toward zero, collisions are detected at once and almost no time is wasted. When frames get very long compared with the delay, each success occupies the channel for so long that the cost of a collision is negligible. The same formula explains why a short, fast network is an easy case for CSMA/CD and a long, fast one is not.