HDLC Bit Stuffing: Zero-Bit Insertion Explained

High-Level Data Link Control (HDLC) uses a process known as bit stuffing to ensure transparent data transmission and maintain proper frame synchronization. This article explains how the HDLC protocol monitors the binary data stream to insert a zero bit after five consecutive ones, how this prevents user payload from being misinterpreted as frame delimiters, and how the receiving device removes the stuffed bits to reconstruct the original message.

The Role of the Flag Sequence

HDLC frames rely on a predefined delimiter called a Flag sequence to identify the beginning and end of a frame. This flag is represented by the specific 8-bit binary pattern 01111110 (hexadecimal 0x7E), which consists of a zero, six consecutive ones, and a zero.

Because the payload data can contain arbitrary binary sequences, user data might naturally contain the pattern 01111110. If transmitted unchanged, the receiver would mistake this user data for the end of the frame, causing premature termination and data corruption.

How the Sender Inserts a Zero Bit (Bit Stuffing)

To prevent the flag pattern from appearing inside the data field, the transmitting hardware continuously scans the outbound binary stream at the physical layer.

1. Continuous Monitoring: The transmitter counts the number of consecutive 1 bits in the data payload.
2. Insertion Rule: Whenever the transmitter detects five consecutive 1 bits (11111), it automatically inserts (stuffs) a single 0 bit immediately after the fifth 1, regardless of whether the next actual data bit is a 0 or a 1.
3. Transmission: The modified bit stream is transmitted across the physical medium.

Example of the Insertion Process

• Original Data: 01111110 (Six consecutive ones)

• After 5th One: The transmitter sees 011111 and inserts a 0.

• Transmitted Stream: 011111010

• Original Data: 01111100 (Five consecutive ones followed by a zero)

• After 5th One: The transmitter sees 011111 and inserts a 0.

• Transmitted Stream: 011111000

By enforcing this rule, the transmitted payload can never contain more than five consecutive 1 bits. As a result, the pattern 01111110 (six consecutive ones) can only occur when an actual frame boundary flag is transmitted.

How the Receiver Processes the Stream (Bit De-stuffing)

The receiving hardware performs the reverse operation to restore the original data:

1. Pattern Detection: The receiver inspects incoming bits and counts consecutive 1s.
2. Fifth One Evaluation: When the receiver counts five consecutive 1 bits (11111), it inspects the sixth bit:
   • If the 6th bit is 0: The receiver identifies it as a stuffed bit, removes (discards) the 0, and routes the remaining data to the payload buffer.
   • If the 6th bit is 1 and the 7th bit is 0: The receiver detects the sequence 01111110, identifying it as a valid HDLC Flag sequence (start or end of frame).
   • If the 6th bit is 1 and the 7th bit is 1 (seven or more 1s): The receiver interprets the sequence as an abort condition or a physical line error.

Through this deterministic hardware-level mechanism, HDLC guarantees data transparency without requiring complex escaping schemes in the higher-layer software.