The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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$
asked in Computer Networks by Veteran (115k points)
edited by | 4.4k views

6 Answers

+23 votes
Best answer
$011111$ *one zero emitted here* $0101$
answered by (319 points)
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

+7 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)

answered by Active (1.4k points)
+4 votes
B option
answered by Boss (16.1k points)
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. 
answered by Loyal (9.3k points)
you've highlighted the wrong zero
–1 vote
I think end delimiter pattern should be 0111110 (five 1's).
answered by Active (1.1k points)
–2 votes
Option B
answered by (453 points)

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
47,937 questions
52,337 answers
67,819 users