bit stuffing

What is bit stuffing?

Bit stuffing refers to the insertion of one or more bits into a data transmission as a way to provide signaling information to a receiver. The receiver knows how to detect, remove or disregard the stuffed bits.

In the data link layer of the Open Systems Interconnection model, a stream of bits is divided into more manageable units, or frames. Each frame contains the sending and receiving information to facilitate transmission.

To separate the frames, an 8-bit flag byte is injected at the beginning and end of the sequence. This keeps the receiver from interpreting the flag as part of the transmitted information.

Bit stuffing can also serve other purposes. For example, it can bring bit streams that don't have the same bit rates up to the same rate to fill buffers or fill frames.

Regardless of the intended purpose, the location of the stuffed bits is transmitted to the receiving end of the data transmission, where the extra bits are extracted and sent back to their original form or bit rate. In this way, bit stuffing enables multiple channels to be synchronized, maximizing the use of available bandwidth.

Alternatively, bit stuffing can be used for run-length limited coding, which limits the number of bits that that can pass without a transition. This reduces the number of consecutive bits with the same value in a data stream to ensure reliable transmission and receipt of data.

However, bit stuffing alone does not guarantee that a payload will be free of transmission errors. Instead, it simply ensures that the transmission begins and ends in the right places. For this reason, Ad hoc error detection techniques must be used to check for issues at the end of the frame and, if errors are present, resend the frame.

Bit stuffing is defined by some to include bit padding, which is the addition of bits to a transmission to make the transmission unit conform to a standard size. It is distinct from bit robbing, a type of in-band signaling.

Real-world examples of bit stuffing

T-carrier systems

Developed by AT&T Bell Laboratories, T-carrier systems provide the digital transmission of multiplexed telephone calls.

The timing or bit rate of T-carrier signals is constantly synchronized between any terminal device and an adjacent repeater or between any two repeaters.

The synchronization is achieved by detecting the transition in polarity for 1 bit in the stream of bits. T1 uses bipolar signaling, where each consecutive 1 bit is represented by voltage with a reverse polarity from the previous bit.

Bits with a value of 0 are represented by a no-voltage time slot. If more than 15 bits in a row are sent with a 0 value, this lull in 1 bit that the system depends on for synchronization may be long enough for two endpoints to become out of sync.

To handle this situation -- the sequence of more than 15 0 bits -- the signal is stuffed with a short, unique data bit pattern, which includes some 1 bits, that is recognized as a synchronization pattern. The receiving end removes the stuffed bits and restores the bit stream to its original sequence.

HDLC packets

In another example of bit stuffing, a standard High-Level Data Link Control (HDLC) packet begins and ends with 01111110. To make sure this sequence doesn't reappear before the end of the packet, a 0 is inserted after every five consecutive 1s.

This was previously referred to as a non-return-to-zero coding scheme in which a 0 bit would have a signal transition and a 1 bit would experience no change in the transmitted data. In this scenario, bit stuffing would insert 0 bits after a sequence of bits with a 1.

This is frequently used in low-speed and full-speed Universal Serial Bus transmissions.