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:
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
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.)
If any of the outputs for the rows being compared differ, place
an X in the square
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
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
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.