Computer Networks: Bit Stuffing

Question

Flag: 01111110
Data: 1000111111100111110100011111111111000011111
bit stuff the given data?

Comments

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. _/\_

---

@sakharam

Answer 1

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.

100011111P110011111P0100011111P111111000011111P

Data Stream after Bit Stuffing

10001111101100111110010001111101111110000111110 (P are replaced by 0)

Comments

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:
 100011111011001111100100011111011111010000111110

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 

100011111011001111100100011111011111010000111110

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—

https://gateoverflow.in/2058/gate2014-3-24