Digital Circuits/Optimization
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Similar States
[edit] Coloring
[edit] State Minimization
While a correctly-designed state machines has an unambiguous behaviour, there can be more than one way on implementing that same behaviour. Conder 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.
[edit] 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 |
If you have forgotten how a Mealy machine is drawn, see here.
[edit] Reduction Method
- 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-quivalent states have been removed, all reamining state-pairs must be equivalent.
- The first step is to go through every cell in the implication chart. For each cell, refer to the two states in the state transistion 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.
- 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 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 → 7.
- For an input of 1: State 3 → 3, 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.
-
- Repeat Step 3 until you check every unmarked cell and cannot mark any of them. In this case, this has already happened.
- Now, search through every unmarked cell (i, j). Write equations "i = j". If you have alreay 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
-
- We have now reduced the state machine to far fewer states (three from seven).
| Figure 1 | Figure 2 |
|---|---|
 |
 |
We can write a new state transistion 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 |
If you have forgotten how a Mealy machine is drawn, see here.
[edit] 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.
