GATE IT 2004 | Question: 80

Question

In a data link protocol, the frame delimiter flag is given by $0111$. Assuming that bit stuffing is employed, the transmitter sends the data sequence $01110110$ as:

• A. $01101011$
• B. $011010110$
• C. $011101100$
• D. $0110101100$

Comments

I think it is better to add bit-stuffing tag here. Similar question where bit-stuffing tag has been added is:

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

---

This might be helpful: https://youtu.be/s8qQ_U32f8k?si=7hu3ubizq8cXWJIo

---

The purpose of bit stuffing is to ensure that the data link layer can clearly distinguish between the frame delimiters (flags) and any identical bit patterns that may appear in the data portion of the frame.

In this question, the flag is given as 0111. To prevent this bit sequence from accidentally appearing in the data and being misinterpreted as a flag, we apply bit stuffing. The goal is to modify the data stream in such a way that the flag pattern never occurs inside it.

The most efficient approach (in terms of algorithmic efficiency) here is to insert a 0 after every two consecutive 1s in the data. This guarantees that the sequence 0111 will never appear in the data portion, since the stuffed 0 will break the run of three 1s required to form the flag.

Therefore, the correct answer is Option D.



NOTE- Why is a 0 inserted after every two consecutive 1s instead of only after the pattern 011 In bit stuffing?
At first glance, one might think of inserting a 0 only after the exact prefix 011. However, this requires pattern-matching with look-behind, which is inefficient in a continuous bit stream. From an algorithmic perspective, it is simpler and faster to track consecutive 1s. By breaking the run after two 1s, we guarantee that three consecutive 1s can never occur, preventing the flag 0111 from ever forming—regardless of what precedes it.

---

To All whom if the concern is about second last position stuffed 0:

To prevent 0111, the transmitter monitors the bits. As soon as it sees 011, it knows the next bit could potentially be a 1, completing the illegal flag. To "break" this, it forcibly inserts a 0. (even after 011 if  there is a 0 still it stuff 0)

At receiver's end: Whenever receiver see 011, I will automatically throw away the very next bit (the stuffed 0) to get the original data back."

so if we do not stuff 0 at second last position, the receiver will throw away the actual data's zero and data would be corrupted.

---

Simple Rule : 

If the flag contains k consecutive 1's, insert a 0 after every (k−1) consecutive 1's.

• Flag = 01111110 → five consecutive 1's → insert 0 after 5 ones (HDLC rule).
   
• Flag = 0111 → three consecutive 1's → insert 0 after 2 ones.

Hence, 

Mostly Gate asks questions related to HDLC rule only now, but if asked like this, 

Then u have the trick now.

String :       011 0 1011 0 0 
 

Ans (D)

Answer 1

The answer will be option D.

The bit stuffing is done after every two $‘11\text{'} ($as the flag is $0111)$ to differentiate the data part from the flag- there must not be $``111"$ in the data so after every $11$ a $‘0\text{'}$ is added. The receiver also knows this and so, it decodes every $``110"$ as $``11".$ Therefore, option D is the answer.

• http://web.nchu.edu.tw/~pcwang/computer_networks/data_link_layer.pdf
• https://en.wikipedia.org/wiki/High-Level_Data_Link_Control

Comments

@vijay kumar 2

If data=1110111 then I think after stuffing the sequence is 11101101.

If the delimiter is 0111 then we need to add 0 only after the pattern 011.

Ex: 11111111 does not require any bit stuffing at all.

I don't know why in the selected answer it has been mentioned as:

The bit stuffing is done after every two '11'

---

@rohith1001 if you can provide some  reference than it would be great.

Ex: 11111111 does not require any bit stuffing at all.

 

 

I have found something on wikipedia which contradict your statement

Another use of bit stuffing is for run length limited coding: to limit the number of consecutive bits of the same value in the data to be transmitted. A bit of the opposite value is inserted after the maximum allowed number of consecutive bits. Since this is a general rule the receiver doesn't need extra information about the location of the stuffing bits in order to do the de-stuffing. This is done to create additional signal transitions to ensure reliable reception or to escape special reserved code words such as frame sync sequences when the data happens to contain them.

---

Run-length_limited - This is a completely different concept.

My point of taking that example was just to say that we do bit stuffing only when the delimiter pattern appears in data. In the example I took, we don't see the delimiter pattern '0111' so requires no bit stuffing.

Answer 2

In the above question, if, in the data link layer bits stuffing is employed
then bit stuffing is done using the flag delimiter. If there is a flag
of n bits then we will compare the data sequence with the flag and for every
n-1 bits matched found, a bit 0 is stuffed in the data sequence after the matched
sequence.
Thus using the above logic
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with pattern of
3 bits i.e. 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched, hence, 0 in italics
is stuffed. Thus resulting in the data sequence as 0110101100 which is option D

http://www.geeksforgeeks.org/gate-gate-it-2004-question-80/

Answer 3

Answer is D.

Explanation:

For differentiating that we have send the data not the delimiter in betwen we use a 0, process being called stuffing.

Our data that needed to be send = 01110110

Delimiter pattern = 0111

so in our data 0 1 1 “a Zero is stuffed” 1 0 1 1 0

therefore data will be modified as  011010110

but when this data will be send to receiver it will generate problems.

 

Here’s how:

Receiver will read data from left to right as

0 1 1 (Oh the sender stuffed this 0) [cause receiver also knows about the delimiter pattern]

so it will remove the stuffed zero.

next,

0 1 1 1 0 1 1 (Oh this zero must be also added by the sender to remove the delimiter pattern, it must be removed.)

and therefore it will be left with 0111011 

But was this the original data? no!

Therefore an extra 0 will be added to the data to preserve the data.

 

now, the data that will be send should be 0110101100

 

and now the receiver will read the data as

0 1 1 (this zero is stuffed therefore should be removed) 1 0 1 1 (this zero is stuffed therefore should be removed) 0

 

and hence the data will be 0 1 1 1 0 1 1 0 

Comments

mere hi explanation hai visual way mein:

Answer 4

..