Digital Circuits/Optimization

State Minimization

While a correctly-designed state machines has an unambiguous behaviour, there can be more than one way on implementing that same behaviour. Consider the two FSMs below:

Generally speaking, we want to find the implementation of an FSM which have fewest state, and therefore require fewest resources, be this size of a ROM device or LEs in an FPGA.

Implication Charts

Implication charts are a common way of reducing an FSM. It works by finding states that have identical transitions to each other. It is a graphical method suitable for fast computation by hand.

First, lets consider a grid of size N×N, where N is the number of states. Each cell represents a pair of states. As this is an unordered pair, the cell (i, j) is equivalent to (j,i), so it can be omitted (green squares). Also, the state is of course equivalent to itself (blue squares). We can then eliminate the upper right triangle and the diagonal. For a seven-state machine, we will have the following implication chart outline:

Note that there are N−1 squares in each direction, and that in any cell, M<N.

In order to begin optimising an FSM, we need a state transition table. For this example, we will take as an example the FSM that implements the following:

Current State	Next State		Output
	Input X		Input X
	0	1	0	1
0	7	2	0	0
1	7	5	0	0
2	7	0	1	0
3	0	7	1	0
4	3	6	0	0
5	3	1	1	0
6	3	4	1	0
7	4	3	1	0

(Index of exercises)

Exercise • From this state tranistion table, draw the Mealy finite state machine that implements it.

If you have forgotten how a Mealy machine is drawn, see here.

Solution

File:FSM Reduction by Implication Chart - Exercise.svg

Reduction Method

1. Draw the implication chart. You have one cell for each possible combination of states. The aim is to eliminate all non-equivalent pairs of states. Elimination is indicated by "marking" the cell with a cross. Once all non-equivalent states have been removed, all remaining state-pairs must be equivalent.
2. The first step is to go through every cell in the implication chart. For each cell, refer to the two states in the state transition table and look at the outputs for each input.
   • If the outputs are different, place a cross in the cell. Look at the output for each input − they must be the same. The states cannot be equivalent if they have different outputs.
   • If the output are the same, the states may be equivalent − this will occur if the next states are also the same. In the cell, write the next states of each of the two state represented by that cell. For example, if cell (2,5):

   For an input of X=0: State 2 → 7, State 5 → 3.

   For an input of X=1: State 2 → 0, State 5 → 1.

   Therefore, we write "7−3" in the top of cell (2,5) and "0−1" on the bottom. We are writing the next state pairs for each output. Figure 1 below shows the implication chart at the end of this stage.

3. The next stage is to go through the chart again. This time we look at the state pairs listed in every unmarked cell. Consider each of the next-state pairs separately. If the cell representing the next-state pair has been marked, mark the current state also (you may have to reverse the order of the states). If any of the next state-pairs are not equivalent, the current state cannot be equivalent. If the cell contains an entry "i−i", ignore it, as a state must be equivalent to itself. For example:

   For an input of 0: State 3 → 0, State 5 → 3.

   For an input of 1: State 3 → 7, State 5 → 1.

   Now, the states 0 and 3 are not equivalent (call (0,3) has been marked). Now, if the next states are not equivalent, then the current state also isn't. Therefore, we mark (3,5). Figure 2 shows the result after the first pass, with new marks shown in red.

4. Repeat Step 3 until you check every unmarked cell and cannot mark any of them. In this case, this has already happened.
5. Now, search through every unmarked cell (i, j). Write equations "i = j". If you have already put one of the terms in an equation and not the other, add it to that equation instead. In this case:

   • 0=1=4
   • 2=5=6
   • 3=7

6. We have now reduced the state machine to far fewer states (three from eight).

Figure 1	Figure 2

We can write a new state transition table, using just one of the (equivalent) states from each equation − we'll choose 0, 2 and 3. It doesn't matter which ones you choose, and you can renumber them afterwards, but we won't bother here.

Current State	Next State		Output
	Input X		Input X
	0	1	0	1
0	3	2	0	0
2	3	0	1	0
3	0	3	1	0

(Index of exercises)

Exercise • From this state tranistion table, draw the Mealy finite state machine that implements it.

If you have forgotten how a Mealy machine is drawn, see here.

Solution

File:FSM Reduction by Implication Chart - Exercise 2.svg

Optimization

This section of the Digital Circuits wikibook is a stub. You can help by expanding this section. If you add something, list yourself as a Contributor.