Bit stuffing

There are a variety of different circumstances when an embedded system needs to deal with data that is presented as a stream of bits. This is not, in itself, a problem, but bits only come in two flavors – 0 and 1. This makes it difficult to manage the flow of data, as there is no easy way to determine the end of a packet or message, for example. When data traffic was controlled by hardware, this was addressed using a “long 1” or “long 0”, but this is rarely an option with modern systems. So, network protocol designers have developed techniques that involve adding extra bits in appropriate ways. This is commonly called “bit stuffing”. This article takes a look at those techniques and how they work.

Networking Protocols
This article is intended for developers who are not networking specialists. If you are an expert in this area, the ideas will be very familiar territory. With some years of working with embedded systems, you are likely to acquire a certain amount of knowledge 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 – WiFi, Bluetooth and USB, for example.

It was the study of the operation of the last of these, USB, a technique that was familiar in form, but unfamiliar in application, showed up: bit stuffing.

Stuffing Bits
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.

Bit stuffing is all about 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 occurin a row in the transmitted data. To make this work, the sendingsoftware/hardware will insert (stuff) an extra 0 after any sequence offive 1s. It can then send a sequence of six 1s specifically to indicatean end of data set. The receiver, on seeing a sequence of five 1s,checks the next bit. If it is 0, the bit is simply discarded; if it is1, then it notes that an end of data set has been flagged. Thistechnique is very flexible and can be adapted to various circumstances.It is broadly the same idea as using an “escape” character inbyte-oriented protocols. Here is an example:

 

Bit Stuffing and USB
Bitstuffing is used in USB, where it has a different purpose. USB is asynchronous protocol, which means that the sender and receiver must besomewhat synchronized to correctly recognize data on the bus. There isno separate clock line between the devices. The receiver usestransitions in the data stream to get in synch. Because of the way theencoding is implemented, a stream of 0s is not a problem, as there areplenty of transitions. However a stream of 1s would have no transitions,which might compromise the synchronization. This is fixed by thetransmitter stuffing a 0 after any sequence of six 1s. The receiver justdiscards any bit following a sequence of six 1s. This is a simplifieddescription, but should convey the idea.

The downsides of bitstuffing 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 datatransmission rate is not predictable, as it is slightly data dependent.

USB Data Transfer and Data Scrambling
Asan aside, USB is a very good example of a communications protocol thatis a stream of bits and it has some interesting characteristics beyondbit stuffing.

For a software engineer, it is easy to imagine astream of bits as just a series of ones and zeros and, logically, thatis just what it is. However, the world of hardware is never quite sosimple. If you tried to monitor a USB transmission by looking at thevoltage on the line, you might expect to be able to see each of the onesand zeros. However, it is not that easy, as USB uses a non-return tozero inverted (NRZI) mechanism; a logic zero is a voltage change; alogic one is no change in voltage (which explains why bit stuffing isused, as mentioned earlier). Following the communication on anoscilloscope screen is very challenging.

Interestingly, USB 3.0also messes with data streams in another way. It has a data scramblingmechanism, which eliminates repetitive patterns in data, which wouldotherwise cause radio interference that would compromise FCCrequirements. That, however, is another story entirely.

Colin Walls hasover thirty years experience in the electronics industry, largelydedicated to embedded software. A frequent presenter at conferences andseminars and author of numerous technical articles and two books onembedded software, Colin is an embedded software technologist withMentor Embedded [the Mentor Graphics Embedded Software Division], and isbased in the UK. His regular blog is located at: http://blogs.mentor.com/colinwalls. He may be reached by email at colin_walls@mentor.com


Join over 2,000 technical professionals and embedded systems hardware, software, and firmware developers at ESC BostonMay 6-7, 2015, and learn about the latest techniques and tips forreducing time, cost, and complexity in the development process.

Passes for the ESC Boston 2015 Technical Conferenceare available at the conference's official site, with discountedadvance pricing until May 1, 2015. Make sure to follow updates about ESCBoston's other talks, programs, and announcements via the Destination ESC blog on Embedded.com and social media accounts Twitter, Facebook, LinkedIn, and Google+.

The Embedded Systems Conference, EE Times, and Embedded.com are owned by UBM Canon.

4 thoughts on “Bit stuffing

  1. “Changing the subject somewhat:nnhttp://en.wikipedia.org/wiki/Consistent_Overhead_Byte_StuffingnnWorks well for binary messages over byte oriented links, also nice for writing records to flash such that each record can “stand on its own”.n”

    Log in to Reply
  2. “Nice tutorial on this topic Colin. I cut my teeth on Async protocols, then on Sync protocols using ASCII characters to delimit messages. The first time I was in a course on Bit Oriented Protocols and the instructor asked “What if we want to send ANY se

    Log in to Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.