A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is01111100101, then the input bit-string isa)0111110100b)0111110101c)0111111101d)0111111111Correct answer is option 'B'. Can you explain this answer?

Question

Answer

Bit Stuffing is used to create framing.

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.

Alternative approach –

The given delimiter pattern is 01111110. Delimiters are used to define the beginning and end of data.

Since delimiters are special bit-patterns used for special purposes, they must be avoided in the encoded form of the input data. To achieve this, Bit Stuffing is used.

On the sending side, any time five consecutive 1’s have been transmitted from the body of the message (i.e., excluding when the sender is trying to transmit the distinguished 01111110 delimiter sequence), the sender inserts a 0 before transmitting the next bit.

If the receiver gets five consecutive 1’s, it makes its decision based on the next bit it sees (i.e., the bit following the five 1s).

If the next bit is a 0, it must have been stuffed, and so the receiver removes it.

If the next bit is a 1, then one of two things is true: Either this is the end-of-frame marker or an error has been introduced into the bit stream.

Going further and reading the next bit distinguishes these two cases. If the next bit is 0, then it is the end of frame marker (delimiter 01111110), and if the next bit is a 1 then there is must be an error in the frame and it is discarded.

So, For the data sequence 0111111101

Encoding would be – 01111101101

Here the bold 0 is stuffed to distinguish it from the delimiter sequence.

Coming back to the question, the encoded string is – 01111100101 and when the receiver senses that it has received 5 consecutive 0’s then

If the next bit is 0, then it is stuffed

If the next bit is 1, then next to next bit would tell if the frame has ended or there is an error.

In this case, the next bit is 0 which means it was stuffed, so the corresponding input sequence is- 0111110101.

Therefore, option (B) is correct.

Answer

Explanation:
To understand why the input bit-string is 0111110101, we need to understand the concept of bit stuffing and how it is applied in the given scenario.

Bit Stuffing:
Bit stuffing is a technique used in framing protocols to ensure data integrity and synchronization between the sender and receiver. It involves adding extra bits to the data stream to distinguish between data and control information.

In this scenario, the delimiter pattern used for bit stuffing is 01111110. Whenever this pattern is encountered in the data stream, an extra 0 bit is stuffed after it to differentiate it from the actual data.

The given output bit-string after stuffing is 01111100101. Let's break it down and understand the process step by step.

Step 1: Start with the output bit-string: 01111100101

Step 2: Look for the delimiter pattern (01111110) in the bit-string.

Step 3: Whenever the delimiter pattern is found, check the next bit.

- If the next bit is 0, it means it is the stuffed bit and should be discarded.
- If the next bit is 1, it means it is the end of the delimiter pattern and the stuffed bit should be preserved.

Step 4: Apply the above rule to the output bit-string.

- Start with the first bit: 0
- Move to the next bit: 1
- Move to the next bit: 1
- Move to the next bit: 1
- Move to the next bit: 1
- Move to the next bit: 1 (found the delimiter pattern)
- Move to the next bit: 0 (stuffed bit, discard)
- Move to the next bit: 0
- Move to the next bit: 1 (found the delimiter pattern)
- Move to the next bit: 0 (stuffed bit, discard)
- Move to the next bit: 1

Step 5: The resulting input bit-string after stuffing is 0111110101.

Conclusion:
Based on the above steps, we can conclude that the correct answer is option 'B' which is 0111110101.

Similar Computer Science Engineering (CSE) Doubts

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

An eight-bit binary ripple UP counter with a modulus of 256 is holding the count 01111111. What will be the count after 135 clock pulses?

In the waveform (

Suppose that code has the following four valid codewords:00000000110011000011001111111111What is the maximum number of errors that can be correctedfor the abovecode? Correct answer is '1'. Can you explain this answer?

What is stat frame delimeter (SFD) in ethernet frame?

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company