Chapter 5. - Redundant States and The Implication Table

Take the Quiz

In the last example for eliminating redundant states, it should be clear that due to the number of equivalent terms and next state conditions the problem becomes quite difficult to solve. So a different approach can be adopted to split up the task.
One way of doing this is to establish all non-equivalences first and then manipulate the remaining terms so that they are equivalent. Using an implication table will aid in this alternative approach.

A method for using an implication table is 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.
  3. 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.)
  4. If any of the outputs for the rows being compared differ, place an X in the square
  5. If the outputs are the same, list the implied pairs in the square
  6. If the implied pairs are identical (e.g., k & k) or the states themselves, then place a check in the square
  7. 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
  8. Repeat the previous step until no further X's are added

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

The above method is quite hard to follow in text form. Do not be despondent, follow the example below, it explains the method in a friendlier way. To open in a new window, click here.

Take the Quiz