Usually, we have to decide whether to use

The following procedure completes the finite state machine implementation, given a particular choice of flip-flops:

Each state has been replaced by its binary encoding given by the state
assignment.

Figure 9.40 is the encoded next-state map, organized according to the
standard binary sequence and showing the don't cares.

D

There are six unique product terms and 15 literals.
In terms of discrete gates, the implementation requires 3 three-input gates,
5 two-input gates, and 4 inverters, a total of 12 gates.

J-K

This implementation requires nine unique terms and 14 literals. The gate
count is 1 three-input gate, 6 two-input gates, and 3 inverters, a total
of 10 gates. This is slightly fewer than the

However, when using some forms of programmable logic, we may need to partition the machine. In some cases we cannot implement a complex finite state machine with a single programmable logic component. The machine might require too many inputs or outputs, or the number of terms to describe the next-state or output functions might be too large, even after state reduction and Boolean minimization.

Suppose we can arrange the outputs in two sets of five, each of which can be computed from different 15-element subsets of the original 20 inputs. Then we could partition the output functions among two programmable logic components, as shown in Figure 9.44.

Of course, it isn't always possible to find such a fortuitous partitioning.
For example, every output might be a function of 16 inputs.

If we cannot reduce the complexity of the finite state machine by simple input/output partitioning, another way to "make it fit" is to partition the single finite state machine into smaller, less complex, communicating finite state machines. We examine this approach in the next subsection.

We have chosen to partition the state diagram into two separate machines,
containing states

What happens if we partition the state diagram, but a transition must take place between the two pieces? We need to introduce idle states to synchronize the activity between the two finite state machines. In essence, the machine at the left hands control off to the machine at the right when a transition from

The revised state diagrams are shown in Figure 9.46.

We have introduced two new states,

Suppose that the right-hand machine sequences through some states, eventually returning to

The first rule applies for a state that is the source of a transition that crosses the boundary. The case is shown in Figure 9.47

The cross-boundary transition is replaced by a transition to the idle
state, labeled by the same exit condition as the original transition. For
example, the

The second rule applies to the destination of a transition that crosses the partition boundary. This is shown in Figure 9.47

The third rule applies when multiple transitions share the same source or destination. This case is illustrated in Figure 9.47

If a state is the target of multiple transitions across the boundary, a single transition is added from the idle state to this state. The transition is labeled with the OR of the conditions associated with the individual transitions in the original state machine. This case is illustrated by the transitions from

When all these rules have been applied, the final rule describes the self-loop

The machine implements a simple up/down counter. When the input

The goal is to partition the machine into two communicating four-state finite state machines. We might need to do this because the underlying logic primitives provide support for two flip-flops within the logic block, as in the Xilinx CLB to be introduced in the next chapter.

Figure 9.48

The machine at the left enters its idle state

To see how the machines communicate, let's consider an up-count sequence from

Meanwhile, the right machine holds in

*J*-*K*flip-flops or*D*flip-flops.*J*-*K*devices tend to reduce the gate count but increase the number of connections.*D*flip-flops simplify the implementation process and are well suited for VLSI implementations, where connections are at more of a premium than gates. Because the CAD tools mentioned in the previous section were developed to assist in VLSI implementations, it is not surprising that they implicitly assume*D*flip-flops as the targets of the assignment. Their best assignment may not lead to the minimum logic for a*J*-*K*flip-flop implementation.The following procedure completes the finite state machine implementation, given a particular choice of flip-flops:

- Given the state assignments, derive the next-state maps from the state
transition table.

- Remap the next-state maps given the excitation tables for the flip-flops
chosen to implement the state bits.

- Minimize the remapped next-state function.

### 9.4.1 Flip-Flop Choice for the Four-Bit Sequence Detector

Let's illustrate the procedure with the 4-bit sequence detector, using the state assignment of Figure 9.39, the encoded state transition table.D

**Implementation**To obtain the direct form for determining the state machine implementation with*D*flip-flops, represent the encoded next-state functions as K-maps. Figure 9.41 contains the four-variable K-maps for the next-state functions*Q*2`+`

,
*Q*1`+`

, *Q*0`+`

, given the current
state *Q*2,*Q*1,*Q*0 and the input*I*. The reduced equations that describe the inputs to the*D*flip-flops are**Implementation**For the*J*-*K*implementation, we begin by remapping the inputs based on the*J*-*K*excitation tables. Figure 9.42 gives the remapped next-state table, and Figure 9.43 shows the K-maps. The*J*-*K*logic equations become*D*flip-flop implementation. However, when you use structured logic such as a PLA to implement the functions, the option with fewer product terms is better. In this case, it would be the*D*implementation.## 9.5 Finite State Machine Partitioning

In the preceding sections, we described the design process for a single monolithic finite state machine. The approach is reasonable for many strategies for implementing a finite state machine, such as using discrete gates.However, when using some forms of programmable logic, we may need to partition the machine. In some cases we cannot implement a complex finite state machine with a single programmable logic component. The machine might require too many inputs or outputs, or the number of terms to describe the next-state or output functions might be too large, even after state reduction and Boolean minimization.

`Example 1`

` FSM Partitioning`

To illustrate
the value of state machine partitioning, suppose we have a finite state
machine with 20 inputs and 10 outputs `(`

including next-state
outputs`)`

. But we only have programmable logic components with
15 inputs and 5 outputs. We cannot implement this finite state machine with
a single component.Suppose we can arrange the outputs in two sets of five, each of which can be computed from different 15-element subsets of the original 20 inputs. Then we could partition the output functions among two programmable logic components, as shown in Figure 9.44.

If we cannot reduce the complexity of the finite state machine by simple input/output partitioning, another way to "make it fit" is to partition the single finite state machine into smaller, less complex, communicating finite state machines. We examine this approach in the next subsection.

### 9.5.1 Finite State Machine Partitioning by Introducing Idle States

Partitioning the finite state machine makes sense if the next-state logic is too complex to implement with the programmable logic components at hand. The problem is that PALs provide a fixed number of product terms per output function. We can make a trade-off between the number of flip-flops needed to encode the state and the complexity of these next-state functions. Our idea is to introduce additional "idle" states into the finite state machine in the hope of reducing the number of terms in the next-state functions.`Example 2`

` FSM Partitioning`

For
example, Figure 9.45 shows a subset of a state diagram. *S*1,*S*2,*S*3 and*S*4,*S*5,*S*6, respectively. The symbols*C*i associated with the transitions represent the Boolean conditions under which the transition takes place.What happens if we partition the state diagram, but a transition must take place between the two pieces? We need to introduce idle states to synchronize the activity between the two finite state machines. In essence, the machine at the left hands control off to the machine at the right when a transition from

*S*1 to*S*6 takes place. The left machine must idle in some new state until it regains control, such as when there is a transition from*S*6 back to*S*1. In this event, the machine on the right must remain idle until it regains control.The revised state diagrams are shown in Figure 9.46.

*S*A and*S*B, to synchronize the transitions across the partition boundary. Here is how it works for the state sequence*S*1 to*S*6 and back to*S*1. Initially, the machines are in states*S*1 and*S*B. If condition*C*1 is true, then the left-hand state machine exits*S*1 and enters its idle state,*S*A. At the same time, the right-hand machine exits*S*B and enters*S*6.Suppose that the right-hand machine sequences through some states, eventually returning to

*S*6. Throughout this time, the left-hand machine remains in its idle state. If the right-hand machine is in*S*6 and*C*2 is true, it next enters its idle state,*S*B. At the same instant, the left-hand machine exits*S*A, returning to*S*1. While the left-hand machine sequences through states, the right-hand machine idles in*S*B.**Rules for Partitioning**We are ready to describe the rules for introducing idle states into a partitioned finite state machine. We illustrate each rule with an example from the partitioned state machine of the previous subsection. All the rules involve transitions that cross the partition -boundary.The first rule applies for a state that is the source of a transition that crosses the boundary. The case is shown in Figure 9.47

`(`

a`)`

.
*S*1-to*-S*6 transition is replaced by a transition with the same condition to*S*A.The second rule applies to the destination of a transition that crosses the partition boundary. This is shown in Figure 9.47

`(`

b`)`

.
The transition is replaced with an exit transition from the idle state,
labeled with the original condition ANDed with the source state. For example,
the transition from *S*6 to*S*1 is replaced with a transition from*S*A. We exit the idle state when both*C*2 is true and the right-hand state machine is in*S*6. Hence, the transition is labeled with the condition*C*2*S*6.The third rule applies when multiple transitions share the same source or destination. This case is illustrated in Figure 9.47

`(`

c`)`

.
If a state is the source of multiple transitions across the partition boundary,
all of these are collapsed into a single transition to the idle state. The
exit conditions are ORed together to label the new transition. For example,
*S*2 has transitions to states*S*5 and*S*4. These are replaced with a single transition to*S*A, labeled*C*3`+`

*C*5.If a state is the target of multiple transitions across the boundary, a single transition is added from the idle state to this state. The transition is labeled with the OR of the conditions associated with the individual transitions in the original state machine. This case is illustrated by the transitions from

*S*2 and*S*3 to*S*5. These are replaced by a single transition from*S*B to*S*5, labeled*C*3*S*2`+`

*C*4*S*3.When all these rules have been applied, the final rule describes the self-loop

`(`

"hold"`)`

condition
for the idle states. Simply form the OR of all of the exit conditions and
invert it. This is shown in Figure 9.47`(`

d`)`

. Consider
the idle state *S*A. Its only exit condition is*C*2*S*6. So its hold condition is the inverse of this, namely .`Example 3`

` FSM Partitioning`

Consider
the six-state finite state machine of Figure 9.48`(`

a`)`

.The machine implements a simple up/down counter. When the input

*U*is asserted, the machine counts up. When*D*is asserted, it counts down. Otherwise the machine stays in its current state.The goal is to partition the machine into two communicating four-state finite state machines. We might need to do this because the underlying logic primitives provide support for two flip-flops within the logic block, as in the Xilinx CLB to be introduced in the next chapter.

Figure 9.48

`(`

b`)`

shows the result
of the partitioning. States *S*0,*S*1, and*S*2 form the core of one machine and*S*3,*S*4, and*S*6 form the other. We also introduce the two idle states,*S*A and*S*B.The machine at the left enters its idle state

*S*A when it is in*S*0 and*D*is asserted or when it is in*S*2 and*U*is asserted. It exits the idle state when the machine at the right is in*S*5 with*U*asserted or in*S*3 with*D*asserted. Otherwise it stays in its idle state. The machine at the right works similarly.To see how the machines communicate, let's consider an up-count sequence from

*S*0 to*S*5 and back to*S*0. On reset, the machine on the left enters*S*0 while the machine on the right enters*S*B. With*U*asserted, the left machine advances from*S*0 to*S*1 to*S*2 to*S*A. It will idle in this state until the right machine is ready to exit*S*5.Meanwhile, the right machine holds in

*S*B until the left machine enters*S*2. At the same time that the left machine changes to*S*A, the right one exits*S*B to*S*3. On subsequent clock transitions, it advances from*S*3 to*S*4 to*S*5 to*S*B, where it holds. When the right machine changes from*S*5 to*S*B, the left machine exits*S*A to*S*0, and the process repeats itself. Down-count sequences work in an analogous way.