.

.

.

.

.

This content is currently under heavy revision.

.

.

.

.

.

.

State Machines

Now that we have the ability to hold information within our digital electronic circuits (using flip-flops), how do we use that capability in useful ways?

One of the most common approaches to designing systems that keep track of information is to use the concept of a state machine. A state machine is a system that keeps track of some kind of "state" information, and can update the state based when needed to keep track of new information. "State" information can be anything we (the human) choose it to be. It could be the inning number and number of runs in a baseball game. It could be how many times an earthquake has occurred in the previous five years. It could be the previous digits entered on a handheld calculator.

The general structure of a state machine can be described like this:

It is very important to realize that there is nothing about state machines that is specific to digital electronic hardware. In fact, the concept gets used far more in software than in hardware, and isn't even limited to technical fields. However, because this text is about digital electronic hardware, that is the context in which we will discuss state machines.

There are three main pieces of the digram above:

• The state: This represents the stored information within the system at any given moment. In digital hardware, state information is typically stored in flip-flops, which retain their values until explicitly updated. Since a flip-flop can only hold a single bit of information, multiple flip-flops are usually needed to hold more complicated state information. And since flip-flops only hold high or low voltage, we (the humans) need to decide what those voltages represent.
• The next-state logic: This logic determines how the current state should change based on inputs and also on the current state. It uses combinational logic to define the rules that dictate how states transition from one to another. When a triggering event (a clock edge, since we are using flip-flops) occurs, the next state is latched into the flip-flops to become the new state.
• The output logic: This logic defines the outputs of the state machine based on the current state (and sometimes also directly on external inputs). The outputs represent the useful actions or information produced by the state machine.

State Diagrams

State machines are much more complicated than combinational logic, and their behavior cannot be described by Boolean expressions or truth tables. To plan the behavior of a state machine, a graphical representation of that behavior called a state diagram is often used. A state diagram shows how the state machine transitions from one state to another based on inputs, and how outputs are defined by each state.

There are many styles of state diagrams, but the simplest is typically called a "classic" state diagram. In this style of state diagram, states are represented by circles labeled with meaningful names (to help us and others understand what the state represents) and contain output values associated with the state. Arrows connecting the circles (the states) represent transitions between states, showing the possible paths the state machine can take from one state to another. Each arrow is labeled with the input conditions under which that transition should occur.

Keep in mind that state diagrams are a design tool. They help designers plan and communicate the intended behavior of the system. How that behavior gets implemented is a later step of the design process.