State Machines Coding Styles

Last month we began examining one of the most common hardware design constructs–the state machine. State machines are so common that there are tools devoted to creating them by drawing circles and arts. There are simulators that will recognize your state machine and animate it to help you debug it. There are even synthesis tools that will add error correcting logic to your state machine so that it can recover from the single event upsets that can happen at high altitude or in electrically noisy environments.

You can take advantage of these tools by programming state machines using a commonly accepted coding style. Last month we began our discussion of this coding style when we saw how to create named states and a designated state register. This month we’ll examine various coding styles that we can use to create the next-state and output generating logic.

We are venturing into the world of combinatorial coding style, a subject that is so controversial that adult engineers have nearly come to blows when strong drinks are present at a design review meeting. This article examines three basic coding styles you can use to implement a state machine. We will use this simple state machine as our example: the life of a dog.

The dog leads a simple life. By default he sleeps, but if you feed him he’s happy and then starts eating. After he’s done eating he goes back to being happy unless he gets tired, you feed him again, or another dog walks in the street. If there is another dog, he starts barking, if you feed him he eats, and if he’s tired he goes back to sleep.

The dog state machine has three inputs: tired, food, and other_dog.

The dog state machine has two outputs: mouth and tail.

The mouth operates when the dog is barking or eating, the tail operates when the dog is happy (product marketing might argue that the tail could also operate when eating, but we’re not implementing that approach). We’re going to code up our dog several ways.

We’re going to see that HDL gives you control over how your final code implements a state machine. There are two steps to the process. First we’ll choose a state machine architecture, then we’ll code it up. The key is to realize that there are many possible state machine architectures and they all deliver different benefits and challenges.

All state machine architectures have three or four pieces:

1. Combinatorial logic to determine the next state.
2. Combinatorial logic to determine the output based on the state.
3. A state register.
4. Clocked output signals (optional).

The simplest way to implement a state machine is to create a process for the first three pieces:

We have a cloud of logic implementing the next state based upon the inputs and current state, a current state register, and a cloud of logic implementing the output.

Here is the code that implements this simple state machine:

You can code this kind of state machine with three separate processes. This has the advantage of clarity. Each process does one thing. Notice that the output logic and the next-state logic have different sensitivity lists. The output is only sensitive to the current state, while the next-state logic is sensitive to the state and the input signals. This is the definition of a Moore state machine.

We can also create a Mealy state machine if the output logic is dependent upon the inputs as well as the state, as we see here:

Let’s use a Mealy state machine to create a dog who barks whenever there is another dog outside, regardless of our dog’s current state.

The rest of the state machine code is the same as in Figure 2. The only difference is that we set the mouth signal to be equal to the other_dog signal before checking the state. Now another dog will get the mouth going regardless of what our dog is doing (this is a fairly accurate simulation of my dog).

Now that we’ve seen how we can separate the next-state logic from the output logic, I have to tell you that I don’t like this coding style because it uses two case statements to respond to the same information. This means that if I add a state to my state machine, I have to add it to both the next-state and the output case statements. I have a hard enough time getting things right once, I hate having to get things right twice. We can get around the problem with this architecture:

Here is the code for this approach:

Now I have one process that is sensitive to the state and the input signals. The case statement is a little more complex because I need to describe the output’s response to the input signals in each state, and once again I can wind up duplicating conditions if different states respond to the input differently.

That said, I have one more pet peeve that we may want to address. If the outputs of this state machine directly drive the outputs of a module or component, then I have a problem with unclocked outputs. Unclocked outputs create design problems:

1. Synthesis tools cannot do timing analysis across module boundaries. This means that if you have 10 ns between clocks, then you can run into trouble if generating the combinatorial outputs from one block that takes 6 ns while processing the combinatorial inputs of another block takes 5 ns. Both blocks think they are meeting timing, but together they are not.
2. You can get glitches on the output signals if they are settling after you’ve changed your state.
3. Your synthesis tool will miss optimizing opportunities because it cannot see a complete combinatorial circuit that crosses module boundaries.

You can avoid all these problems by clocking your output signals. This creates a circuit where your output signals appear one clock cycle after the state that generates them, but you avoid the problems of unclocked outputs. This design looks like this:

And here is the code:

Now we have one process that implements the entire state machine. This process is sensitive to the clock and the reset. On every clock edge, the state machine outputs the signals associated with the current state and moves the state machine to the next state. Notice that mouth and tail are registers now, so they get set on line 51 along with the current state. This state machine will deliver clean edges on every clock.

Summary

We’ve now examined several ways to code a state machine. Design tools, simulators, and synthesis tools will all recognize and generate state machines that you code using any of these techniques. This, of course, raises the question, “Which is best?”

The answer is, “Whichever best matches your application.” If you have a complex output circuit, you may choose to separate it from the next-state logic. You may find that you’d rather duplicate the state case statement rather than duplicate the logic that responds to inputs. You may not be able to afford the clock cycle it takes to create clocked outputs. You may have coding styles at work that limit your approach.

There is no single optimum style. Instead of slavishly using one style because it was the first one we learned, the best approach is to understand all our options and make a conscious decision.