Framing & Bit Stuffing

The problem: where does a frame start?

The physical layer delivers an endless stream of bits. The data link layer has to cut it into frames so that it can add addresses, check for errors with a CRC and deliver each frame. The receiver must know where each frame begins and ends. There are four classic ways:

Method	Idea	Weakness
Character count	A header field says how many bytes follow.	One corrupted count and the receiver loses sync for good.
Flag bytes + byte stuffing	A special byte marks the start and end.	The flag may appear in the data, so it must be escaped.
Flag bits + bit stuffing	A special bit pattern marks the ends.	The pattern may appear in the data, so extra bits are inserted.
Physical-layer coding violations	Use signal patterns that never occur in data.	Only works where the encoding has spare symbols.

Flags are the most common. The trouble is that the data may contain the flag, and stuffing is the trick that prevents it.

Bit stuffing (HDLC)

HDLC (and the framing of many other link protocols) uses the flag 01111110, a 0, six 1s and a 0. The rule:

Sender: whenever five 1s in a row have been sent, insert a 0, whatever the next data bit is. Receiver: whenever five 1s in a row are received and the next bit is a 0, delete that 0.

Because the sender breaks every run of five 1s, the frame body never has six 1s in a row, so 01111110 can only be a flag.

Worked example

Data: 0111111011111010

Step	Bits sent	Count of 1s	Action
first 0	0	0
next five 1s	11111	5	insert 0 (stuffed)
the sixth 1	1	1
0	0	0
five 1s	11111	5	insert 0 (stuffed)
0, 1, 0	010	0

On the wire (with both flags):

01111110  011111010111110010  01111110
 flag     stuffed data          flag

The 16 data bits grew to 18 (two stuffed bits). Without stuffing, 0111111 in the middle of the data would look like the beginning of a flag.

The receiver scans the body: after 11111 it finds a 0 and deletes it. In the 3D model the stuffed bits are pink; switch to De-stuff (receive) to watch the receiver drop them and rebuild the original data. A real receiver reads the bit stream like this:

It sees	Meaning
11111 0	five 1s then 0: the 0 is stuffed, drop it
111111 0	six 1s then 0: a flag (a frame boundary)
1111111	seven or more 1s: an abort (the sender gave up the frame)

Overhead

The data 11111 is sent as 111110: one extra bit per five. In the worst case (all 1s) the frame grows by 20%. For random data a stuffed bit is needed with probability 1/62, which is about 1.6%.

Even the flag can be sent

Data 01111110 is sent as 011111010: the stuffing turns it into something that does not look like a flag at all. That is how a link can carry any bit pattern, which the technical term data transparency means.

Byte stuffing (PPP)

Links that work on whole bytes (like the Point-to-Point Protocol) use the flag byte 0x7E and an escape byte 0x7D:

Sender: if a data byte is 0x7E or 0x7D, send 0x7D and then the data byte XOR 0x20. Receiver: on seeing 0x7D, drop it and take the next byte XOR 0x20 as data.

The XOR makes the second byte different from both special values (0x7E → 0x5E and 0x7D → 0x5D), so the receiver never mistakes it for a flag.

Data bytes	On the wire
41 7E 42 7D 43	7E 41 7D 5E 42 7D 5D 43 7E

The overhead is one extra byte per special byte. For random data that is 2 out of 256 values, about 0.8%, but a frame full of 0x7E bytes would double in size.

Bit stuffing versus byte stuffing

	Bit stuffing	Byte stuffing
Works on	any number of bits	whole bytes only
Flag	01111110	0x7E
What is inserted	a 0 after five 1s	ESC (0x7D), and the byte is changed
Typical use	HDLC, SDLC, USB (a variant)	PPP, SLIP
Frame length	not a multiple of 8 bits	whole bytes

What about errors?

Stuffing makes framing unambiguous when there are no errors. If a bit error creates a false flag in the middle of a frame, the receiver splits one frame into two; if one destroys a flag, two frames merge. Either way the CRC at the end of the frame fails and the damaged frames are discarded. Framing finds the frames; error detection decides whether they are trustworthy.

Code

import random

FLAG = '01111110'

def bit_stuff(data):
    """HDLC bit stuffing: after five 1s in a row, insert a 0."""
    out, ones = '', 0
    for b in data:
        out += b
        ones = ones + 1 if b == '1' else 0
        if ones == 5:
            out += '0'                      # the stuffed bit
            ones = 0
    return out

def bit_unstuff(bits):
    """Receiver: after five 1s the next bit is a stuffed 0, so drop it."""
    out, ones, i = '', 0, 0
    while i < len(bits):
        out += bits[i]
        ones = ones + 1 if bits[i] == '1' else 0
        if ones == 5:
            i += 1                          # skip the stuffed 0
            ones = 0
        i += 1
    return out

def frame(data):
    return FLAG + bit_stuff(data) + FLAG

def deframe(wire):
    assert wire.startswith(FLAG) and wire.endswith(FLAG)
    return bit_unstuff(wire[8:-8])

FLAG_BYTE, ESC = 0x7E, 0x7D

def byte_stuff(data):
    """PPP byte stuffing: a flag or escape byte becomes ESC followed by (byte XOR 0x20)."""
    out = []
    for b in data:
        out += [ESC, b ^ 0x20] if b in (FLAG_BYTE, ESC) else [b]
    return out

def byte_unstuff(data):
    out, i = [], 0
    while i < len(data):
        if data[i] == ESC:
            i += 1
            out.append(data[i] ^ 0x20)      # the byte after ESC is data, flipped back
        else:
            out.append(data[i])
        i += 1
    return out

data = '0111111011111010'
print(bit_stuff(data))
# 011111010111110010
print(frame(data))
# 0111111001111101011111001001111110
print(deframe(frame(data)) == data)
# True
print(bit_stuff('01111110'), bit_stuff('11111'), bit_stuff('1111111111'))
# 011111010 111110 111110111110

stuffed = byte_stuff([0x41, 0x7E, 0x42, 0x7D, 0x43])
print([hex(b) for b in stuffed])
# ['0x41', '0x7d', '0x5e', '0x42', '0x7d', '0x5d', '0x43']
print([hex(b) for b in byte_unstuff(stuffed)])
# ['0x41', '0x7e', '0x42', '0x7d', '0x43']

# Overhead on random data: about one stuffed bit per 62 data bits
random.seed(1)
bits = ''.join(random.choice('01') for _ in range(1_000_000))
print(round((len(bit_stuff(bits)) - len(bits)) / len(bits), 4), round(1 / 62, 4))
# 0.0161 0.0161

Common mistakes

• Stuffing after six 1s. The rule is five 1s: the flag has six, and the stuffed bit has to break every run before it gets there.
• Counting the stuffed 0 as data. It is removed by the receiver, and the count of 1s restarts after it.
• Forgetting to stuff at the end. If the data ends in 11111, a 0 must still be added, or the closing flag would merge with it.
• Stuffing the flags themselves. Only the data between the flags is stuffed.
• Using byte stuffing without changing the byte. Sending just ESC + 0x7E would still leave a 0x7E in the stream. The XOR 0x20 is what removes it.