Question 6.6: Use the implication chart to minimize the state table shown ......

Step 1 Construct an implication chart.
The implication chart is a chart in the form of right triangle, as shown in Figure 6.4.2(a). It can be observed from Table 6.4.3 that there are eight states, so we can construct the implication chart as shown in Figure 6.4.2(a). Note that there is no first state in the vertical direction, starting from state 2 to state 8; there is no the final state in the horizontal direction, starting from state 1 to state 7. This organizing style can effectively avoid the repeat comparison. Each cell in the chart represents the pairs of next states corresponding to a pair of states determined by the vertical and horizontal states.

Step 2 Fill the implication chart.
The chart is completed by comparing each pair of states in the state table to determine whether they are equivalent. The comparing result can be filled in the corresponding cell. Usually, there are three kinds of comparing results.
The first result is that two states can be directly determined to be a pair of equivalent states, entering a tick “√” in the cells corresponding to these state pairs. For the state table in Table 6.4.3, there is no pair of equivalent states that can be directly determined, so no tick occurs in the cells.
The second result is that two states are directly incompatible. If two states are not equivalent, enter a cross “×” in the cells. For example, state 1 and state 3 do not have the same output for each input value, so they are not equivalent and thus a cross “×” is filled into the corresponding cell.

The third result is that two states are possible equivalent. For each input combination, if two states have the same output, the equivalence of their next states must be determined by the equivalence of other state pairs. For this situation, the implied state pairs represented by (a,b) are listed in the corresponding cells. Let us check state 3 and state 8. For each input value, their outputs are the same. So whether or not these two states are equivalent depends on the equivalence of their next states. If X = 0, whether or not state 3 and state 8 are equivalent depends on the equivalence of state 5 and state 8; if X = 1, whether or not state 3 and state 8 are equivalent depends on the equivalence of state 1 and state 4. So state pairs (5,8) and (1,4) are the implied equivalence of state 3 and state 8, which is filled in the corresponding cell. Similarly, the implication chart can be completed as shown in Figure 6.4.2(b).

Step 3 Perform the relevant comparison.
In this step, the implied equivalent pairs in the cell must be checked to determine if they are equivalent. If they are equivalent, a tick “√” is filled in the cell; if they are not equivalent, a cross “×” is filled in the cell. For example, the implied pairs (1,8) corresponding state 3 and state 4 are not equivalent because their outputs are not the same, so a cross “×” is filled in the corresponding cell. The relevant comparison ends until all implied pairs are checked in the cell. Finally, any cell not containing a cross “×” corresponds to an equivalent state pairs, as shown in Figure 6.4.2(c).

Step 4 Merge the equivalent states and minimize the state table.
As shown in Figure 6.4.2(c), each cell without a cross represents a pair of equivalent states. It can be obtained from Figure 6.4.2(c) that all pairs of equivalent states are [1,2], [1,5], [2,5], [3,6], [3,7], [4,8], and [6,7]. With [1,2] and [1,5], state 1, state 2, and state 5 are equivalent, which is represented by [1, 2, 5]; So does [3, 6, 7]. That is, the equivalent pairs are [1, 2, 5], [3, 6, 7], and [4,8]. The resulting minimized state table is obtained as in Table 6.4.4.