The Gateway to Computer Science Excellence
+35 votes

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:

  1. $0111110100$
  2. $0111110101$
  3. $0111111101$
  4. $0111111111$
in Computer Networks by
edited by | 7.1k views
Delimiter pattern=$01111110$.From this pattern it is clear that we are going to insert $0$ in input string.It means no. of $1$ in input string and output string(after stuffing 0) should be same.So we can directly say ans $b$

8 Answers

+35 votes
Best answer
$011111$ *one zero emitted here* $0101$

Correct Answer: $B$
edited by
Please explain this
In bit stuffing we insert 0 after 5 consecutive occurrence of 1.
So what is the use of delimiter pattern here ???
See the given delimiter patter also supports the same thing. If in input string 01111110 will be present then it will be wrongly interpreted as delimiter, so to avoid that we are inserting 0 after five consecutive occurrences of 1s.
how about inserting a 1 after 6 occurrences of 1?
Explain Clearly Use of Delimeter and why we are using 5 bits instead of 6 bits? Whatever it is please explain in detail. Thanks.
Why a $0$ is stuffed after five $1s$ and not $6$?

The purpose of bit stuffing is to distinguish between delimiter pattern occurring at start and end of the frame from the delimiter pattern occurring in the data part.

Suppose if our frame is as following,

$\overbrace{01111110}^\text{start of frame delimiter}$     $\overbrace{0101\textbf{01111110}10}^\text{data bits}$     $\overbrace{01111110}^\text{end of frame delimiter}$

See those data bits also have the delimiter pattern. We can see stuffing after five consecutive $1s$ is proper since if we stuff a $0$ after six $1s$, it won't make any difference.

Also, the number of $1s$ are the same before and after bit stuffing. by counting the number of $1s$ in options, we can answer this question.

@junk_mayavi Do we always stuff a 0, can't we stuff a 1 after data 0111 111 1 0 ?? 

The bold 1 is stuffed.


@Rishabh Gupta 2 a 0 bit causes signal transition, whereas 1 bit causes no change. if there is no transition for a long time in transmitted data, there is a chance that sender and receiver clock may go out of sync. this can be the case here.  run-length limited encoding deals with this issue. again, this should be implementation specific and defined by RFCs. such an example definition can be seen here


So, if the delimiter pattern was something like 1000 0001, or something where we have more 0s, then what we are going to use for bit stuffing?

@Rishabh Gupta 2 may be in that case, it makes sense if they use 1 to stuff. but those will be implementation specific as I said and it will be given anyway in question.

If 8-bit delimiter pattern was 01111111 , then we would have added pseudo 0 after 0 followed by 6 1's ?

we see pattern of delimiter till (n-1) bit prefix???why here (n-2) first have considered 

i.e we should match 01111110 pattern? how 01111110?

what is wrong with it please specify

same doubt... Plz help
yes sandy right!!
+15 votes

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)

+4 votes
B option
as there is no presence of delimiter pattern thus it will remain unchanged .Am i right?
+3 votes

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. 
you've highlighted the wrong zero
+3 votes

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



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)

+1 vote

$\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$

–1 vote
I think end delimiter pattern should be 0111110 (five 1's).
–2 votes
Option B

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,580 answers
95,396 users