In order to delimit messages from a stream of bits being exchanged on a data link, a sender marks the beginning and end of each message with a control flag. In order to prevent the receiver from inadvertently detecting the end of a message when a pattern in the data matches the control flag, the sender stuffs extra bits or characters into the data as necessary, while the receiver removes these extra bits or characters. Assume that a sender and receiver are exchanging data on a link using bit stuffing.
(a) Given a message containing the following bits: 1111101010000111111110001
What bit pattern (including the beginning and ending flags and any stuffed bits) will the transmitter send?
(b) Given that the following bits arrive at a receiver:
What bit pattern (after you remove the beginning and ending flags and any stuffed bits) will the receiver pass on for higher level processing?
The flag is a sequence 01111110 which delimits the start of the frame. A technique known as bit stuffing is used to insert additional zeros into the data so that a flag sequence never appears anywhere but at the start and end of a frame. These extra bits are "unstuffed" again by the receiver.
For bit stuffing, Each frame begins with a start and end bit ...
This solution is provided in 250 words. It describes bit stuffing and the technique of bit stuffing and unstuffing, as well as determines in each example the message pattern.