The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 votes

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:

- $0111110100$
- $0111110101$
- $0111111101$
- $0111111111$

+23 votes

+2

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.

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

+21

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.

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.

+2

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

+8

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

+1

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?

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?

+2

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

+7 votes

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 "**011111 00101**".. (i.e -

+4 votes

+3 votes

Answer B.

8-bit delimiter pattern is 01111110. The output bit-string after stuffing is 01111100101. The above highlighted bit is stuffed bit. So input bit-string must be 0111110101.

0 votes

$\text{Bit-Stuffing}:$ Bits stuffing is the insertion of noninformation bits into data and it is used for synchronization purpose example

$A. 0111110100 \rightarrow 011111\color{red}{0}0100$

$B. 0111110101 \rightarrow 011111\color{red}{0}0101$

$C. 0111111101 \rightarrow 011111\color{red}{0}1101$

$C. 0111111111 \rightarrow 011111\color{red}{0}1111$

So Option $B$

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.5k
- Admissions 592
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,456 questions

53,658 answers

186,156 comments

70,919 users