Branching method using QM Method and K Map

Branching method is a technique used when a given function does not contain any essential prime implicant in it. The solution to such a problem contains more than one set of solutions. There may be two independent sets of solutions, which may be regarded as two branches of solutions; hence the name branching method.

Example 17: Reduce the expression S = S(0, 1, 5, 7, 8, 10, 14, 15).

Solution: We solve the problem using the QM branching method. For this, we prepare the QM charts as shown below. It can be seen, we can form only two charts. Also we notice from Chart 2 that only eight pairs are obtained and that no quads can be formed from these pairs.

Now, from Chart 2, we obtain the pairs as A(0, 1), B(0, 8), C(1, 5), D(8, 10), E(5, 7), F(10, 14), G(7, 15), and H(14, 15). Table 2.14 shows the desired QM cyclic chart showing entries of these groups.

From the table, we obtain the four selected groups (encircled) as A(0, 1), D(8, 10),, E(5, 7), and H(14, 15). We may also obtain a second set of groups containing pairs B(0, 8), C(1, 5), F(10, 14), and

G(7, 15). Thus in this problem using a cyclic chart (see problem S2.4), we find two independent sets of pairs, both pairs being equally valid and minimum. As stated above, since there are two independent branches of pairs in this problem, this method of solving the problem is called as the branching method. The reduced function using the first branch of pairs mentioned above is:

S = a′b′c′ + ab′d′ + a′bd + abc                                  (2.37a)                                                                                           
and the reduced function using the second branch of pairs mentioned above is:

S = a′c′d + acd′ + bcd +b′c′d                                    (2.37b)                                                                                    

a.   Solution using the Modified QM method

In this scheme, we delete the terms covered by other implicants. For this, let us first choose A(0, 1). Then we strike out B since it contains 0. We next select E(5, 7) and strike out C(1, 5) as  1 and 5  are covered by A and E, respectively. Then we select D(8, 10) and H(14, 15) and delete F (10, 14) and G(7, 15) since the elements in them  are already covered. The finally selected groups are A, D, E, and H, respectively. These are indicated in bold letters.

The selection shown above is quite random, which suggests that there are other possibilities in this case. For example, we can choose B, C, F and G to form a second set of implicants. It can be clearly observed that the minimum number selected is half of the number of implicants present in this case.

It can be seen that the modified QM technique is a general technique and can be easily applied to all types of logic reduction including the problems which use the branching method.

b. Solving the Problem using the K-map Method

We first solve the problem using the K-map method. We prepare the K-map in this case as shown in Fig. 2.28(a). Notice that in this map, we have shown entries only in the cells mentioned in the given problem, i.e., we have shown 1 as the entry in the cells 0, 1, 5, 7, 8, 10, 14, and 15. The remaining cells are left vacant instead of filling them with 0s. This operation will help in identifying the pairs, quartets etc. without confusion. The cells left unfilled may be filled with 0s after the grouping operation is completed. This technique will be followed in this text for solving problem.

From Fig. 2.28(a), we find that the reduced function is the same as that given by Eq. (2.37-b). Similarly, from Fig. 2.28(b), we get a second reduced function, which is the same as that given by Eq. (2.37-a).  

No comments:

Post a Comment