The Gateway to Computer Science Excellence
+3 votes
Flag: 01111110
Data: 1000111111100111110100011111111111000011111
bit stuff the given data?
in Computer Networks by | 3.4k views
if possible can you go through the below discussion?
i have followed standard convention, one thing you should notice that you should not stuff o if you get '011111' after stuffing '0'....because newly created '011111' pattern was not present in the data, it is created due to stuffing..

@joshi_nitish. '0' will be stuffed or '1' ???

Because if we stuff a '0', receiver will not be able to distinguish the flag and data. ...0111110...

I have confusion in this topic. Can you provide some link for this. _/\_


1 Answer

+3 votes

Flag: 01111110
Data: 1000111111100111110100011111111111000011111

whenever we encounter 11111(5 ones) after a 0 we would insert 0 in the data after 011111 0

Note that the last zero above(bold one) is not a part of original data stream.

Positions where 0 will be stuffed are indicated by P highlighted in yellow.

Ref : Forouzan

Note : 0 will be stuffed after every stream of 11111 which follows a 0 in the data stream.


Data Stream after Bit Stuffing

10001111101100111110010001111101111110000111110 (P are replaced by 0)

edited by
do we need to stuff a bit after one 0 and 5 consecutive 1's (011111) or five consecutive 1's?
yes a zero would be added.
did you even read my comment??
when will we stuff a 0 after 011111 or 11111?

this is from Forozuan, we will stuff a 0 after 011111 not 11111:


Sorry for the inconvenience Manu 

I was also having doubt on this part which you asked. 
I think below may help you

So, whenever we encounter 11111 after a 0 we would insert 0 in the data after 011111 0

Reference : Forouzan 

Yes. Thanks. Because of you my 1/2 marks are saved in Gate 18 If any question comes based on this concept :)

yes, so you should update your solution by mentioning the same.
If we have to add one 0 after each 011111, then my doubt is:

why are we stuffing 0 at 4th place, because if we consider already stuffed bit then it makes pattern as 011111, please note this 0 in this pattern is not from data it's stuffed by us.

Yes, you're right.

When the sender is inserting a 0 after every five 1's which is followed by a 0.

So, a zero in fourth place won't be inserted because when the receiver will unframe the data

the zero at 3rd place would be removed and after that we would have only streams of 6 ones in continous go without having a zero before.(The zero which was removed was not part of data)
Yes, had been a single or more zero here then a zero would have been inserted into 4th place.
Will change and update my answer
what is your final answer?
is it fine  now?

now you're trapped :) :) 
look the following screenshot form Tanenbaum:

PS: Forozuan is an useless book, i have found 3-4 mistakes in this book!


okay even if we follow the above approach then the 


see the highlighted 0.

Then, also when receiver will see a five stream of 1's it will automatically remove a zero after five ones'

In that case, would the data stream be affected?

Answer won't change in above case also.

as per the tanenbaum we have to stuff a 0 at 4th place also as you did earlier, but as per Forozuan we shouldn't.
Data at receiver side will remain same but it stuffed data in both approach will change
Hence, it depends on the sender and receiver how they agree for bit stuffing after all it's a synchronization mechanism. We cannot say in real world environment that according to one book it must be this or that. Results must be general.

So, as long as sender and receiver are agreeing on the framing policy, no problem would come.

Also, in GATE I have never seen such questions where there would be ambiguity in deciding answer in these types of questions. If ever they will come, they may come under multi-statement true type questions.

Hence forouzan is also correct :)
I am confused with one thing, in every comments it is mentioned as five 1s. But the flag has 0(six)1s0. How do you conclude five 1s from the flag description?
if we add stuff bit as 0 after six 1's then it is not consistent. Receiver will not able to decode message correctly. So we add 0 after five 1's.  ;)
I did not get you. Can you explain with an example?

See the discussion and answer of this question—

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,581 answers
95,400 users