Bit Stuffing Algorithm: Worked Encoding, De-stuffing and Exam Traps

The rule "insert a 0 after five consecutive 1s" sounds easy until the data already contains a flag, an original 0 follows the fifth 1, or the receiver must tell stuffed bits from data. The 21-bit payload 011111101111101111110 becomes 24 bits after stuffing, returns to 21 bits after de-stuffing, and makes each overhead denominator explicit. The trace uses the delimiter 01111110, with both delimiter flags outside the stuffed content.

Why bit stuffing is needed in delimiter-based framing

At the data-link layer, framing gives the receiver an unmistakable boundary between frames. A common teaching delimiter is the HDLC-style flag 01111110: one 0, six consecutive 1s, and one 0.

The problem is that raw data may legally contain those same eight bits. For example, the payload 01111110 is identical to the flag. An unmodified receiver could treat that payload as a boundary and split the frame incorrectly.

Bit stuffing makes the protected content transparent. After the sender processes this payload, it becomes 011111010: a 0 is inserted after the first five consecutive 1s. The content can no longer contain six uninterrupted 1s, so it cannot reproduce the delimiter. For wider context, CS Fundamentals for Exams & Placements maps the broader study area, while Computer Networks explains the subject overview.

The sender algorithm counts consecutive 1s

The sender counts a run, not the total number of 1s in the content. Any original 0 ends the current run.

ones = 0
for each input bit:
    emit the input bit
    if the bit is 1:
        ones = ones + 1
    else:
        ones = 0
    if ones == 5:
        emit an extra 0
        ones = 0

Consider the boundary case 111110. The sender emits the fifth 1, inserts a stuffed 0, and then continues to the original final 0. Therefore:

111110 becomes 1111100.

The two ending zeros have different roles. The first is stuffed and the second belongs to the input. Stuffing inserts a bit; it never replaces the next original bit.

Textbook questions may give only a payload, while a protocol may protect a larger content field between flags. Process exactly the bits named in the question. Do not carry the counter into either flag.

Worked example: stuff a 21-bit payload step by step

The worked payload is:

011111101111101111110

Its length is 21 bits. Separating it at its original zeros exposes the runs clearly:

0 | 111111 | 0 | 11111 | 0 | 111111 | 0

The three runs of 1s have lengths 6, 5, and 6. Now scan each chunk and insert a zero immediately after every fifth consecutive 1.

Concatenating the emitted chunks without spaces gives:

011111010111110011111010

The stuffed content is 24 bits long. S1, S2, and S3 occupy one-based positions 7, 15, and 22. With two eight-bit flags and no other frame fields, the transmitted sequence for this calculation is:

01111110 | 011111010111110011111010 | 01111110

Its total length is 8 + 24 + 8 = 40 bits. A complete protocol frame may also carry address, control, FCS, and other fields; include them when the stated frame format contains them.

Receiver de-stuffing reverses the rule

The receiver scans only the content between the two flags. It copies received bits while counting consecutive 1s. After copying five 1s, it inspects the next bit. For valid stuffed content, that next bit is 0; the receiver discards it, resets the counter, and continues. An ordinary 0 encountered before the count reaches five is payload and must be copied.

Apply that rule to 011111010111110011111010. Delete only bits 7, 15, and 22, each the zero immediately after a five-1 run. The recovered content is:

011111101111101111110

Its length is 21 bits, exactly matching the sender input. As a useful self-check, the original separator zeros and the flag-like prefix 01111110 must return as data. If either is lost, the run counter was handled incorrectly. A received 1 after five consecutive 1s belongs to delimiter or abort handling by the framing protocol; it is not discarded as a stuffed bit.

Calculate stuffed bits, frame length and efficiency

For a run of r original consecutive 1s, the inserted-zero count is floor(r/5). The worked payload has runs of 6, 5, and 6, so:

floor(6/5) + floor(5/5) + floor(6/5) = 1 + 1 + 1 = 3 stuffed bits.

Keep the denominators separate when calculating ratios:

• Stuffing overhead relative to original content: 3/21 x 100 = 14.29%.

• Useful content within the stuffed interior: 21/24 x 100 = 87.5%.

• Useful content within the simplified flagged sequence: 21/40 x 100 = 52.5%.

The last result includes two eight-bit flags but no other protocol fields.

As a second check, 20 consecutive 1s require floor(20/5) = 4 inserted zeros. The stuffed interior is therefore 20 + 4 = 24 bits, and its useful-content fraction is 20/24 x 100 = 83.33%. Add flag overhead separately only if the question asks for the complete transmitted length.

Bit stuffing versus byte stuffing, plus common traps

Both protect framing transparency, but operate on different units.

Bit stuffing does not insert an entire byte. Avoid four traps:

• Counting five 1s anywhere -> extra zeros -> count only consecutive runs.

• Waiting for six 1s -> a flag may appear -> insert after the fifth.

• Replacing an original 0 -> lost data -> insert, then resume the original stream.

• Stuffing the flags -> broken boundaries -> exclude both delimiters.

The reset detail is visible in 111111. Its correct stuffed form is 1111101, with one inserted zero between the fifth and sixth original 1. The inserted zero resets the count. The sixth original 1 starts a new count.

How exams test bit stuffing

Questions usually take one of four mechanical shapes: compute the stuffed stream, recover the original stream, count inserted bits or total length, or distinguish bit stuffing from byte stuffing and delimiters from protected content.

• Input 11111011111 contains two separate five-1 runs. Its stuffed form is 1111100111110, length 13, with 2 inserted zeros.

• De-stuff received content 011111010 by removing the zero after five 1s. The recovered data is 01111110.

• For separated run lengths 4, 5, and 11, the count is floor(4/5) + floor(5/5) + floor(11/5) = 0 + 1 + 2 = 3 inserted zeros.

For broader practice, use Computer Networks MCQs. That collection spans the wider subject; bit-stuffing practice is narrower, tracing each inserted zero through encoding, reversal, and overhead calculations.

The short version and the next practice step

Use a five-step solver: mark the flags, isolate the protected content, scan left to right with a consecutive-ones counter, insert or remove only the zero immediately after a count of five, and verify both the final string and its length. For the worked example, remember 21 -> 24 -> 40 -> 21: original content, stuffed interior, simplified flagged sequence, recovered content.

For structured study, use GATE Guidance by Sanchit Sir. For a broader core-CS route that includes Computer Networks, use CS Fundamentals for Placements by Sanchit Sir. Then practise sender and receiver traces until every inserted zero can be justified by its five preceding 1s.