Stuffing bits

I am not a networking specialist. If you are an expert in this area, this posting will be teaching a grandmother to suck eggs (strange expression – I wonder what it actually means). Obviously, over years of working with embedded systems, I have learned quite a lot about protocols, so learning about a new one is not starting from scratch. For many, networking begins and ends with TCP/IP. However, there are lots of other Internet protocols – FTP, UDP and HTTP, for example. There are also other kinds of connectivity that may or may not be thought of as networking – Wi-Fi, Bluetooth and USB, for example.

It was while studying the operation of the last of these, USB, that I came across a technique that was familiar in form, but unfamiliar in application: bit stuffing …

The term “bit stuffing” broadly refers to a technique whereby extra bits are added to a data stream, which do not themselves carry any information, but either assist in management of the communications or deal with other issues.

The use of bit stuffing, with which I was familiar, was to do with protocol management. Imagine you have a stream of binary data and you periodically want to include a marker to say that a data set has finished. Obviously, you can use a particular bit sequence, but how do you recognize it when any sequence of bits might occur within the data stream? This is where bit stuffing comes in.

For example, we can define a rule that no more than five 1s can occur in a row in the transmitted data. To make this work, the sending software will insert (stuff) an extra 0 after any sequence of five 1s. It can then send a sequence of six 1s specifically to indicate an end of data set. The receiving software, on seeing a sequence of five 1s, checks the next bit. If it is 0, the bit is simply discarded; if it is 1, then it notes that an end of data set has been flagged. This technique is very flexible and can be adapted to various circumstances. It is broadly the same idea as using an “escape” character in byte-oriented protocols.

I was interested to see how and why bit stuffing is used in USB, where it has a different purpose. USB is a synchronous protocol, which means that the sender and receiver must be somewhat synchronized to correctly recognize data on the bus. There is no separate clock line between the devices. The receiver uses transitions in the data stream to get in synch. Because of the way the encoding is implemented, a stream of 0s is not a problem, as there are plenty of transitions. However, a stream of 1s would have no transitions, which might compromise the synchronization. This is fixed by the transmitter stuffing a 0 after any sequence of six 1s. The receiver just discards any bit following a sequence of six 1s. This is a simplified description, but I hope that it conveys the idea.

The downsides of bit stuffing are that it introduces an overhead, but this is minimal (0.8% on random data in USB, for example), and it means that the overall data transmission rate is not predictable, as it is (slightly) data dependent.

Interestingly, USB 3.0 also messes with data streams in another way. It has a data scrambling mechanism, which eliminates repetitive patterns in data, which would otherwise cause radio interference that would compromise FCC requirements. But that another story entirely …

This entry was posted on Monday, June 12th, 2017 at 9:05 am. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.