In HDLC, how to recognize bit stuffing?

Question

In framing for the HDLC protocol, assume the receiver receives the following string of bits:

[…] 011111010 […]

How can it realize whether the sequence “011111010” is real data, or the result of a bit stuffing operation from an original flag-like sequence “01111110”?

how can the receiver recognize the two different options?

Answer 1

Simply. There are no two options. The sequence 01111110 (0x7E) is not allowed for the original data in the frame, i.e. it is reserved for the flags. So, while bit-stuffing, only data bit sequences are affected, but not flag bit sequences. Such any sequence the receiver sees with 5 ones in a row is definitely not a flag sequence, which has kept its successive 6 ones.

Noting that the flag character has the bit pattern 01111110 (a contiguous sequence of six 1 bits), bit stuffing arranges for a 0 bit to be inserted after any contiguous string of five 1 bits appearing in a place other than the flag character itself.

-- (reference see below)

Note that any data bit sequence of pattern [x zeroes] [5 ones] [y zeroes] is stuffed to [x zeroes] [5 ones] [y+1 zeroes]. So you will receive e.g. a data sequence of 01111101 as 011111001, one of 011111001 as 0111110001and so on. The receiver knows that this happens on sender-side and removes any additional zero after 5 ones at unstuffing.

And when byte-stuffing any 0x7E found in the data is replaced by the 2-byte 0x7D5E, whereby 0x7D serves as an escape character, before being put into the frame. Again, the flag sequences remain untouched.

See K.R.Fall & W.R.Stevens (2012), TCP/IP Illustrated Volume 1: The Protocols, 2nd Ed., Addison-Wesley, pp.131 for the whole procedure:

The PPP frame format, in the common case when HDLC-like framing is used [...], is surrounded by two 1-byte Flag fields containing the fixed value 0x7E. These fields are used by the two stations on the ends of the point-to-point link for finding the beginning and end of the frame. A small problem arises if the value 0x7E itself occurs inside the frame. This is handled in one of two ways, depending on whether PPP is operating over an asynchronous or a synchronous link. For asynchronous links, PPP uses character stuffing (also called byte stuffing). If the flag character appears elsewhere in the frame, it is replaced with the 2-byte sequence 0x7D5E (0x7D is known as the “PPP escape character”). If the escape character itself appears in the frame, it is replaced with the 2-byte sequence 0x7D5D. Thus, the receiver replaces 0x7D5E with 0x7E and 0x7D5D with 0x7D upon receipt. On synchronous links (e.g., T1 lines, T3 lines), PPP uses bit stuffing. Noting that the flag character has the bit pattern 01111110 (a contiguous sequence of six 1 bits), bit stuffing arranges for a 0 bit to be inserted after any contiguous string of five 1 bits appearing in a place other than the flag character itself. Doing so implies that bytes may be sent as more than 8 bits, but this is generally OK, as low layers of the serial processing hardware are able to “unstuff” the bit stream, restoring it to its prestuffed pattern.