Channels ▼

Al Williams

Dr. Dobb's Bloggers

Altered States

June 03, 2011

Last time I discussed state machines and how they could make embedded systems — at least some of them — much simpler to create and maintain. Of course, you could argue that nearly all programs (and most CPUs) are already state machines. But I am thinking more about representing them as state machines to start with, not describing the behavior of a bunch of ad hoc statements with a state machine after the fact.

There are plenty of tools around to help you. The popular Boost library, for example, has a state machine library (statechart). There are other tools that are more flexible with languages (such as Ragel). Look for more on some of those in the future. It is reasonably simple to roll your own state machines too, depending on how generic you want to make the engine. A switch statement and a state variable can do the trick.

I have a small library I wrote that I often pull out when I need something simple and I'm using C++. You could adapt the same ideas to C or Java, of course. To use it, you simply include state.h, which gives you a base class called statemachinebase. You can then derive a class to handle your special requirements for input and output. You can also add your states and your state transitions to the base class' tables easily.

In my previous blog, I talked about a traffic light. The state diagram is below, so you don't have to go find it in the last blog.

[Click image to view at full size]

Using the library to build the traffic light requires just a few items in the derived class:

  • Custom state IDs (not strictly necessary, but makes it nice to read)
  • A way to make timer events look like input signals (I used SIGALRM, which is common on UNIX, Linux, etc.)
  • A definition for the state machine outputs
  • A set of state table entries
  • A set of state transition table entries

The state IDs make the code readable and that’s easy:

  // custom states -- use one hot encoding
  enum 
    {
      REDGREEN=1,  // default state
      REDYELLOW=2,
      GREENRED=4,
      YELLOWRED=8
    };

Recall from my last post that a "one hot encoding" uses a single bit for each state. This is clearly using that scheme. Just as an aside, many hardware state machines modify the one hot strategy so that the initial state is 0. This is easy to detect and is the default value for the state variable, so it saves hardware that would only initialize the variable. Plus it gives you one extra possible state (that is, a byte can hold 9 one hot states, if 0 is a legal state). The traffic light is a "pure" one hot representation.

The timer system is just a few functions that set up a UNIX-style signal to fire every second and maintains a countdown timer. When the timer expires, the state machine sees a "1" input. Of course, the signals are going to occur at exactly one second, but for a simple traffic light, no would notice a few seconds of slack either way. Naturally, in a real system you might have other kinds of events that require a more precise timer, but you can do anything your hardware will support. The library just cares that some input is readable for all the events that cause a transition. Additionally, when a state becomes active, the timing is automatically set. A short time delay occurs when a yellow light is active, and a longer time passes for a green light.

By default the library uses integers for input and output. The traffic light has to modify the input, but it uses the output integer as-is, assuming that the low byte of the output represents 6 different outputs. The byte has the pattern:

	X  R1  Y1  G1  X  R2 Y2 G2

Where X is an unused bit. The R, Y, and G bits are red, yellow, and green. One pair of lights (e.g., North/South) is numbered with a 1 and the other pair is numbered with a 2. Of course, real traffic lights that use incandescent bulbs preheat filaments, but I ignored that here. Besides, I don't think I have to preheat LEDs, so let's stick with that.

If you look at the state diagram, there are 4 states. I am using the Moore model, so each state has an output associated with it. Here's the code that sets up the states:

    registerState(REDGREEN,0x77,0x41);
    registerState(REDYELLOW,0x77,0x42);
    registerState(GREENRED,0x77,0x14);
    registerState(YELLOWRED,0x77,0x24);

The 0x77 is the output mask. Only the bits in the mask will be modified. The second number is the output colors as described above.

Finally, you need the state transitions:

    registerTest(~0,REDGREEN,TIMEREXP,TIMEREXP,REDYELLOW);
    registerTest(~0,REDYELLOW,TIMEREXP,TIMEREXP,GREENRED);
    registerTest(~0,GREENRED,TIMEREXP,TIMEREXP,YELLOWRED);
    registerTest(~0,YELLOWRED,TIMEREXP,TIMEREXP,REDGREEN);

That's it. The ~0 in the transition table just makes a mask with all 1 bits. The traffic light uses one hot encoding, so you can match all the bits safely. The only thing left is to write a main function that creates the traffic light object and then calls the Process method (provided by the base class) repeatedly.

I glossed over some details, of course. You can find a slightly improved version of the entire program here. It shows how easy it is to modify a table-driven state machine. The entire program assumes that there are two buttons pedestrians can use to request the light to change their way. This requires just a little code in the input function to represent the buttons as 2 and 4 (recall that 1 is the time expiration).

To take advantage of the buttons, the state transition table changes:

    registerTest(~0,REDGREEN,TIMEREXP,TIMEREXP,REDYELLOW);
    registerTest(~0,REDGREEN,BUTTON1,BUTTON1,REDYELLOW);  // new
    registerTest(~0,REDYELLOW,TIMEREXP,TIMEREXP,GREENRED);
    registerTest(~0,GREENRED,TIMEREXP,TIMEREXP,YELLOWRED);
    registerTest(~0,GREENRED,BUTTON2,BUTTON2,YELLOWRED);  // new
    registerTest(~0,YELLOWRED,TIMEREXP,TIMEREXP,REDGREEN);

Granted, this traffic light is pretty generous to pedestrians because it immediately forces the green side to yellow when you press the button, but you can easily modify it to, say, shorten the current cycle instead of just ending it. That's the point. It is easy to change the behavior by adding new states and transitions.

The entire traffic.cpp and traffic.h files might look a bit bloated at first. But if you examine the code carefully, you'll see that most of it is simulating the button pushes and doing easy-to-read printing of states and time delays so you can see what's going on. A real traffic light would actually be simpler!

One day soon, I'll return to state machine tools for embedded systems. For now, why not leave a comment and tell us if you use any state machine tools for design or implementation? Are they homegrown or something off the shelf?

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video