State of the Machine

It is a shame that most books that talk about state machines take a very abstruse approach to the topic. FPGA designers use state machines to reason about digital design, but I don’t think many programmers think of using formal (and maybe generic) state machines as often as they should. Of course, we often write what amounts to a state machine without thinking about it.

For example, consider a traffic light. The lights are outputs, and red, yellow, and green are the states. Some even have buttons for pedestrians to cross (I don’t know why Brits call those pelican crossings). How would you write firmware for a traffic light?

It would be easy enough to write subroutines to set the output and do the delay timing:

while (1) {
  greenred() ;  // greem on N/S and red on E/W
  pause(DELAY1) ; 
  yellowred() ;  // yellow on N/S and red on E/W
   ***a***pause(DELAY2) ; 
  redgreen() ;   // red on N/S and green on E/W
  pause(DELAY1) ; 
  redyellow() ;  // red on N/S and yellow on E/W
  pause(DELAY2) ; 

This is still a state machine, albeit a handcrafted one. But you could also express it as a generic state table. For example:

State Trigger Action North/South East/West
0 (startup) pause for DELAY1 Green Red
0 (timer expires) set state 1
pause for DELAY2
Yellow Red
1 (timer expires) set state 2
pause for DELAY1
Red Green
2 (timer expires) set state 3
pause for DELAY2
Red Yellow
3 (timer expires) set state 0
pause for DELAY1
Green Red

Notice that the first state table entry is nearly the same as the last. The difference is that the first one is the initial state and sets everything up. The last line handles the normal changing of the light (and, in fact, sets the state back to 0).

This machine could have been simplified if there were two tables: one table handling the transitions and another that mapped outputs to states. For example:

State North/South East/West
0 Green Red
1 Yellow Red
2 Red Green
3 Red Yellow
Current State Trigger Next State/Timer
0 (timer expires) 1/DELAY1
1 (timer expires) 2/DELAY2
2 (timer expires) 3/DELAY1
3 (timer expires) 0/DELAY1

If you’ve done hardware state machines before, you might recognize this as the difference between a Mealy machine and a Moore machine. A Mealy machine is a state machine that uses its inputs as part of how it forms its outputs. So the transition between states is what sets the outputs. In a Moore machine, each state has an output associated with it (just like the last two tables).

There are advantages and disadvantages to both methods (for example, hardware implementations of Mealy machines change their outputs asynchronously, which is usually bad, but also often require fewer states than a Moore machine, which is good). In software, the difference is a little harder to see, but if you compute the outputs based on the transition between states, you are using the Mealy method. If you instead compute a new state and then, based on that state, determine the output, you have built a Moore machine.

Regardless of the machine type, you usually see state diagrams drawn with bubbles like this:

[Click image to view at full size]

State of the Machine

The other design choice that mirrors hardware design is how to represent the state. On the face of it, that seems like a silly question. State 0 is 0, State 1 is 1, and State 10 is 10, right? Perhaps not. That is certainly one scheme you can use, but there is a design trade involved.

If you use sequential state numbers, you can pack a lot of states into a small variable (256 states in one byte). That’s a good thing, but it becomes hard to manipulate them in certain ways. For example, suppose you wanted a state table that had an entry for “the current state is state 0 or 7.” Your state table would have to take a list of current states, which is both wasteful (especially in the common case) and drives up code complexity.

On the other hand, you could use what hardware designers call “one hot” encoding. In this scheme only 1 bit of the state variable can be set at one time and it represents the state. So 1 is state 0, 2 is state 1, 4 is state 2 and so on. This makes it very easy to figure out which state is active and also makes it easy to describe things like “current state is 0 or 7.” The downside, of course, is that now a byte can represent 8 states instead of 256!

So far, the traffic light is pretty simple because the only input is a timer. Next time, I’ll show you how it would look with some physical inputs, and present some code and tools for handling generic state machines. Maybe your next programming job can be simply filling in a state chart!