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 onebit 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 2^{0}, 0 and 2 differ by 2^{1}, and 0 and 8 differ by 2^{3}. 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
differenceinonebitpositiononly. 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

P_{1}

0,
1
0,
2
0,
8

1 – 0 = 1
2 – 0 = 2
8 – 0 = 8

2^{0}
2^{1}
2^{3}

Q_{1}

1,
3
2,
3
2,
6
8,
12

3 – 1 = 2
3 – 2 = 1
6
– 2 = 4
12 – 8 = 4

2^{1}
2^{0}
2^{2}
2^{2}

R_{1}

3, 7
6, 7
12, 13

7 – 3 = 4
7 – 6 = 1
13 – 12 = 1

2^{2}
2^{0}
2^{0}

S_{1}

7, 15
13, 15

15 – 7 = 8
15 – 13 = 2

2^{3}
2^{1}

Step 3: In Step
3, we make still lager pairings. For example, a pair from group P_{1} can be combined with a
pair from the adjacent group Q_{1}
if they differ by a power of 2. Thus, in
Chart 3, the pair (0, 1) of Group P_{1}
can be combined with the pair (2, 3) from Group Q_{1}, as they differ by the same power of 2 (i.e., 2^{0
}= 1) between individual members and by 2^{1} between the pairs.
That is, between 0 and 1, the difference is 2^{0} (= 1); between 2 and 3, difference is
2^{0} (= 1).
Now, to find the second condition, i.e., the difference between
pairs, take any member in pair P_{1},
say 0. We now find the difference between 0 and 2, its corresponding member in
pair Q_{1}. The difference can be seen to be equal to 2
(=2^{1}). Since the pairs (0, 1)
and (2, 3) have satisfied our two conditions, we can combine them to form a quad
P_{2}. 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 P_{2}
and Q_{2} 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 P_{2} differ
by a factor of 1 (= 2^{0}) between them. Thus we observe that 0, 1, 2,
and 3 differ by 1 from each
other. Now, consider the members in
Group Q_{2}. 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 1differencebetweenadjacent
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
rightmost 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
