Implication Chart Method for State Minimization

By | 10th September 2021

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.

Figure 1: Implication Chart
Figure 2: Reduced Implication Chart

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.
(Visited 22 times, 1 visits today)

Leave a Reply

Your email address will not be published. Required fields are marked *