GATE CS 2014 Set 3 Q24 — Data Link Layer: Framing, Error Detection, MAC, Ethernet Bridging

In a bit-stuffing protocol with the delimiter pattern $01111110$ (which contains six consecutive $1$s), the transmitter inserts (stuffs) a 0 after every five consecutive 1s in the input data stream to prevent the delimiter from appearing in the payload.

To recover the original input bit-string from the stuffed output, we perform the reverse process (destuffing):

• Scan the stuffed bit-string from left to right.
• Whenever we encounter five consecutive 1s, the immediately following 0 is identified as the stuffed bit and is removed.

Let's apply this to the given stuffed output: $01111100101$

1. We scan the bits: $0$, followed by five consecutive $1$s: $11111$.
   Current sequence: $0\ \underbrace{1\ 1\ 1\ 1\ 1}_{\text{five 1s}}$
2. The next bit in the stream is a $0$. Since it immediately follows five consecutive $1$s, this $0$ is the stuffed bit and must be removed:
   Stuffed stream: $0\ 1\ 1\ 1\ 1\ 1\ \mathbf{\underline{0}}\ 0\ 1\ 0\ 1$
3. Removing the stuffed $\mathbf{0}$ yields the original input stream:
   Input stream: $0111110101$

Thus, the correct input bit-string is $0111110101$, which corresponds to Option B.