0

## Quine McCluskey (Tabular) Method Example

• 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 P has 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, R and 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 0, 1 0, 2 0, 8 1 – 0 = 1 2 – 0 = 2 8 – 0 = 8 20 21 23 Q1 1, 3 2, 3 2, 6 8, 12 3 – 1 = 2 3 – 2 = 1              6 – 2 = 4            12 – 8 = 4 21 20                    22                    22 R1 3, 7 6, 7 12, 13 7 – 3 = 4 7 – 6 = 1            13 – 12 = 1 22 20                    20 S1 7, 15 13, 15 15 – 7 = 8 15 – 13 = 2 23 21

Step 3: In Step 3, we make still lager pairings. For example, a pair from group P1 can be combined with a pair from the adjacent group Q1 if they differ by a power of 2.  Thus, in Chart 3, the pair (0, 1) of Group P1 can be combined with the pair (2, 3) from Group Q1, as they differ by the same power of 2 (i.e., 20 = 1) between individual members and by 21 between the pairs. That is, between 0 and 1, the difference is 20  (= 1); between 2 and 3, difference is 20  (= 1).

Now, to find the second condition, i.e., the difference between pairs, take any member in pair P1, say 0. We now find the difference between 0 and 2, its corresponding member in pair Q1.  The difference can be seen to be equal to 2 (=21).  Since the pairs (0, 1) and (2, 3) have satisfied our two conditions, we can combine them to form a quad P2.  Once 0, 1, 2, and 3 are grouped, the grouping 0, 2, 1, and 3 can also be ticked off, as this quad has already been selected once.  By checking out for groupings in this fashion, we find that we have one more quartet (i.e., 2, 3, 6, 7) available to us.  No further pairings are possible in this group. The second set of groupings is shown in Chart 4.

Now, we notice that some pairs such as (0, 8), (8, 12), (12, 13), (7, 15) and (13, 15) are left behind in Chart 3 which cannot be combined further.  We encircle each one of these groups and keep them as independent groups with names A, B, C, etc. as shown in Chart 5. According to this scheme, the pair (0, 8) is designated as A, the pair (8, 12) is designated as B, and so on. The pairs and quads show reduction in variables, which are then checked for repetition; if a  pair or quad is covered in other pairs, quads etc., then such pairings will be discarded. The remaining SOP expression will be used for logic implementation

Step 4: The next step in the QM reduction process is to find whether pairing is possible from groups P2 and Q2 to form an octet.  For this, we must see that individual members differ by the same pattern in both groups, and any member in one group differ by a power of 2 with the corresponding member in the other group.

In our example, adjacent numbers of Group P2 differ by a factor of 1 (= 20) between them. Thus we observe that 0, 1, 2, and 3 differ by 1 from each other.  Now, consider the members in Group Q2. These are, respectively, 2, 3, 6 and 7.  Even though 2 and 4, and 6 and 7 differ by 1 from each other, the adjacent members 3 and 6 differ by 3 and hence the pattern of 1-difference-between-adjacent members is not followed here.  So, in the first instance itself, these groups cannot be combined to form an octet. Thus, we stop at this point, and name the quad (0, 1, 2, 3) as final Group F and the quad (2, 3, 6, 7) as final Group G and encircle them, as shown in Chart 5.

Chart 5

 Final groups Members of the final groups A B C D E F G 0, 8 8, 12 12, 13 7, 15 13, 15 0, 1, 2, 3 2, 3, 6, 7

Step 5: The last step is to remove the common (or, redundant) terms, which have been selected more than once from different groups. In the QM method, Table 2.13 is drawn as shown in for the reduction purposes.

As shown in Table 2.13, the first column represents the names of the groups. The remaining columns are drawn to enter all the minterms in the given problem. In our problem, we have the minterms 0, 1, 2, 3, 6, 7, 8, 12, 13 and 15. So, we must draw tabular columns to accommodate all of these minterms.

After drawing the rows and columns of Table 2.12 as shown, we mark ‘X’ in cells where there is an entry. For example, final Group A has entries in the cells under the columns designated 0 and 8. Similarly, Group F has entries under columns 0, 1, 2 and 3. In this way, we fill the relevant cells with entries from groups A, B, C, D, E, F, and G as shown.

After having completed the filling of the cells, as explained above, we start the elimination process. In this elimination process, we have to remove the redundant terms (terms that have already been selected in various groups, and whose presence in the final logic expression will only add unnecessary extra gates). This is done as follows.

Let us first consider the larger groups. In the given problem, groups E and F are larger groups (quartets). Each group has two common entries in 2 and 3. But E and F differ in the remaining two entries. So, we choose them as essential and encircle all their members.

Next, we look for common terms in the paired groups of A, B, C, D, and E. We notice that, if we choose Group B with members 8 and 12, and Group F, we can eliminate Group A whose members are 0 and 8. This is because 0 is included in group F and 8 is included in Group B. We then score out the Group A with elements of 0 and 8. This process is repeated until all the redundant terms are eliminated, by visual inspection of the table. We find that groups A, C, and D are redundant. The selected groups are F, G, B, and E and we encircle them as selected groups. The final SOP expression can be obtained from these selected groups by the elimination process illustrated in the following

Example 13: Consider group F = 0, 1, 2, 3 (designated in decimal numbers). We now find the binary equivalent numbers of these decimal numbers and enter them one below the other, as shown in Table 2.14.

Table 2.14

 Decimal number Equivalent bits Equivalent variables 0 1 2 3 0  0  0  0 0  0  0  1 0  0  1  0 0  0  1  1 a′  b′  c′  d′ a′  b′  c′  d a′  b′  c  d′ a′  b′  c  d Reduced solution 0  0  – – a′  b′ – –

In the above example, we have written the binary and algebraic equivalents of decimal numbers 0, 1, 2, and 3, as shown. We then encircle the member elements in the vertical columnar groups, and eliminate those variables, which appear in complemented and uncomplemented forms. The resultant SOP expression is given by:
S = a′b′

This process is continued, as shown in Table 2.15 and the final SOP expression is obtained by combining the terms left in the right-most column of the table.
From Table 2.15, we obtain the reduced final SOP expression as:

S = a′ b′ + a′ c + a c′ d′ + a b d                (2.38)

Table 2.15 Reduction Method

 Final group Members (digits) Members (bits) Members  (variables) Reduced function F 0, 1, 2, 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 a′b′c′d′ a′b′c′d a′b′cd′ a′b′cd a′b′ G 2, 3, 6, 7 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 a′b′cd′ a′b′cd a′bcd′ a′bcd a′c B 8, 12 1 0 0 0 1 1 0 0 ab′c′d′ abc′d′ ac′d′ E 13, 15 1 1 0 1 1 1 1 1 abc′d abcd abd