7,152 views

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

1. $01101011$
2. $011010110$
3. $011101100$
4. $0110101100$

### 1 comment

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

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.

@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.

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/