Question
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
Official answer and solution
- Official answer
- B
- From
- Official GATE 2014 answer key
Solution
Reverse the bit-stuffing procedure by locating the stuffed zero after five consecutive ones.
-
Bit-stuffing protocol rules (HDLC standard):
- Delimiter pattern:
01111110(six consecutive 1s bounded by 0s). - Transmitter rule: Whenever the transmitter detects five consecutive 1s (
11111) in the data bit-stream, it automatically inserts (stuffs) a0immediately after the fifth 1. - Receiver rule: Whenever the receiver observes five consecutive 1s (
11111), it inspects the next bit:- If the next bit is
0, it is a stuffed bit and is discarded. - If the next bit is
1, followed by0, it is the delimiter flag01111110.
- If the next bit is
- Delimiter pattern:
-
Given stuffed output string:
0 1 1 1 1 1 0 0 1 0 1 -
Scanning from left to right:
- Bit 1:
0 - Bits 2 to 6:
1 1 1 1 1(a sequence of five consecutive 1s). - Bit 7: The bit immediately following the five 1s is
0. According to protocol rules, this0was stuffed by the transmitter! - Removing this stuffed bit (
0at position 7) yields:
0 1 1 1 1 1+0 1 0 1=0111110101.
- Bit 1:
-
This matches option B.
Final answer
B
Common trap
Removing the second 0 instead of the first 0 that immediately follows the run of five 1s.
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2014 Computer Science and Information Technology (CS) Session 3
- Question
- 34 of 65, printed as CS Q.24
- Section
- Computer Science and Information Technology
Report an error in this question
GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.