Audit the Stuffing Overhead and Marker Guarantee

Ada measures byte- and bit-stuffing overhead and proves the boundary marker is unique

ADA · CALCULATION AUDIT

Audit the Stuffing Overhead and Marker Guarantee

To find message boundaries, the chapter marks frames with the flag byte 7E and then must stop ordinary data from imitating it. Byte stuffing escapes any payload byte equal to 7E, while bit stuffing inserts an extra 0 after five consecutive 1 bits, so the data stream can never reproduce the marker. This audit measures the overhead each mechanism adds and proves the boundary guarantee holds: how many extra bits or bytes does stuffing cost, and can payload data ever look like the marker?

Companion to the chapter Packet Framing — every number here comes from that chapter.

A framing marker is a physical signal pattern as well as a parsing rule: count the bits or bytes the transmitter adds, then prove the data stream cannot imitate the boundary.

1. Byte stuffing for the chapter's flag example

The escaping figure uses flag byte 7E. When a payload byte is itself 7E, the transmitter sends an escaped pair instead of the single data byte:

1 payload byte that equals 7E → 2 transmitted bytes

extra bytes = 2 - 1 = 1 byte; expansion for that byte = 1 / 1 = 100%

The overhead is local to ambiguous bytes: ordinary payload bytes still cost one transmitted byte each, while each flag-valued payload byte pays one extra escape byte.

2. Bit stuffing blocks a false marker

The chapter states that bit stuffing inserts one 0 after five consecutive 1 bits. A run of five payload ones therefore becomes six transmitted bits:

11111 → 111110

extra bits = 6 - 5 = 1 bit; expansion for that run = 1 / 5 = 0.20 = 20%

The common flag byte 0x7E is binary 01111110, which contains six consecutive ones. Because the transmitter inserts a 0 immediately after any five data ones, payload data cannot produce that six-one run on the wire.

Mechanism	Chapter value	Audit result
Byte stuffing	Payload byte equals 7E	1 extra byte for that ambiguous byte
Bit stuffing	Insert 0 after five 1 bits	1 extra bit per five-one run, or 20% for that run
Boundary guarantee	0x7E = 01111110	Six consecutive data ones cannot appear unstuffed

What the mathematics buys you: escaping is not magic; it is a measurable overhead paid to preserve a parser invariant. The receiver can trust a delimiter only because the transmitter proves that ordinary data cannot look like the delimiter.

Every number above is taken from this chapter's own worked example and re-derived step by step.