GATE CSE 2014 | Set 3 | Question: 24

Question

A bit-stuffing based framing protocol uses an $\text{8-bit}$ delimiter pattern of $01111110.$ If the output bit-string after stuffing is $01111100101,$ then the input bit-string is:

• A. $0111110100$
• B. $0111110101$
• C. $0111111101$
• D. $0111111111$

Comments

Not a part of GATE 2027 syllabus (DLL framing is removed)

---

This question seems to be a good example of bit stuffing being performed even when it isn't necessary to prevent the delimiter pattern.

---

Thanks for the comment 😊

Answer 1

$011111$ *one zero emitted here* $0101$

Correct Answer: $B$

Comments

YESS!!

---

This might help

---

Adding this snippet of information forouzan

Answer 2

here delimeter is "01111110" .....

so rule will be like this ...

at sender :- add 0 after each occurance of "011111" in input data..

at Reciever :- remove 0 for each occurance of "011111" in output.....

According to que Output string is "01111100101" 

so input will be "01111100101".. (i.e - 0111110101)

Answer 3

When delimiter pattern appears in data, we do stuffing so that data is not interpreted as a delimiter.

We usually stuff 0 and break the delimiter pattern present in data.

Now we have some data which has a delimiter pattern. (there could be any sequence of 0's and 1's before and after this delimiter pattern)

...

0

1

1

1

1

1

1

0

...

We can break the pattern by stuffing 0 after

• 2 consecutive 1's
• 3 consecutive 1's
• 4 consecutive 1's
• 5 consecutive 1's

We cleverly choose to stuff a 0  only after 5 consecutive 1's because by doing so we reduce the number of 0's to be stuffed and thereby also number of 0's un-stuffed later while reading this frame.

(Ex: If we stuff a 0 after every 2 consecutive 1's, we will have to stuff every time 2 consecutive 1's appear in the data. This would be too many times. And also while reading the frame, every 0 that occurs after 2 consecutive 1's has to be un-stuffed. This is not so clever)

Answer 4

B option

Comments

as there is no presence of delimiter pattern thus it will remain unchanged .Am i right?

Answer 5

Answer B.

8-bit delimiter pattern is 01111110. 

The output bit-string after stuffing is 01111100101.

The above highlighted bit is stuffed bit.  
So input bit-string must be 0111110101. 

Comments

you've highlighted the wrong zero

Answer 6

$\text{Bit-Stuffing}:$ Bits stuffing is the insertion of noninformation bits into data and it is used for synchronization purpose example

 

$A. 0111110100 \rightarrow 011111\color{red}{0}0100$ 

$B. 0111110101 \rightarrow 011111\color{red}{0}0101$ 

$C. 0111111101 \rightarrow 011111\color{red}{0}1101$

$C. 0111111111 \rightarrow 011111\color{red}{0}1111$

So Option $B$