possible error in bit stuffing?

[leonardomaccari]

I am not sure the bit stuffing explanation and examples are correct (sect. 2.1.2): "Then, it sends all the bits of the frame and inserts an additional bit set to 0 after each sequence of five consecutive 1 bits." Why would one want to put more than one zero in a sequence like "0111111111111"? according to the text this would be changed into "011111011111011", while it could just be "01111101111111" as the second set of 1s is not mistakable with the marker 01111110. Forouzan describes it differently: "In bit stuffing, if a 0 and five consecutive I bits are encountered, an extra 0 is added", which makes more sense. I tracked the example with the same marker in Tanenbaum's book, where he mentions the HDLC protocol as the one introducing that specific marker, however I can't access the ISO standard now. Wikipedia has a nice page on HDLC, they cite Tanenbaum, and they justify this choice not only to detect the marker, but also to enforce a change of bit for synchronization purposes, which again, makes sense, but then one would need to expand the description a bit and maybe relate it with Manchester encoding.

[qdeconinck]

For the sequence "0111111111111", your description of putting "01111101111111" may make sense. However, if you considered "011111111111", generating "0111110111111" would be problematic, as then the frame delimiter would be added before and after the frame ("01111110", written in italic for convenience), giving "01111110011111011111101111110". This would make the receiver to read it as "01111110011111011111101111110", hence corrupting the frame as it would decode "011111".

This scheme can be optimised, but all depends on the wanted implementation. The proposed scheme is efficient to be integrated in hardware at both sender and receiver sides, as it does not need to look at the next bit to infer whether 1) it should put an additional "0" bit, and 2) the read "0" bit is a stuffing bit or not.

For reference, it might be nice to have a reference link towards "Forouzan", "Tanenbaum's book" and "Wikipedia HDLC".

[leonardomaccari]

To be sure I understood, I am not saying one should match exactly 01111110 (so indeed one should read the next bit to decide if stuffing a zero or not). I am reporting Forouzan that suggests one should match 011111: in your example when one generates "0111110111111" then, the reading should start from the added zero, and not from the following bit. I am not familiar with hardware implementations, so I can not tell if this also requires more state and resources (your 2) point). If you think this is the case, I suggest adding in the text some extended rationale, to answer the doubt that came natural to me ("why only 5 ones and not zero, followed by 5 ones?") .

For reference:

Behrouz A. Forouzan, Data Communications and Networking (i am referring to the 4th edition of which I have a pdf) "The strategy is called bit stuffing. In bit stuffing, if a 0 and five consecutive I bits are encountered, an extra 0 is added."

A. Tanenbaum, Computer Networks (this is copy-pasted from the 5th edition, but in the last edition I have in Italian it is consistent) "Framing can be also be done at the bit level, so frames can contain an arbitrary number of bits made up of units of any size. It was developed for the once very popular HDLC (High-level Data Link Control) protocol. Each frame begins and ends with a special bit pattern, 01111110 or 0x7E in hexadecimal. This pattern is a flag byte. When ever the sender’s data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream."

https://en.wikipedia.org/wiki/High-Level_Data_Link_Control#Synchronous_framing

"This bit-stuffing serves a second purpose, that of ensuring a sufficient number of signal transitions. On synchronous links, the data is NRZI encoded, so that a 0-bit is transmitted as a change in the signal on the line, and a 1-bit is sent as no change. Thus, each 0 bit provides an opportunity for a receiving modem to synchronize its clock via a phase-locked loop. If there are too many 1-bits in a row, the receiver can lose count. Bit-stuffing provides a minimum of one transition per six bit times during transmission of data, and one transition per seven bit times during transmission of a flag."

[qdeconinck]

I think both approaches work (i.e., "5 ones" vs. "1 zero and 5 ones"). The first approach is maybe a bit less optimised regarding the amount of data on the wire, but has the advantages to require a bit less implementation effort. The important part is that both the sender and the receiver needs to agree on when the stuffing zeros must be added.