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

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$

---

Similar question: https://gateoverflow.in/3724/gate2004-it-80

---

Why we are not stuffing a ‘1’ after 6 consecutive 1?

Answer 1

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

Correct Answer: $B$

Comments

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. 

---

Thanks.

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!!

---

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?