Digital Systems Design

Finite State Machine Optimization

Introduction

In this lesson, we will concentrate on state minimization, state assignment, and choice of flip-flops (again and in more depth). Finite state machine optimization is important even in today's era of very large scale integrated circuits. Here, we present methods, as well as more formal techniques suitable for computer implementation, for reducing the number of states and for choosing a state encoding. we also examine the approaches for choosing the machine's flip-flops and how the choice affects the next-state and output combinational functions. The right choice of flip-flop leads to a smaller gate count and thus fewer components to implement the machine. Limited logic resources, such as input/outputs, product terms, or flip-flops may force you to partition your state machine because it cannot fit into a given programmable logic component. So, we develop techniques for partitioning complex finite state machines into simpler, smaller, communicating machines.

Learning Objectives

In particular, we shall cover:

• Procedures for optimizing a finite state machine.

• Application of modern computer-aided design tools for state assignment.

• Techniques for breaking finite state machines into smaller, communicating state machines that are well suited for implementation with programmable logic.

Why Optimization ?

Finite state machine design process consists of

• Step1: Understanding the problem

• Step2: Obtaining a formal description (symbolic state transition table)

• Step3: minimizing the number of states

• Step4: Encoding the states

• Step5: Choosing the flip-flops to implement the state registers, and

• Step6: Implementing the finite state machine's next-state and output functions.

Here we start at step 3 and work through to the final implementation at step 6.

As long as the input/output behavior of the machine is correct, lets see if it really matter how it is implemented.

Two different state diagrams for the odd parity checker are shown above. They have identical output behavior for all input strings.

The two implementations of the state diagrams are certainly not the same. The machine with more states requires more flip-flops and more complex next-state logic.

Equivalence of finite state machines can be defined as "Two machines are equivalent if their input/output behavior is identical for all possible input strings."

For a particular finite state machine, there are many equivalent forms. Rather than reusing states while deriving the state diagram, you could simply introduce a new state whenever you need one (to keep the number of states finite, you will need to reuse some of them).

Finite state machine in as few states as possible usually reduces the number of logic gates and flip-flops you need for the machine's implementation.

For the parity checker, our implementation in previous lessons required no gates because a good state assignment choice naturally matched the control input to the toggle flip-flop.

A state diagram with n states must be implemented with at least k flip-flops, where 2k - 1 < n ð 2k. By reducing the number of states to 2k - 1 or less, you can save a flip-flop. For example, suppose you are given a finite state machine with five state flip-flops. This machine can represent up to 32 states. If you can reduce the number of states to 16 or less, you save a flip-flop. Less logic usually means shorter critical timing paths and a higher clock rate for the system.

A typical programmable logic part might have "2000 gate equivalents" (rarely approached in practice) yet provide only 64 flip-flops! An important goal of state reduction is to make the implementation "fit" in as few components as possible. The fewer components you use, the shorter the design time and the lower the manufacturing cost.

State reduction techniques also allow you to be sloppy in obtaining the initial finite state machine description. If you have introduced a few redundant states, you will find and eliminate them by using the state reduction techniques introduced next.

State Minimization/Reduction

Two states have equivalent behavior if, for all input combinations, their outputs are the same and they change to the same or equivalent next states. State reduction identifies and combines states that have equivalent "behavior."

Referring to the above state diagrams, states S0 and S2 of the state diagram on the right are equivalent. Both states output a 0; both change to S1 on a 1 and self-loop on a 0. Combining these into a single state leads to the state diagram on the left. On all input strings, the output sequence of either state diagram is exactly the same.

In order to reduce states, we begin with the symbolic state transition table. First, we group together states that have the same state outputs (Moore machine) or transition outputs (Mealy machine). These are potentially equivalent, since states cannot be equivalent if their outputs differ. Next, we examine the transitions to see if they go to the same next state for every input combination. If they do, the states are equivalent and we can combine them into a renamed new state. We then change all transitions into the newly combined states. We repeat the process until no additional states can be combined. Alternative algorithms for state reduction include row matching and implication charts. Row matching does not always obtain the best reduced state table, but is easy to accomplish. Implication charts are more complex to use by hand, but they are easy to implement via computer and do find the best solution. Combine the two approaches gives best results. We first quickly reduces the number of states using Row matching and then we find the equivalent states missed by row matching more rapidly using . implication chart method.

Row matching method

In the row matching method we examine the rows of the state transition table. If there are any rows that are identical in both the next state entries and the output entries for all the inputs then the states having the identical rows are considered to be identical states. When two or more states are identified as identical they can be combined into one state. To do this replace all the entries of the identical states in the state transition table by any one of the identical states.

We will use the following state machine as an example:

For example in this machine rows for states S10 and S12 are identical for the next state transitions and the outputs for all the input combinations. Since they are identical we can combine them into one row and eliminate one state. When we do this we have to replace every occurrence of the matched states by the new state. In our example replace states S10 and state S12 by state SA. Similarly the rows S7, S8, S9, S11, S13, and S14 are all identical to each other. We will replace all these states by state SB. Doing these two replacements gives us the following state transition table.

Now we have more rows that are identical to each other. Rows S3 and S6 are identical. We can continue on with this row matching process one more time as follows. We will call them S3 and S6 as SC. Rows S4 and S5 are also identical so we will call then SD with this replacement the state transition table reduces to:

Here we see that we have reduced the original table which had 15 states to one that has only 7 states. Such a drastic reduction is possible only in a few machines. Notice that states S1 and S2 are not identical and also states SB and SA are not identical.

Row matching does not give the most reduced result every time. A more practical method uses the implication’s chart. This is a much more systematic approach to finding states that can be combined into a single reduced state.

The Implication Chart Method

The Implication Chart Method is a more systematic method for finding the states that can be combined into a single reduced state. The method starts by forming a chart that will allow us to compare each state with every other state taken two at a time. This chart known as the Implication Chart.

To use the implication chart you do not have to reduce the table using the row matching method but for hand operations the fewer the number of states you have before you begin the implication chart the lesser the amount of effort you have to put in to get the result. So it is a good idea to begin any state reduction by first identifying identical states as we have just done.

We will study this through an example of a binary sequence detector that will detect an
input of 010 or 110 without overlap. The state transition table for such a detector is shown below.

The implication table shows if two states that are being compared have the same future transition from here on for all future inputs. If the future transitions are the same then the two states may be compatible with each other. Compatibility is guaranteed if the next states are compatible with each other. For example if states S0 and S1 transition to states S4 and S5 and if S4 and S5 are compatible with each other then it is implied that the states S0 and S1 will be compatible with each other. It is from this type of implications that the table gets its name.

Consider following chart:

This method operates on a data structure that enumerates all possible combinations of states taken two at a time, called an implication chart.

The above chart shown above has more cells than needed for comparison. In the way that the diagonal entries are not needed since we do not need to compare a state with itself. Also note that al the upper and the lower triangles of cells are symmetric. The chart cell for row Si and column Sj considers the same information as that for row Sj and column Si. Therefore, the chart reduces to the green structure below:

We will fill the implication chart as follows. Let Xij be the cell whose row is labeled by the state Si and whose column is labeled by the state Sj. If we were able to combine states Si and Sj, it would imply that their next state transitions for each input combination must also be equivalent. The cell contains the next-state combinations that must be equivalent for the row and column states to be equivalent. If Si and Sj have different outputs or next state behavior, an X is placed in the cell. This indicates that the two states can never be equivalent.

The implication chart with initial entries for three-bit sequence detector is as shown below.

S0, S1, S2, S3 and S5 have the same outputs and are the candidates for being combined. Similarly, states S4 and S6 might also be combined. Any combination of states across the groups, such as S1 and S4, is labeled by an X in the chart. Since their outputs are different they can NEVER be equivalent. To fill the chart entry for (row) S1 and (column) S0, we look at the next transition. S0 goes to S1 on 0 and S2 on 1, while S1 goes to S3 and S4 respectively.

We will fill the chart in with S1-S3, the transitions on 0 and S2-S4, the transitions on 1.We call this grouping implied state pairs. The entry means that S0 and S1 cannot be equivalent unless S1 is equivalent to S3 and S2 is equivalent to S4.The rest of the entries are filled in similarly.

At this point the chart contains enough information to prove that many states are NOT EQUIVALENT. For example we already know that S2 and S4 cannot be equivalent, since they have different output behavior. Thus there is no way that S0 can be equivalent to S1.

Next consider the first pass to the implication chart.

Entry S2-S0 has to be marked with X because the chart entry for the implied state pair S2-S6 is already marked with a X. Entry S3-S0 is also marked, because S1-S0 has just been marked. The same is true for S5-S0.by the end of the pass; the only entries not marked are S2-S1, S5-S3 and S6-S4.

We now make a second pass through the chart to see if we can add any new markings. Entry S2-S1 remains unmarked. Nothing in the chart refuses that S3 and S5 are equivalent. The same is true of S4 and S6. Continuing S3-S5 and S4-S6 are now obviously equivalent. They have identical outputs and transfer to the same next state (S0) for all input combinations. Since no marking have been added the algorithm stops. The unmarked entries represent equivalence between the row and the column indices. The final reduced state table can be drawn as:

Now how did you get this table?

The steps of the Implication Chart Method for state reduction can be summarized as follows:

1. Draw the Implication Table so that it contains a square for each pair of states in the next state table, i.e., square i-j is used for checking rows i and j of the state table for equivalence

2. Visit every square in the table so that you compare each pair of rows in the state table (A suggested order for these visits is to start at the top of the left-most column of the Implication Table and to go down the column. After completing all the comparisons for this column, then move to the top of the next column to the right of the previous column and again go from top to bottom. Continue this process until all squares in all columns have been visited.)

   1. If any of the outputs for the rows being compared differ, place an X in the square

   2. If the outputs are the same, list the implied pairs in the square

      • If the implied pairs are identical (e.g., k & k) or the states themselves, then place a check in the square

3. For all squares in the table with implied pairs, examine the square of each implied pair. If any of the implied pair squares has an X, then put an X in this square

4. Repeat the previous step until no further X's are added

5. Upon completion of the previous step, squares without X's, e.g., square i-j, indicate equivalent states, i.e., i º j

We can generalize the procedure for finite state machines with more than one input. The only difference is that there are more implied state pairs: one for each input combination.

State Assignment

The minimum number of flip-flops needed to encode N states is log₂N. There are many possible assignments of binary codes to states, each leading to a different circuit. The state assignment problem is to choose an ‘optimum’ assignment (typically leading to a minimum-cost circuit).

Binary Encoding

There are many state-encoding techniques available for state-word encoding. The simplest is binary of course, but there are others. For example, suppose we have a state machine with 5 states used, then we could apply several alternatives shown below:

Gray-Code Encoding

The Gray-Code is used in order that only one bit changes in each state transition, this ensures that there can be no spurious values in-between two states – for example we could change from 001 to 010 in simple binary, but this may have an intermediate sequence such as:

001 à011à010

or

001à000à010

This can be caused by logic hazards and uneven propagation delays. A gray-code will only have a single bit change, and as such will never have any intermediate values, even if logic delay paths are uneven in the circuit implementation. Unfortunately It is difficult to ensure that all states follow a specific code such as gray-code, since some states are reached from more than one previous state.

A good choice of state assignment can greatly effects the complexity of excitation and output equations. The best state assignment can be only found by trying all the assignments and determining the resulting equations. There is no effective way to guarantee a “best” assignment. Heuristic guidelines can be used for good assignments but they sometimes perform poorly too. The total number of possible state assignments for 5 states: A, B, C, D, E and minimum # of bits (3), is

                        3 bits è 2³ = 8 values

                        8·7·6·5·4  =  8! / 3!   =  6720

One-Hot Encoding

This is an encoding scheme that has one bit per state. This type of encoding is called one-hot because only one state variable bit is set, or "hot," for each state. The benefit is that the next state generation function is simple. Also, because only two bits change per transition, power consumption is small. The drawback is that it takes a lot of register bits, one per state. However, all of these are a real advantage in FPGAs, because FPGAs are register rich.

Typically, there is a register after each LUT. For many state machines, the next state generator for a state bit will fit in a single LUT. Also, because next state functions tend to be local in scope, the routing between state variables is minimal when expressed as one-hot. For most state machines, one-hot is the way to go in FPGAs.

Also, one-hots are easy to implement in schematics. You can almost see the state machine representation jump out at you because each state has its own flip-flop.

An example of one-hot in an 8 state state machine:

00000001
00000010
00000100
00001000
00010000
00100000
01000000
10000000

As you can see, each state is assigned to a flip flop, allowing for minimal decode delay. If area is a concern, then grey codes are the most efficient. An example of grey codes in an 8 state state machine would be:

001
011
111
110
100
000
100
110

In this case, only one bit is changing at any one time, allowing for minimal decode delay.

One-Hot Encoding Example:

Messages composed of five symbols from the set (A, B, C, D, E) are to be transmitted over a serial link. The variable length Huffman code is used to encode the data stream. The binary representation and the frequency of occurrence for the five symbols are:

A suitable set of Huffman code can be designed for this set of symbols as follows:

The continuous stream of received data is translated from Huffman code back to binary code with a finite-state machine decoder as shown below:

All signals change on the rising edge of CLK.

DIN is the serial data stream containing the message in Huffman code designed above. DOUT is the binary code output. It should contain the valid binary code during the clock cycle in which the last bit of each transmitted symbol is received. During this cycle, the VALID signal is high.

The state diagram of the finite state machine assuming that the state machine is initialized to state 0 on power-up and always return to state 0 at the beginning of each symbol can be drawn as follows:

Using one-hot encoding, we can design the logic circuits required to implement this finite state machine in Boolean equation form as follows:

It is not necessary to minimize the logic equations nor obtain the optimal state assignment.

N3 = T2 * /DIN

N2 = T0 * DIN

N1 = T0 * /DIN

N0 = VALID = T1 + T3 + T2 * DIN

DOUT0 = T1 * DIN + T3 * DIN

DOUT1 = T1 * /DIN + T3 * DIN

DOUT2 = T3 * /DIN

No equations has more than 4 input variables. Assuming the finite state machine is implemented with an Altera Flex10K FPGA with 4-LUT based logic cells, only one logic cell is required to implement each equation including the state flip-flop. Therefore 7 logic cells are required to implement the above design.

State Assignment Heuristics

This heuristic deals with determining a good way of assigning sequential machine state names to the state variables (i.e., the flip-flop names) used to implement the machine. Three heuristic rules in the order of precedence are:

1. If two or more states have the same next state for a given input, they should be given adjacent assignments.

2. If two states are both next states of a present state, they should be given adjacent assignments

3. States which have the same output for a given input should be given adjacent assignments.

Lets use am example to illustrate these rules or guidelines for state assignment.

Let is develop the State Graph of a Moore sequential machine that has one input and one output. When the input sequence 011 occurs, the output becomes 1 and remains 1 until the sequence 011 occurs again in which case the output returns to 0. The output then remains 0 until 011 occurs a third time, etc.

Typical input/output sequence as follows,

X = 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1
Z =   0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1

The state diagram can be drawn as follows:

The State Table for the above State Diagram can be drawn as follows:

Note: There is only one output for both inputs (i.e. whether X=0 or X=1). Because we are considering Moore Machine.

Then, Using Implication Chart, reduce the number of states to the following. Here the step is not shown, and students are encouraged to verify this step using the Implication Chart method described earlier.

We can re-label the states so that they are in the order A, B, C, D, E, F again as below, but this step is not necessary.

Now consider first rule of the Heuristic: States which have the same next state for a given input should be given adjacent assignments.

 

The table highlighted shows that, States (A, B, C) which have the same next state (B) for a given input (X=0) should be given adjacent assignments. i.e. B next state for the same input X=0 suggests that the states A, B and C should be given adjacent assignments.

Also,

States (D, E, F) which have the same next state (E) for a given input (X=0) should be given adjacent assignments.

States (C, D) which have the same next state (D) for a given input (X=1) should be given adjacent assignments.

States (A, F) which have the same next state (A) for a given input (X=1) should be given adjacent assignments.

So, we need to have adjacency assignment for:

• A, B and C

• D, E and F

• C and D

• A and F

Now consider second rule: States which are the next states of the same state should be given adjacent assignments.

The above highlighted table shows that, States (B,A)  which are the next states of the same state (A) should be given adjacent assignments.

Similarly, States (B,C)  which are the next states of the same state (B) should be given adjacent assignments. States (B,D)  which are the next states of the same state (C) should be given adjacent assignments. States (E,D)  which are the next states of the same state (D) should be given adjacent assignments. States (E,F)  which are the next states of the same state (E) should be given adjacent assignments. And, States (E,A)  which are the next states of the same state (F) should be given adjacent assignments.

In all, the table suggests adjacency assignment for:

• B and A

• B and C

• B and D

• E and D

• E and F

• E and A

Now consider third rule: States which have the same output for a given input should be given adjacent assignments.

The above highlighted table shows that States (A, B and D) which have the same output of 0 for a given input should be given adjacent assignments. Also, States (D, E and F) which have the same output of 0 for a given input should be given adjacent assignments. Therefore,

The output of 0 suggest adjacency for

• A, B and D

while the output of 1 suggest adjacency for

• D, E and F

Lets list all the conditions again.

Rule 1 is to be applied first and then Rule 2 and then Rule 3.

First draw an 3 variable k-map, as six states can be implemented using 3 flip flips using binary assignment.

Now try to incorporate Rule 1 in the above k-map

Note that, though there are several ways to incorporate the rules, but we have selected it such that all rules can be applied simultaneously. That is, the following k-map meets all the requirements of (A, B and C), (D, E and F), (C and D), (A and F)

The above k-map meets most of the Rule 2 and Rule 3 criteria too.

Therefore, the State Binary Assigned of the State Table:

is

Here, A is replaced by 000 as per the k-map. Then the A's in the Next State Table are replaced by the state assignment for A, i.e. 000

Similarly for B, C, D, E and F.

After deriving the above state table, we need to select flip flops. Then, using the excitation table for the selected flip-flop, we need to drawn another state table, with the Flip Flop input entries.

Lets choose J-K Flip Flop. The excitation for the J-K Flip Flop has to be used.

The next State table can be drawn with Inputs X=0 and X=1 distributed for each row as:

Only one entry is filled above. Rest is to be filled by the students and complete the table.

Then using K-Maps, we can design the sequential circuit.

 

Choice of Flip-Flops

After state reduction and state assignment, the next step in the design process is to choose flip-flop types for the state registers. Usually, we have to decide whether to use 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 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:

1. Given the state assignments, derive the next-state maps from the state transition table.
2. Remap the next-state maps given the excitation tables for the flip-flops chosen to implement the state bits.
3. Minimize the remapped next-state function.

Procedure with the 4-bit sequence detector is illustrated here, using the state assignment as shown in the encoded state transition table below:

Each state has been replaced by its binary encoding given by the state assignment. Table below is the encoded next-state map, organized according to the standard binary sequence and showing the don't cares.

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. The four-variable K-maps for the next-state functions Q2+, Q1+, Q0+, given the current state Q2, Q1, Q0 and the input I can be drawn. The reduced equations that describe the inputs to the D flip-flops are

D_Q2+ = Q₂ . Q₁ + Q₀

D_Q1+ = Q₁ . Q₀ . I + Q₂ . Q₀. I + Q₂ . Q₁

D_Q0+ = Q₂ . Q₁ + Q₂. I

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 Implementation 

For the J-K implementation, we begin by remapping the inputs based on the J-K excitation tables. Figure below gives the remapped next-state table. The J-K logic equations become

JQ2+ = Q1 JQ1+ = Q2 JQ0+ = Q2 . Q1 + Q2. I

KQ2+ = Q0 KQ1+ = Q0 . I + Q0. I + Q2 . Q0 KQ0+ = Q2

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 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.