The Design of State Machines

State tables and state diagrams

18383

Introduction

The most difficult task in designing sequential circuits occurs at the very start of the design; in determining what characteristics of a given problem require sequential operations, and more particularly, what behaviors must be represented by a unique state. A poor choice of states coupled with a poor understanding of the problem can make a design lengthy, difficult, and error-prone. With better understanding and a better choice of states, the same problem might well be trivial. Whereas it is relatively straight-forward to describe sequential circuit structure and define applicable engineering design methods, it is relatively challenging to find analytical methods capable of matching design problem requirements to eventual machine states. Restated, we can effectively present how to design, but we will present what to design through examples and guided design problems. And so this initial and most important design task, identifying behaviors in the solution-space to a problem that require unique states, will be presented over time through examples, and you must learn this skill through experience (some general guidelines will also be presented later). In general, the first step in designing a new state machine is to identify all behaviors that might need states, and all branching dependencies between states. Then, as an understanding of the problem and solution evolve, original choices can be rethought, challenged, and improved.

State Table

One method of capturing the behavioral requirements of a state machine is through the creation of a state table. A state table is nothing more than a truth table that specifies the requirements for the next-state logic, with inputs coming from the state register and from outside the circuit. The state table lists all required states, and all possible next states that might follow a given present state.

Figure 1. Describe a state machine using state table.
Figure 1. Describe a state machine using state table.

State-to-state transitions can be directed by input signals, so the table must list any input signals required to cause a given transition. Figure 1 above shows an expanded model of a state machine, and illustrates how the state/truth table can be used to find the next-state logic. In the state table, the first four rows all show ‘000’ for the state variables. This is because there are two inputs, and a next state must be specified for all possible combinations of inputs. From the state table, you can deduce that if the machine is in state ‘000’ and the inputs are both ‘0’, then the next state will be ‘001’; if the machine is in state ‘000’ and the inputs are ‘0’ and ‘1’, then the next state will be ‘011’; and so on.

The output truth table shows how the state variables and any Mealy inputs are combined to form outputs. In this example, only one of the two inputs (I1) is used by the output logic circuit. The state and output tables can be combined into a single truth table (also called a state table) to specify all combinational logic requirements (i.e., both next-state and output requirements) in a single table.

The next-state truth table requires at maximum N input columns for each of N state variables, and M input columns for each of M circuit inputs. It is not required that all possible states nor all possible combinations of inputs be used; hence, the next-state truth table need not have all 2(N+M) 2^{(N+M)} \space rows present. Just which rows are required in the truth table depends on which of the 2N2^N possible states are used in a given sequential circuit, as well as which inputs are used in each state (again, choosing states and branching conditions is the more difficult engineering challenge, and several examples in this and future lab exercises will help illustrate the process). For each row of the truth table, the next-state output values are assigned according to the desired next state. The use of DFFs in the state register is assumed, so a ‘1’ in an output column will cause the corresponding DFF to transition to a ‘1’ on the next clock edge.

Although truth tables (or state tables) can always be used to specify next-state and output logic, they suffer from a significant drawback: it is difficult to visualize the sequential nature of a circuit’s behavior. A more useful method exists for specifying next-state and output logic that has a powerful advantage‚ it lets you not only specify logic requirements, but also clearly visualize the sequential and/or algorithmic behavior of a circuit.

State Diagram

A state diagram represents states with circles, and transitions between states by arrows exiting one circle and arriving at another. A binary number called the state code can be written in the state-circle to indicate the value stored in the state register when the state machine is in that state. Directed arrows leaving one state and arriving at another show permissible state transitions. Input variable requirements for transitions are shown immediately next to each transition; the indicated transition will only take place if the input conditions shown are present. Transitions (also called branches) occur at every clock edge; thus, at every edge, the present state is exited, and the next-state entered. Often, it is required that for some input conditions, the machine hold in a given state this holding condition is shown as a directed arrow leaving and re-entering the same state. In the partial state diagram shown in Fig. 2, the state register contains three flip-flops: if the state register is storing ‘000’, then it will remain in that state if A is ‘0’ at the next clock edge; otherwise it will transition out of the state if A is ‘1’. The figure on the right uses VHDL syntax for checking and assigning logic values. Many texts use conventional logic equation symbols instead.

Figure 2. States and transitions representation in state diagram.
Figure 2. States and transitions representation in state diagram.

When a state diagram is used as a conceptual tool to help arrive at a given problem solution, it is typically sketched and modified in an iterative fashion. Circles are drawn representing possible states, interconnected according to problem requirements, and redrawn and reconnected as the problem and solution become clearer in the designer’s mind. Once a state diagram has been created that captures the design specifications, a fairly automatic procedure can be applied to create a circuit from the diagram.

State-to-state transitions occur when the state register is loaded with new next-state values. Since the state register can only be written on a CLK edge, state-to-state transitions can only occur on the CLK edge. Thus, the presence of the CLK signal is implied in a state machine, and the CLK signal is not shown in the state diagram. Likewise, RST or PRE signals are not shown in a state diagram; rather, an arrow is shown pointing to an initial state that the machine should assume whenever a reset signal is asserted. A ‘0’ bit in the reset state requires the RST input of the corresponding state register DFF to be connected to the reset signal, and a ‘1’ in the reset state requires the PRE input to be connected to the reset signal. Thus, RST and PRE signals are not shown in the state diagram their presence is implied when an initial state is identified. Only signals that are needed by the next-state or output logic circuits are shown in the state diagram.

An example of a simple state diagram is shown below in Fig. 3. This machine receives input from three buttons labeled X, Y, and Z, and asserts two signals called RED and GRN; RED if and only if the proper three-button-press sequence X-Z-Y is detected; GRN when a new sequence starts. This early stage state diagram does not show state variables or state names. The diagram has evolved by the iterative process mentioned above states and branching conditions were added and modified as the needs of the problem became clearer, until a complete solution was found.

Figure 3. State diagram of a simple state machine.
Figure 3. State diagram of a simple state machine.

Note that for each state, the branching conditions take into account all possible input combinations, and no ambiguous branching conditions are present. If some input combinations are not accounted for, or if branching conditions indicate more than one next state, unpredictable operation can occur. The partial state diagrams in Fig. 4 below illustrate these points in the diagram on the left, if both A and B are ‘1’, or if C = ‘0’, it is not clear which branch to take. The need to unambiguously show possible next states is important enough that many texts name two rules: the sum rule states that all inputs leaving a given state must OR to a logic ‘1’; and the mutual exclusion rule states that any combination of inputs can indicate only one next state.

In Fig. 4 below, the logic graphs illustrate a simple method for ensuring that both the sum rule and exclusion rule have been obeyed (these graphs resemble, but are not, K-maps). One graph is needed to analyze branching conditions from each state, and the number of input variables determines the graph’s size (input variables are used as the axis variables for the logic graph). Each cell in the graph represents the unique combination of inputs indicated by the axis variables, and cell entries show the next state for the branch conditions indicated by the axis variables. Information can be transferred to the logic graph to document the next-states for all branches from a given state. Each cell should have one and only one entry an empty cell indicates the sum rule has been violated, and more than one entry indicates the exclusion rule has been violated. The state diagram on the left of the figure above shows both sum rule and exclusion rule violations, and so the state diagram must be modified before further design activities are attempted. In the example shown, one possible solution that removes all unknowns and redundancies is shown. Note that removing ambiguities changes the branching conditions it is up to the designer to choose new branches that are consistent with the problem description. In general, after a state diagram has been sketched, and before any further circuit design activities are undertaken, it is good design practice to ensure that neither the sum rule nor the exclusion rule are violated.

Figure 4. Sum rule and exclusion rule of state diagram.
Figure 4. Sum rule and exclusion rule of state diagram.

Output signal names are shown near every state during which they must be asserted. If an output must to be asserted in consecutive states, the output should be shown on the state diagram in consecutive states. One method of preparing a state diagram is to show output names only near the states in which they are asserted. A better method is to show each output driven to ‘1’ or ‘0’ in every state this avoids any confusion.

Once the sequential behavior of a problem has been captured with a state diagram, state codes can be assigned to each state. The state codes show the actual contents of the state register when the state machine is in that state. For a state diagram with N states, at least log2Nlog_2Nstate variables are required so that each state can be assigned a unique number. In Fig. 4 above, the state diagram has 4 states, so log2(4)=2log_2 (4)=2 state variables are required. More than the required number of state variables can be used, but in general, the fewest number of state variables needed are used since adding more state variables creates a larger and more complex circuit. Any state code can be assigned to any state, but in practice certain rules can be used to guide the assignment of state codes.

In general, state codes are chosen to minimize the required logic in the next state and/or output logic circuits, or to eliminate timing problems in sequential circuit outputs. One rule of thumb is to minimize the number of flip-flops that change state during any state transition. Ideally, only one flip-flop would change state for any transition in the diagram (a state-to-state transition where only one state variable changes is known as unit-distance coding). It is usually not possible to create a situation wherein all transitions are unit-distance coded, but it is generally possible to choose state codes that yield the highest number of unit-distant coded states. A second rule of thumb is to match state register bits to output requirements wherever possible.

Figure 5. Assign state codes for state diagram.
Figure 5. Assign state codes for state diagram.

For example, in a four-state machine with an output that must be asserted in two of the states, it may be possible to assign state codes such that the output is asserted only when one of the flip-flops is a ‘1’, thereby eliminating the output logic altogether. Figure 5 shows both unit-distant coding, and matching an output to state codes (i.e., the output is ‘1’ whenever flip-flip #2 is a ‘1’, meaning no output logic is required).

Important Ideas

  • A state diagram represents states with circles, and transitions between states by arrows exiting one circle and arriving at another. A binary number called the state code can be written in the state-circle to indicate the value stored in the state register when the state machine is in that state.
  • If some input combinations are not accounted for, or if branching conditions indicate more than one next state, unpredictable operations can occur.
  • Output signal names are shown near every state during which they must be asserted. If an output must to be asserted in consecutive states, the output should be shown on the state diagram in consecutive states.
  • In general, state codes are chosen to minimize the required logic in the next state and/or output logic circuits, or to eliminate timing problems in sequential circuit outputs.