Becoming a State Machine Design Mastermind

Imagine a robot with an all-around bump sensor. The response to the bump sensor activating depends on the previous state of the robot. If it had been going forward, a bump will send it backwards and vice versa. This robot exhibits behavior that is easy to model as a state machine. That is, the outputs of the machine (motor drive) depend not only on the inputs (the bump sensor) but also on the current state of the machine (going forward or backward).

As state machines go, that’s not an especially complicated one. Many state machines have lots of states with complex conditions. For example, consider a phone switchboard. The reaction to a phone going off hook depends on the state of the line. If the state is ringing, picking up the phone makes a connection. If the state is idle, the phone gets a dial tone. The switchboard also has to have states for timeouts, connection failures, three way calling, and more.

If you master state machines your design and debug cycles will both move along faster. Part of this is understanding and part is knowing about the tools you can choose to use. I’ll cover both below.

Software

You can implement a state machine in software or hardware. A software version of the robot state machine might look like this:

state = FORWARD;
while (true) // do forever
 {
 if (bump)
    if (state==FORWARD) state=REVERSE; else state=FORWARD;
 if (state==FORWARD) move_forward(); else move_backward();
 }

Another way to get the same effect is to write a program that reads the data from a table that matches input and current state to find the next state. For example:

table[0].current_state=FORWARD;
table[0].bump_input=TRUE;
table[0].next_state=REVERSE;
table[1].current_state=REVERSE;
table[1].bump_input=TRUE;
table[1].next_state=FORWARD;

Flip Flop Hardware

Hardware implementations use flip flops and there are at least two different ways to construct a state machine. Let’s make our robot a little smarter. Suppose you want the robot to go slowly each time it changes direction, but if it makes it through three loops (or clock cycles, if you prefer) without hitting something, the robot should speed up. There are several ways you could do this. It makes sense to use a counter, but that’s not the only way to set it up. Consider the following states:

  • Forward Slow (1)
  • Forward Slow (2)
  • Forward Slow (3)
  • Reverse Slow (1)
  • Reverse Slow (2)
  • Reverse Slow (3)
  • Forward
  • Reverse

state-machine-diagram-croppedThe state diagram above is the customary way to think about and document state machines. I’ll tell you about the tool I used to create it shortly. Every state machine has a starting state (the one with the double ring). The circles are states and the arrows represent things that make a state transition to another state.

State Representation

In software, it makes sense to represent each state with a number (perhaps with a #define to make it easier to read) or an enumerated value. For a hardware design, you need to select a way to represent each state. The most obvious choice is to simply use a number stored in registers or flip flops. This is compact, but requires decoding each state using combinatorial logic (AND, OR, and INVERTER gates). If you aren’t careful, you may also trigger spurious states when multiple bits in the state representation change at one time. There’s no reason, of course, the states have to use sequential numbers, so you might select a gray code (where only one bit changes per state transition).

Even more extreme–but very common–is the one hot encoding method (PDF). Here, you use one flip flop per state so that only one flip flop is set at any given time. This requires an initialization to set the first state or special logic to allow state zero to be the starting state. However, it is fast and reduces decoding logic, so it is often used.

Moore vs Mealy

There are two common strategies for implementing hardware state machines: Moore machines and Mealy machines. A Moore machine creates outputs using only the state information. That means any unique set of outputs requires a separate state. For a one hot machine, our hypothetical robot needs 8 flip flops: two sets of 3 for the slow states and two more for the normal states.

In a Moore machine, the outputs (let’s say forward, reverse, and slow) will originate from some logic gates connected to the state machine output (an OR gate, for example, would generate the forward signal from any of the forward states).

The alternative is a Mealy machine. With a Mealy machine, the outputs can also depend on the inputs. This requires careful design because it can create output glitches as thing change. However, it does usually require fewer states since similar outputs are grouped.

In the case of our robot, imagine the drive system provides you with a number of steps taken at a given speed and direction. You receive 8 bits of input. The bits start at zero each time you change the motor direction or speed and counts up until it reaches the maximum count. You decide to stay in slow mode until the count reaches 100 in slow mode. Further, assume you have two outputs for each direction: forward slow, forward, reverse slow, and reverse.

A Moore machine would require hundreds of states if you did a naive implementation. With a Mealy machine, the outputs depend not only on the state, but the value of the drive counter. Of course, if the counter was part of the state machine, that would make it a Moore machine. In fact, you can always convert a Moore machine to a Mealy machine and vice versa.

The choice is usually pretty clear. If you are concerned about speed and the size of state representation, you want a Mealy machine. If you want no chance of output glitches, use a Moore machine.

Optimization

In addition to selecting an encoding and a machine style, there are opportunities to minimize state machines by combining equivalent states, for example. This sounds easy, but it can get complicated rather quickly.

Luckily, there are automated tools (including the ones you use for FPGA development) that will minimize state machines. There are cases, though, where the smallest possible state machine leads to unwanted complexity in output decoding or other related logic.

A Practical Example

parity-stateConsider a synchronous serial data stream (that is, a serial data stream with a clock). The data should have odd parity, meaning that if the data stream has an odd number of 1 bits, the parity bit is 0, otherwise the parity bit is 1. The count of 1 bits in the data stream along with the parity bit will always add up to an odd number. From a state machine perspective, this is fairly simple as shown in this diagram.

The reset state (thick blue line) assumes there are no one bits, or an even number, so the output is a 1 (so that there is an odd number). As long as zero bits arrive, the state remains unchanged. When a 1 bit appears, the state changes to odd and the output goes to zero. The machine stays in that state until it receives another 1 bit.

How would you implement something like this? Consider this state table:

Current State      Input       Next State
0                    0         0
0                    1         1
1                    0         1
1                    1         0

Does that look familiar? It should. This is exactly the truth table for an XOR gate. The output bits make it clear we can use one state variable (0=odd, 1=even). So here’s a simple implementation in logic:

Or if you prefer Verilog:

module parity(input reset, input clk, input data, output par);
 reg state;
 always @(posedge clk)
 begin
 if (reset) state<=1'b1;
 else state<=state^data;
 end
endmodule;

Note the ^ character is Verilog (and C) for XOR.

Automating State Machine Development

There’s nothing to stop you from creating your own state machines in Verilog or VHDL, just like the parity bit example. However, there are some automation tools (ranging from free open source to very expensive) that let you describe the state machine as a table or state diagram and many will even generate the code for you.

One tool is Fizzim, which is open source and easy to use. It makes good looking diagrams (like the one above), so even if you don’t want to generate code, you may still want to check it out. Fizzim uses Java for the GUI, so it will run almost anywhere. It uses Perl as a backend code generator and, again, that’s pretty portable.

You don’t actually have to use the GUI, if you want to stick with manipulating text, but the GUI is handy. There are three object types: the state machine, states, and transitions. Each element can have attributes that describe different things for the back end Perl program.

The Fizzim tutorial is well worth reading even if you may not want to use Fizzim. In the course of showing the tool, they also cover practical nuances of state encoding, output generation, and coding state machines in Verilog. The latest version can also output VHDL.

Software Libraries

If you prefer to sling your state machines in software, there are a lot of options (if you don’t want to roll your own). The Boost libraries that are popular for C++ programmers are one option. There are even options for the Arduino. Java programmers have options, too.

There’s lots of other possibilities. If you like Web development, there’s a framework in JavaScript. There’s even a W3C draft for an XML standard to specify and execute state machines. Another tool of interest in the Ragel compiler, which can generate target code in a variety of languages.

Homework

Once you get used to thinking about state machines, you’ll see them everywhere. Robots, traffic lights, burglar alarms, and thermostats could use a state machine implementation. You can go overboard, of course. (The light switch has two states: on and off.) However, for moderately to very complex systems, state machines can be the way to go.

For simple machines, you may want to hack out your own custom implementation. However, if you can use existing software or hardware implementation tools, you’ll probably have a better experience.

21 thoughts on “Becoming a State Machine Design Mastermind

  1. State diagrams, with big round states and pointy transitions, are error prone, difficult to understand and code. State tables are the way to go, and especially if involving stakeholders from other professions – takes them 2-seconds to learn.

    1. I would disagree with you on this in many cases, especially as the number of states goes up. The state diagrams can make it clear what the transitions are, and, if the states are well named, the operation can be understood at several levels without chasing around a state table, especially when communicating out of specialty.

      Poorly layed out state diagrams, especially if the states and transitions are not appropriately named, are torturous, like most flowcharts are. I bring up flowcharts because, despite the current attitude that the concept is outdated, and that the place they are most often seen anymore is where the model has been co-opted by the management knuckleheads and education gurus in an attempt to lend scientific and mathematical credibility to their gourd rattling and so-called concept maps, they are a fantastic tool when laying out processes with well defined decision points and sequential principal flows.

      1. Okay, I’m up for a bit of a bonfire: Technically we’re both wrong, but ‘Spaghetti & Meatballs’ has been out for longer than state-transition tables. State diagrams fail to capture vital semantic detail, such as transition (guard) condition order evaluation, whilst state tables afford far, far greater complexity in all aspects, whilst remaining orderly and concise. I would have liked to contribute to your erudition, though it appears the mod is equally as opinionated, and has afforded me no opportunity to link, even to my own instructional material.

    2. For extremely simple state machines that never need changing, perhaps. Table based approaches have trouble with scalability: the number of table entries is the product of the number of states and the number of events. If you throw in ‘pseudo-events’ like entrance and exit, it gets pretty big, pretty fast. Adding a state or an event is a hassle. In C, my favorite way of representing a state machine is with state handler functions, taking an event pointer as an argument and returning a function pointer to the function representing the next state. It is readable, compact, fast and easy to add new states and events.
      As to diagrams, you’re right – if you code them by hand. There are some decent tools out there for taking a UML state chart and producing code. These are a must if you get complicated or hierarchical state machines. I like QM, in particular.

  2. Something that I note the Fizzim tool does that makes a good style recommendation is breaking up combinational logic and the sequential statement as, when your statemachine gets particularly complex, it can be very easy to introduce latches you weren’t expecting (putting the register as an item on its own ensures you don’t – your combinatorial logic may still be borked but at least you can see it a bit more in the simulations).

    And even the simplest statemachine can become confusing when you interlink the interactions of a dozen or so together (an ASIC is nothing more than a massive collection of them :-)
    ..then the problem becomes more of a documentation one of defining the interfaces fully (or play spot the holes in specs)


  3. {
    if (bump)
    if (state==FORWARD) state=REVERSE; else state=FORWARD;
    if (state==FORWARD) move_forward(); else move_backward();
    }

    Question: How many times the function “move_forward()” will be called in the first 30 minutes of run?

    1. It’s kind of convoluted but the code is actually correct. He takes into account that the value of state is changed in the first if statement by reversing the impact of the if and else clause in the second one. So if it is going forward and there is a bump, state will be forward at the first if statement, causing it to test true, but then gets changed to reverse before the second test which will cause it to test false so the else clause is used telling it to move backward. On the next bump the first clause will test false putting it back into the forward state making the second if statement test true calling the move forward function. For clarity they should really be combined under one if statement. My initial reaction was that it was wrong but after tracing the logic found it to be correct but not clear.

        1. The WordPress editor eats some of my indents. I’ll try to reclean it here shortly.

          By the way, the original code I pulled this from goes with an RC servo driven robot I use with students some time. The move_forward() and related calls do 25 cycles of 20mS servo drive so they are about 500mS each. This was meant more as a conceptual exemplar here, not an absolutely practical example, so I didn’t dive into those details.

          1. The concern came from the fact that the bump switch does not instantly became off when the robot goes backwards, and the speed of that while loop could be very fast.

            As an effect, the robot bumps into a wall, then the logic start to alternate the state and the calls to move_forward() and move_backwards() at the speed of the while loop, which is very, very high.

            As a result, the robot will continuously switch the polarity for the motors, but the inertia will pin it near the wall.

  4. We use the commercial software called EasyCode at work to do some pretty complex state-machine designs (www.easycode.de). I’ve used that tool for a long long time for most of my embedded software developments (mostly in C) since i’ve learned coding in the good old days. It’s not a perfect piece of software, but the graphical interpretation helps me a lot to keep the code structured and organized in large projects. The best thing tho is that it can generate the basic source code for extremely complex state machines out of the state-event diagrams. As added bonus, we can use the graphics directly as code documentation (we have to hand in full source documentaion to get our products certified). So far i’ve never seen any open source solution that can do something similar. For now tho, we are happily paying the license fees for the benefits we get.

  5. Also have a look at ThingML (https://github.com/SINTEF-9012/ThingML). It provides a textual syntax for implementing State Machines. Visual representations can be automatically exported, and it possible to compile ThingML programs to C/Arduino/JavaScript/Java programs that are ready to run, and it should not be too difficult to write a compiler targeting VHDL or similar language to target FPGAs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s