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

The 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

Consider 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.

Filed under: misc hacks