1. Digital Logic
2. Topic: Structural Implementation of State Diagram

Structural Implementation of State Diagram

A state diagram with state codes and complete branching conditions contains all information required for the design of optimal next-state and output logic circuits. In fact, a state diagram contains exactly the same information as the state table (or next-state truth table), with the added benefit of showing sequential flow. By following a few simple rules, the information in a state diagram can be transferred directly to K-maps so that a minimal next state logic circuit can be found.

The process is illustrated in the three figures below using a state diagram similar to the one presented earlier (but in this state diagram, the GRN output is now a Mealy output that combines the X and Y inputs with state codes see states ‘01’ and ‘11’). In the first step, all branch conditions are checked to ensure that neither the sum rule nor the exclusion rule is violated (branch condition checking uses the logic graphs as shown in Fig. 1). State codes are assigned so that a minimum number of bits change across the set of all state transitions. In this example, it is not possible to use unit-distant coding for all state transitions, nor is it possible to match outputs to state codes. The state codes shown result in the greatest number of transitions having unit-distant codes. The second step is to transfer information from the state diagram to K-maps so that logic circuits can be defined.

In this example, two state variables and two outputs require four K-maps, one for each of the next-state circuit, and one for each output. The next-state circuits will drive the D inputs of the state-variable flip-flops, and the output logic circuits will produce outputs based on the state variables and inputs. The state variables are used as the K-map index variables for all four maps. In the next- state maps, branch condition inputs are shown as entered variables. Thus, loops in the next-state maps will be in terms of the state codes (axis variables) and inputs (entered variables). For output maps, a ‘1’ or ‘0’ is placed in a cell to indicate whether an output is asserted in that state; for Mealy outputs, the input variables that drive the output are placed in the maps as entered variables. The Rules below describe to process of populating K-maps in detail.

1. Sketch one K-map for each state variable and each output. The state variables are the K-map index variables (and so K-map size is determined by the number of state variables). Since state variables are used on the K-map indexes, each cell K-map cell corresponds to a present state.
2. For next state K-maps, enter branch conditions from each present state into the corresponding K-map cell if, and only if, the branch leads to a next state where the state DFF being mapped is ‘1’.
3. For Moore model K-maps, enter a ‘1’ in each K-map cell where the output must be asserted; for Mealy model K-maps, enter a ‘1’ for unconditional outputs, or the variable (or expression) for conditional outputs in each K-map cell where the output must be asserted.

The process is applied to the state diagram above in Fig. 1, resulting in the K-maps shown below in Fig. 2.

The third and final step is to create a circuit from the equations obtained from looping the K-maps. A block diagram of the circuit is shown below in Fig. 3. You should recognize the Mealy model schematic. Following the methods described and with sufficient practice, a wide variety of state machines can be designed.