In HDLC, flag fields delimit the frame at both ends with the unique pattern 01111110.

A single flag may be used as the closing flag for one frame and the opening flag for the next. On both sides of the user–network interface, receivers are continuously hunting for the flag sequence to synchronize on the start of a frame.While receiving a frame, a station continues to hunt for that sequence to determine the end of the frame. Because the protocol allows the presence of arbitrary bit patterns (i.e., there are no restrictions on the content of the various fields imposed by the link protocol), there is no assurance that the pattern 01111110 will not appear somewhere inside the frame, thus destroying synchronization.To avoid this problem, a procedure known as bit stuffing is used. For all bits between the starting and ending flags, the transmitter inserts an extra 0 bit after each occurrence of five 1s in the frame. After detecting a starting flag, the receiver monitors the bit stream.When a pattern of five 1s appears, the sixth bit is examined. If this bit is 0, it is deleted. If the sixth bit is a 1 and the seventh bit is a 0, the combination is accepted as a flag. If the sixth and seventh bits are both 1, the sender is indicating an abort condition.With the use of bit stuffing, arbitrary bit patterns can be inserted into the data field of the frame.This property is known as data transparency.

a. Apply bit stuffing to the following bit string: 111111111111011111101111110.

b. In which instances of bit stuffing for this string is the extra 0 is not strictly necessary for avoiding a flag pattern but necessary for the operation of the algorithm?