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 updates that state when needed to keep track of new information. "State" information can be anything that we (the engineers) 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 digits that have been 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 diagram above:

• The state: This represents the information stored 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 engineers) need to decide what information those voltages represent, which (as mentioned above) can be anything we need it to represent.
• The next-state logic: This logic determines how the state should change. The main reason for saving state information is so that the behavior of the system can change based on that information, so the next-state logic depends on the state. Because that behavior is also almost always affected by inputs coming into the system, the next-state logic also depends on those inputs. In a digital hardware implementation, when a triggering event occurs (a clock edge, since we are using flip-flops), the new state is latched into the flip-flops. In other words, the next-state logic produces the state information that will become the state after the clock edge.
• The output logic: Because the state information is usually encoded in some way so that it can be more efficiently stored (i.e. using the fewest flip-flops), that state information needs to be decoded in order to produce useful outputs. The logic to do that translation is called the output logic.

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 describes how the outputs of the system behave based on the 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 (usually called a transition arc) 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 (like you) plan and communicate the intended behavior of the system. How that behavior gets implemented is a later step of the design process.

Theoretically, a state machine could have an infinite number of states, but of course that could not be physically implemented. Because of that, useful state machines have a finite number of states, and are thus sometimes specified as finite state machines (FSMs). This distinction is not necessary for most engineering designs.

State Diagram Example

Imagine you want a system that will assert an output named ready only after an input named prep has been active for two consecutive rising edges of a clock signal. This behavior cannot be implemented with combinational logic, but is perfect for some simple sequential logic.

The first step is to decide what information needs to be stored as state. Note that this step doesn't need to be done entirely up-front; it can be interleaved with deciding how states transition between each other. In this case though, there is a clear answer: the state machine needs to keep track of how many consecutive clock edges the input has been active for -- none, one, or two. There's no need to keep track of any more than that, because that information would not affect the behavior.

With the states decided, their transitions can be planned using a state diagram. Note that, because this state machine will be implemented with flip-flops storing the state, the state can only change on rising edges of the clock, so the transition arcs are effectively implementing the "rising edges of a clock signal" part of the required behavior.

Another feature has been added to this state diagram: a double-circle indicating the reset state; i.e., the state that should be entered when the state machine starts operating or gets reset. The physical mechanism to achieve that is, again, specific to the implementation. State diagrams only describe behavior, not implementation.

Implementation in Digital Hardware

Encoding the State

Once the states and their transitions have been defined, the first step towards implementation is to decide how to represent each state using digital logic values so that they can be stored in flip-flops.

For this example, there are three states:

• None: No active inputs yet (reset state)
• One: Input prep has been active for one clock cycle
• Two: Input prep has been active for two consecutive clock cycles

Because there are three states, the implementation requires at least two flip-flops (since two bits can represent up to four distinct states). There are multiple valid ways to assign binary codes to states, but the most common approach is to use simple binary counting:

State	Encoding (Q1 Q0)
None	00
One	01
Two	10

The remaining code 11 is unused and can either be treated as a "don't care" or redirected to a safe state during design to ensure predictable operation.

Logic Design

Now that each state has a unique binary encoding, the entire behavior of the system can be specified using only logic values. This is often done in a state transition table -- a table that shows the next state and output for each possible combination of the current state and inputs.

Current State (Q1 Q0)	Input prep	Next State (Q1⁺ Q0⁺)	Output ready
00 (None)	0	00 (None)	0
00 (None)	1	01 (One)	0
01 (One)	0	00 (None)	0
01 (One)	1	10 (Two)	0
10 (Two)	0	10 (Two)	1
10 (Two)	1	10 (Two)	1
11 (Unused)	0	XX (don't care)	X
11 (Unused)	1	XX (don't care)	X

Deriving the Logic

From the transition table, Boolean equations for the next-state and output logic can be derived using standard techniques such as Karnaugh maps or algebraic simplification. Expressions need to be derived for each of the next-state bits and for each of the output values.

Q1 and Q0 represent the current state bits, and Q1⁺, Q0⁺ the next state bits.

Next-state logic:

Q1⁺ = Q1 + Q0 * prep

Q0⁺ = /Q1 * /Q0 * prep

Output logic:

ready = Q1