Skip to content
Documentation Background

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.


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.

StepWorking bitsXOR with 1001Remainder so far
110110010010
20101 (bring down next bit)leading 0, skip101
31010 (bring down)0011011
40110 (bring down)leading 0, skip110
51100 (bring down)0101101
61010 (bring down)0011011

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.

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 b consecutive bad bits is the error polynomial x^i (some polynomial of degree b-1). If b <= r, its degree is lower than G’s, and G has a constant term, so G cannot divide it. The error cannot hide. Every burst of r bits 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 + 1 factors 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 G is about 0.5^r. For r = 32 that 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.


Efficiency means the long-run fraction of slots (or time) that carry a successful transmission.

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.368

At 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.

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.184

The price of removing synchronization is exactly half of the throughput.


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.

After the nth collision of a frame the adapter picks K uniformly from {0, ..., 2^n - 1}, with n capped at 10.

CollisionsChoices for KChance two colliding adapters pick the same KLongest wait at 10 Mbit/s
10 to 11 in 251.2 µs
20 to 31 in 4153.6 µs
30 to 71 in 8358.4 µs
100 to 10231 in 1024about 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.

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 ms
  • d_prop = 25.6 µs
  • efficiency = 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.