Implication Chart Method for State Minimization

Implication Chart Method for State Minimization is very popular for reducing the steps of an FSM and it is more machine friendly method than Row Equivalence Technique. In this method, a chart is prepared to find the equivalent steps. The implication chart is shown in Figure 1. States are written along the x-axis as $S_0$ , $S_1$ ,…, $S_n$ and the states are written along the y-axis in the reverse order. A square $X_{ij}$ , contains the equivalent states between $S_i$ and $S_j$ . The Implication Chart can be modified as $X_{ij}=X_{ji}$ and thus the triangle above the diagonal can be removed. Also, the diagonal can be removed as there is no sense to find equivalence to a state and itself. The reduced implication chart is shown in Figure 2.

First step of Implication Chart Method for State Minimization is to fill the squares of the chart correctly. According to the state table shown in Table 1, an implication chart is shown in Figure 3. The squares are filled as by two rows. First row consists of 0-successors and the second row consists of 1-successors. In the topmost square from the left side, first row is $S_3 - S_1$ and the second row is $S_5 - S_2$ . These pairs are called as implied state pairs. During the filling of squares, some boxes are crossed for states which can not be combined. For example, $S_2$ and $S_0$ can not be combined as their output is different.

Table 1: State table example for state minimization.

Figure 3: Implication chart after filling of squares and marking cross for not related states.

State minimization by Implication chart method is accomplished by some passes until no further combination is possible. Searching of equivalent states is done from the top to the bottom starting from the left side of the chart. The state $S_1$ can be combined with state $S_0$ or $S_3$ as shown in Figure 4. But state $S_2$ and $S_5$ can not be combined as the square corresponding to the states $S_3$ and $S_4$ is marked crossed. So, the square block corresponding to $S_2$ and $S_5$ is cross marked. Similarly for the square block $X_{65}$ as state $S_6$ and $S_3$ can not be combined. At the end of the first pass it can be concluded that $S_0$ , $S_1$ and $S_3$ can be equivalent. Also, $S_2$ , $S_4$ and $S_6$ can be combined. The state $S_5$ can not be combined any other states.

Figure 4: Implication chart after pass 1.

Second pass started similarly from the top to bottom starting from the left to right as shown in Figure 5. Here, the square block $X_{10}$ is cross marked as we have seen in the earlier pass that $S_2$ can not be combined with $S_5$ . Similarly, the square block $X_{31}$ is cross marked because of state $S_5$ . After the second pass it can be concluded that $S_0$ and $S_3$ are equivalent. Also, $S_2$ , $S_4$ and $S_6$ are equivalent.

Figure 5: Implication chart after second pass.

Another pass can be run but after the third pass there is no new state for reduction. Thus finally the modified state table can be formed. Here, $S_0$ and $S_3$ are combined as $S^*_0$ . The states $S_2$ , $S_4$ and $S_6$ are combined as $S^*_2$ . The modified state table is shown below in Table 2. Here, initially there were seven states and after minimization there are now four states.

Table 2: State table shown in Table 1 after state minimization.

-2

Related Posts