The Gateway to Computer Science Excellence

+35 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$

+35 votes

+5

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.

+3

Explain Clearly Use of Delimeter and why we are using 5 bits instead of 6 bits? Whatever it is please explain in detail. Thanks.

+34

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.

+4

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

+11

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

+5

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

0

If 8-bit delimiter pattern was 01111111 , then we would have added pseudo 0 after 0 followed by 6 1's ?

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

+3 votes

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)

+1 vote

$\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$

52,375 questions

60,580 answers

201,987 comments

95,396 users