Simplification When Don’t-Care Terms are Present:
Example 16: We now use an example to illustrate the reduction process in the QM when don’t-care terms appear in the given logic function. Reduce S = Sm(1, 2, 4, 5, 6, 8, 9, 12) + d(3, 10, 13, 15).
Solution: Chart 1 shows the initial grouping, Chart 2 shows the pairs, and Chart 3 shows the quads. In the case of the K-map reduction technique, don’t-care terms were treated as valid terms if it were helpful in the reduction process. The same assumption is brought into the QM reduction process also. The QM charts of Example 16 are drawn as shown below using the principles discussed in the previous sections.
Example 16: We now use an example to illustrate the reduction process in the QM when don’t-care terms appear in the given logic function. Reduce S = Sm(1, 2, 4, 5, 6, 8, 9, 12) + d(3, 10, 13, 15).
Solution: Chart 1 shows the initial grouping, Chart 2 shows the pairs, and Chart 3 shows the quads. In the case of the K-map reduction technique, don’t-care terms were treated as valid terms if it were helpful in the reduction process. The same assumption is brought into the QM reduction process also. The QM charts of Example 16 are drawn as shown below using the principles discussed in the previous sections.
It may be noticed that the don’t-care terms are identified with the letter d attached to them in Chart 1. However, once they are identified, the letter d is dropped from respective terms, as shown in Chart 3. Now, the quads and pairs are designated using bold letters digits as shown. The reduced terms represented using bold letters are:
A : 1, 5, 9, 13
B : 4, 5, 12, 13
C : 8, 9, 12, 13
D : 1, 3
E : 2, 3
F : 2, 6
G : 2, 10
H : 4, 6
I : 8, 10
J : 13, 15
The above groups are now entered as shown in Table 2.18 for reduction by the modified QM technique. In Table 2.18, we represent the selected groups by bold digits. The groups that are not selected are represented by conventional letters and digits. In Table 2.18, we have shown a third column with entries Y/N. Y represents yes, indicating the selection of that group, while N represents no indicating the rejection of that group.
The finally selected reduced Groups are A, B, C, and F. In selecting these groups, we have discarded Groups D, E, H, I, and J, as each one of them contains at least one don’t-care term, which has no relevance at all in the final groups. For example, Groups D (2, 3d) and G (2, 10d) have no relevance at all since the only valid member in these groups, viz., 2, has already been selected in Group F. Hence they are discarded. The same is the case with E, H, I, and J. The reduction process to get the final SOP expression is then carried out, as shown in Table 2.19.
From Table 2.19, we obtain the resultant expression as
S = c′ d + bc′ + ac′ + a′ b′ d +a′ cd′ (2.40)
We now solve Example 15 using the K-map shown in Fig. 2.40. From the K-map, we obtain the resultant expression as the same one given by Eq. (2.40).
Table 2.19
Group | Group members | Elimination | Reduced Function |
A | 1, 5, 9, 13, | 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 | c′d |
B | 4, 5, 12, 13 | 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 | b c′ |
C | 8, 9, 12, 13 | 1 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 | a c′ |
F | 2, 6 | 0 0 1 0 0 1 1 0 | a′ c d′ |