Chapter 5. - Redundant States and The Implication Table

Next Page of this Chapter

How do we know if a state diagram is optimized?
Quite simply, we don't. There are what's called redundant states that can occur in state diagrams and therefore state tables. This section will explain how to recognize redundant states and also how to eliminate them to reduce the complexity of the problem. (By reducing the number of states we can reduce the number of flip-flops we need to use, see chapter 7)

What are redundant states?

Two states which appear numerically different, can in actual fact be logically identical.
States are identical if both of the following are satisfied:

  1. The output of both states are equal.
  2. Both states have equivalent next states.

Statement 2, simply means that if the next states are compared together and are found to be equal (or reference the states we are looking at) then we can consider them equal to each other. See the diagrams below.

The last diagram is the difficult one to understand. It is quite easy to see wether two (or more) states are redundant or not in the first two diagrams as the outputs are different. The third diagram demonstrates that if the next states are different and those next states are not equivalent to each other, then the two states cannot be considered redundant. However the last diagram demonstrates that if the outputs are equal and the next states are equivalent to each other (i.e. state 1 is equivalent to state 2 if state 2 is equivalent to state 1.) then the two states can be considered equivalent and therefore eliminate one of them.

Re-read the last passage several times and try to work through the above diagrams until it all makes sense as this is quite an abstract stage.

Next Page of this Chapter