The Quine-McCluskey (QM) method is a tabular form of reduction. It is suitable for problems where the Number of variables involved exceeds four. Hand calculations can be used in problems involving up to six variables. When more than six variables are involved, computer-aided solutions are required. Just like the K-map reduction technique, the QM method also relies on reduction by combining two minterms when they differ from each other in one-bit position only. For example, ABC and ABC′ can be combined to give the term AB as the two terms differ only in the position of the variable C. The QM method involves several steps in reduction process. These steps are illustrated through the following examples.
Quine McCluskey (Tabular) Method Examples
Quine McCluskey (Tabular) Method Examples
Example 12: Reduce S = S(0, 1, 2, 3, 6, 7, 8, 12, 13, 15).
Solution: To solve the given problem, we follow the steps given below:
Step 1: The first step in the QM method is to separate the minterms into specific groups, as shown in Table 2.12. These groups are formed on the basis of the number of 1s in their binary form. For example, the binary number 0000 has no 1 in it and hence forms the first group. Binary numbers 0001, 0010, 1000, 10000, etc. have one 1 in them and are put together to form the second group. This process is continued to form groups with two 1s, three 1s, etc., as shown in Table 2.12.
We shall make use of Table 2.12 to proceed further with our example. By comparison of the minterms in our example with the tabulation given in Table 2.12, we form the groups belonging to the first Chart of the QM scheme. It may be noted that the members in each group differ in one-bit position only from the members of the adjacent group below (or above) that group. For example, ‘0’ in Group P and 1, 2 or 8 in Group Q differ from each other in one bit position only. This rule follows for all the subsequent groups in the first as well as other charts. It may also be noted that the groups are named as P, Q, R, etc. for the convenience of their identification. Once we are familiar with the procedure of groupings, this designation is not required as will be clear from the examples to follow.
Now, the first column of the first chart shows the names of the groups as P, Q, R, S, etc. and the second column shows the member(s) in them. Thus we find that Group Phas only ‘0’ as its member. Below this, in Group Q, we have numbers 1, 2, and 8 as its members. Similarly, every member of Q is different from every member of R in only one position. Thus, we conclude that the groups P, Q,R, etc. are chosen such that every member in a group differs in only one bit position from every other member in the group immediately above or below it. It may also be noted that this is not true for distant groups. Hence grouping and pairing is not possible among distant groups.
Step 2: In this, as stated above, we first form the groups, as shown in Chart 1. From this chart, we prepare Chart 2, which shows the members of each group that can be paired together, these pairings being indicated by tick marks, as shown in Chart 2. For this, we inspect adjacent groups and collect members that differ from one another by a power of 2. For example, ‘0’ of Group P differs by a power of 2 from the members of Group Q. Thus, 0 and 1 differ by 20, 0 and 2 differ by 21, and 0 and 8 differ by 23. Hence, they can be paired together to form the members of Chart 3. The principle behind these pairings is that each of these pairs can be combined to eliminate one bit, as shown:
Table 2.12
Minterm | Number of 1s in the binary equivalent number | |
Decimal number | Binary equivalent number | |
0 | 0000 | 0 |
1 2 4 8 | 0001 0010 0100 1000 | 1 |
3 5 6 9 10 12 | 0011 0101 0110 1001 1010 1100 | 2 |
7 11 13 14 | 0111 1011 1101 1110 | 3 |
15 | 1111 | 4 |
Illustration 1: We can combine Decimal Numbers 0 and 1 as shown below to eliminate D.
As stated, in the pairing shown above, we find that variable D is eliminated.
Illustration 2: As in Illustration 1, we find that decimal numbers 0 and 8 can be combined to eliminate A, shown below. Thus we find that appropriate pairing eliminates the variables appearing in the complemented and uncomplemented forms.
In this way, one pairing operation between adjacent groups results in logic reduction by one bit. As stated previously, it may be noted that pairing must be done strictly between adjacent groups, i.e., between P and Q, Q and R, Rand S, and so on. Pairing cannot be done between P and R, P and S, etc., as they do not obey the rule of difference-in-one-bit-position-only. The results of the pairing are tabulated, as shown in Chart 3. It may also be noted that when a pair is chosen, the corresponding numbers (in decimal form) must be marked with a tick (ü) sign so as to indicate that these numbers have already been selected. This is shown in Column 2 of Chart 3. Column 3 shows the difference between the decimal numbers in each pair; it must be remembered that this difference must be exactly a power of 2, as indicated in Column 4. Usually, Columns 3 and 4 need not be shown in the charts; these can be easily avoided in practical solutions using the QM method. Here, they are shown only for illustration. It also may be noted that to find the difference between two numbers, decimal numbers are easier to remember and handle than binary numbers. For example, it is easy to subtract (mentally) 7 from 12 than subtracting 0111 from 1100. Also, it is easier to find that 12 –7 = 5 is not a power of 2 and hence pairing of 12 and 7 is impossible.
Chart 1 Chart 2
Group name | Members of the group | Group name | Members of the group | |
P | 0 | P | 0b | |
Q | 1 2 8 | Q | 1b 2b 8b | |
R | 3 6 12 | R | 3b 6b 12b | |
S | 7 13 | S | 7b 13b | |
T | 15 | T | 15b |
Chart 3
Group Name 1 | Members of the group 2 | Difference in the pairs in decimal numbers 3 | Difference in the pairs in the power of 2 4 |
P1 |
