A serial protocol marks the start of each frame with a flag pattern, 01111110. Engineers soon notice that ordinary data can contain the same eight bits, and the receiver then sees a frame start in the middle of a payload. Separately, a long run of 1s in the data starves the receiver's clock recovery of transitions. Both problems come from the data being allowed to contain any pattern at all.

How can a protocol stop data from forming certain patterns, without restricting what data can be sent?

The obvious answer, and why it breaks

One obvious answer is to forbid the patterns: tell users not to send six 1s in a row. That makes the link unable to carry arbitrary data, which is unacceptable. Another is to pick a flag so long and strange that data "will never" contain it, which only makes the failure rarer and harder to find. The protocol must accept every possible payload and still guarantee the forbidden patterns never appear on the wire.

The idea: insert a bit, remove it at the other end

Bit stuffing changes the data on the wire, not the data itself. The transmitter watches the bits it sends. Whenever a run of identical bits reaches a set length, it inserts one extra bit of the opposite value. The receiver follows the same rule: after the same run, it knows the next bit was inserted and throws it away. The payload arrives unchanged; only its on-wire form was altered.

Two things follow at once. The wire can never carry a run longer than the limit, so transitions are guaranteed for clock recovery. And a flag that contains a run longer than the limit can never appear inside stuffed data, so it is unique by construction. A stuffed bit that is missing, or a run one longer than allowed, also tells the receiver something went wrong: a free error check.

Build it: stuff, unstuff, measure

The model implements the two rules used in practice. USB inserts a 0 after six 1s. CAN inserts a bit of the opposite value after five identical bits of either value, and the inserted bit starts the next run. It checks that every stream comes back exactly, and measures overhead on random data, on all 1s, and on the pattern that is worst for CAN.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

"""Bit stuffing, two ways.

USB style: after six 1s in a row, insert a 0.
CAN style: after five identical bits in a row, insert one bit of the opposite value
(the inserted bit counts towards the next run).
The receiver removes exactly the bits the rule says were inserted.
"""
import random


def usb_stuff(bits):
    out, ones = [], 0
    for b in bits:
        out.append(b)
        ones = ones + 1 if b else 0
        if ones == 6:
            out.append(0); ones = 0
    return out


def usb_unstuff(bits):
    out, ones, skip = [], 0, False
    for b in bits:
        if skip:
            assert b == 0, "bit-stuff error: seventh 1"
            skip, ones = False, 0
            continue
        out.append(b)
        ones = ones + 1 if b else 0
        if ones == 6:
            skip = True
    return out


def can_stuff(bits):
    out, last, run = [], None, 0
    for b in bits:
        out.append(b)
        run = run + 1 if b == last else 1
        last = b
        if run == 5:
            out.append(1 - b); last, run = 1 - b, 1
    return out


def can_unstuff(bits):
    out, last, run, skip = [], None, 0, False
    for b in bits:
        if skip:
            assert b != last, "stuffing violation: six identical bits"
            skip, last, run = False, b, 1
            continue
        out.append(b)
        run = run + 1 if b == last else 1
        last = b
        if run == 5:
            skip = True
    return out


rng = random.Random(7)
data = [rng.randint(0, 1) for _ in range(10_000)]
cases = {
    "random data": data,
    "all ones": [1] * 1200,
    "CAN worst case (11111 then 0000 1111 repeated)": [1] * 5 + [0, 0, 0, 0, 1, 1, 1, 1] * 150,
}
print(f"{'data':48} {'USB overhead':>13} {'CAN overhead':>13}")
for name, bits in cases.items():
    u, c = usb_stuff(bits), can_stuff(bits)
    assert usb_unstuff(u) == bits and can_unstuff(c) == bits
    print(f"{name:48} {100 * (len(u) - len(bits)) / len(bits):12.1f}% {100 * (len(c) - len(bits)) / len(bits):12.1f}%")
print("PASS: both schemes round-trip; overhead depends on the data, with a fixed worst case")

It prints:

data                                              USB overhead  CAN overhead
random data                                               0.6%          3.2%
all ones                                                 16.7%         20.0%
CAN worst case (11111 then 0000 1111 repeated)            0.0%         25.0%
PASS: both schemes round-trip; overhead depends on the data, with a fixed worst case

Three lessons in three lines. On random data stuffing is nearly free: long runs are rare. Its cost depends on the data, so the length on the wire is not fixed, which complicates timing for any protocol that must know exactly when a frame ends. And the worst case is bounded and known: about 17% for USB on all 1s, 25% for CAN on a pattern where each stuffed bit itself starts a new run of the opposite value. A link's timing budget must allow for the worst case, not the average.

The design space

Stuffing suits low and medium rates where variable length is acceptable. At high rates, protocols prefer fixed-overhead codes, because a fixed-length block is much easier to pipeline than a frame whose length depends on its content.

How real protocols chose

The two rules differ for a reason: USB's NRZI already turns 0s into transitions, so only runs of 1s need breaking. CAN sends levels directly, so runs of either value must be broken.

What breaks

A designer sizes a receive buffer and a frame timeout from the payload length alone (illustrative). On normal traffic, stuffing adds well under 1% and everything fits. Then a customer sends a payload of all 1s: the frame on the wire is about 17% longer, the timeout fires before the frame ends, and the frame is discarded. Only that customer's data triggers it.

• Symptom: frames lost only for particular data content.

• Root cause: buffers and timeouts sized for the average stuffed length, not the worst case.

• Fix: size everything that depends on frame length for the worst-case stuffing ratio, and add all-ones and worst-case patterns to the regression.

Key takeaways

• Bit stuffing inserts an opposite bit after a run of identical bits; the receiver removes it by the same rule.

• It bounds run length, keeps flags unique and gives a free error check, at a data-dependent cost.

• Size every length-dependent buffer and timeout for the worst case: about 17% for USB, 25% for CAN.

Related topics

• Part 2 overview: Encoding and Framing