The Quine McKluskey Algorithm
To simplify Boolean expressions we have generally used the Karnaugh map.
For practical purposes, the K-Map is limited to expressions of 5 variables or less.
Here we use 2 maps to simplify the expression:
Example: Minimise the following:
Like the K-map, the QM procedure uses the Boolean Law: xy +xy’ = x to find the prime implicants by comparing and combining adjacent product terms.
The method is essentially a tabular one using a sequence of lists and charts to eventually zero in on the minimum solution.
The method also uses the fact that the indices of adjacent minterms differ by a power of 2, since adjacent minterms differ by only 1 variable.
The QM procedure is as follows:
Step 1:
Create a list (LIST 1) of minterm indices, grouping them according to the number of 1’s they contain. Initially, the indices are written in binary but later we will perform the procedure using decimal indices.
Step2
Starting from group 0, compare each term in group I with the terms in group I+1, that is the adjacent group.
When two terms differ in one variable, put a mark (a tick will do) next to both terms.
The result of the combination is a term with all of the original variables but with a “-“ in the location of the variable that has been eliminated.
The new term is entered into a 2nd list (LIST 2). List 2 is completed when all possible comparisons from LIST 1 are performed.
Each group in LIST 2 (again grouped according to the number of 1’s the terms contain) corresponds to combinations between a single pair of terms in LIST 1
STEP 3
Continue the process with LIST 2 to generate LIST 3. Compare only terms in adjacent groups AND which have the same variables eliminated from STEP 2 (i.e. a “-“ in the same location)
Repeat the process until no more combinations are possible. If duplicate terms arise they can be discarded, but be sure to check the terms which are combined.
STEP 4
The unchecked terms in all of the lists represents the PIs of the function. The next step is to find the minimum cover.
This is done using a PI chart and identifying the essential PIs.
Consider the following example:
Simplify the function
F(w,x,y,z) = (0,1,2,8,10,11,14,15)
The binary equivalents of the minterms are shown in the following table:
Let us group them according to the number of 1’s in each number:
We now compare adjacent groups, Grp 0 with Grp 1, Grp1 with Grp 2 and so on to generate LIST 2.
The asterisks check off the terms which have been combined.
The interpretation is as follows. If we examine minterms 0 and 1, they are equivalent to w’x’y’z’ and w’x’y’z. These can be combined and simplified by eliminating the z variable to give w’x’y’.
Thus the 1st entry in LIST 2 which is 000-, is binary for w’x’y’ with the “-“ indicating the eliminated variable z.
LIST 2 is again grouped according to the number of 1’s in each term.
Adjacent groups are again combined, this time looking for terms with the “-“ in the same position. The adjacent groupings already ensure that the terms only differ by one variable.
Note that no combination was possible between Grp1 and Grp2, since none of the entries contained a “-“ in the same position.
We are left with 3 terms (the shaded entries) that cannot be combined further. The QM algorithm has terminated. What we are left with are the Prime Implicants of the function.
The minimized function is then:
F = w’x’y’ + x’z’ + wy
This can be compared with the answer obtained from the K-map technique.
Recall from Kmap theory that in order to ensure a minimal solution we had to identify the Essential Prime Implicants (EPIs).
From the map these were the sets of ones that were covered only by 1 prime implicant.
With the QM algorithm, a table called a PI chart is used to select the EPIs.
The chart tabulates the minterms in a row across the top of the table and the unchecked PIs in a column.
The chart is used of follows
1.In each row, place an “X” in the column corresponding to each minterm of the PI.
2.When all the PI minterms have been identified, find all the columns which just 1 “X”. Circle these X’s. The corresponding PIs are the Essential PIs. Check off these PIs.
3.Draw a line through each EPI and then a vertical line through each minterm covered by that EPI (the X’s in each row). These minterms are now covered and need not be considered any further.
4.The remaining PIs can now be selected to cover the remaining minterms. Each PI should be chosen to eliminate as many minterms as possible. Sometimes it is helpful to draw a second PI table containing the unselected minterms.
5.The minimal expression is now obtained from the EPIs and the remaining PIs from step 4
Applying these rules to our example:
PI / 0 / 1 / 2 / 8 / 10 / 11 / 14 / 150,1 / X / X /
0,2,8,10 / X / X / X / X / /
10,11,14,15 / X / X / X / X
The circles represent minterms that are covered by only one PI. The corresponding PI is an EPI.
PI / 0 / 1 / 2 / 8 / 10 / 11 / 14 / 150,1 / X / X /
0,2,8,10 / X / X / X / X / /
10,11,14,15 / X / X / X / X
When we draw a line through the minterms and horizontally through the PIs, in this example we cover all of the minterms. There is no need to develop a second table.
The answer obtained from the LISTs was in fact minimal.
Example 2: Minimise the following function using the QM algorithm:
f(a,b,c,d) = (0,1,2,5,6,7,8,9,10,14)
Step 1: We develop the lists based on the number of ones in each minterm, group them and eliminate those which differ by one literal.
Note that we have used decimal numbers. The procedure is the same in that numbers from adjacent sections are compared with those differing in a power of 2 being combined.
In List 2 both numbers are compared.
The PIs left are:
1,5 (4), / 0001 / a’c’d
5,7 (2), / 0101 / a’bd
6,7 (1); / 0110 / a’bc
0,1,8,9 (1,8) / 0000 / b’c’
0,2,8,10 (2,8) / 0000 / b’d’
2,6,10,14 (4,8) / 0010 / cd’
f = a’c’d + a’bd + a’bc + b’c’ + b’d’ + cd
Clearly this is not minimal. We go to the PI chart to determine the essential PIs
We must include (0,1,8,9) and (2,6,10,14).
We now need to cover minterms 5 and 7 which we see can be done with PI (5,7)
Hence the minimum solution is:
fmin = b’c’ + cd’ + a’bd
Example 3
Minimize the following function:
.f(a ,b, c, d)=m(0,1,3,5,13,15) +d(2,6,10,11,12)
Here we treat all don’t cares as minterms and include them in the first part of the process of determining the complete set of PIs.
However, we do not include the don’t care terms in the minterm list of the PI chart
Attempt in class
© 2001QMA1