| minterm | binary | № of 1's |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 1 |
| 3 | 0011 | 2 |
| 6 | 0110 | 2 |
| 7 | 0111 | 3 |
| 8 | 1000 | 1 |
| 9 | 1001 | 2 |
| 14 | 1110 | 3 |
| 15 | 1111 | 4 |
| Group | minterm | abcd | № 1's |
|---|---|---|---|
| 0 | 0 | 0000 | 0 |
| 1 | 1 2 8 | 0001 0010 1000 | 1 |
| 2 | 3 6 9 | 0011 0110 1001 | 2 |
| 3 | 7 14 | 0111 1110 | 3 |
| 4 | 15 | 1111 | 4 |
The Quine McCluskey method is preferable for boolean expressions with a large number of variables, beyond five variables other method becomes very unwieldy and difficult to manage.
Although the k-map or karnaugh map is by far the simpler method for obtaining an optimal boolean expression and the Quine McCluskey technique, in comparison, is really quite unwieldy involving the use of several tables and a process of mathematical deduction, never the less, as a systematic procedure it greatly reduces the complexity of the process of finding an optimal boolean expression, and it is far more effective than the karnaugh method when dealing with more complicated logic.
Our expression is a boolean function in four variables, which evaluate to 1 on the values 0,1,2,3,6,7,8,9,14,15. Our variables will be expressed in their binary form for succinctness. This expression effectively says that the output function f will be 1 for the given minterms.
f(a,b,c,d) = Σ m(0,1,2,3,6,7,8,9,14,15)
Our first step is to write out a table of our minterms and count the 1's required for each binary representation:
| minterm | binary | № of 1's |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 1 |
| 3 | 0011 | 2 |
| 6 | 0110 | 2 |
| 7 | 0111 | 3 |
| 8 | 1000 | 1 |
| 9 | 1001 | 2 |
| 14 | 1110 | 3 |
| 15 | 1111 | 4 |
| Group | minterm | abcd | № 1's |
|---|---|---|---|
| 0 | 0 | 0000 | 0 |
| 1 | 1 2 8 | 0001 0010 1000 | 1 |
| 2 | 3 6 9 | 0011 0110 1001 | 2 |
| 3 | 7 14 | 0111 1110 | 3 |
| 4 | 15 | 1111 | 4 |
The next table will be generated by matching the minterms in group n with the minterms in group n+1, whilst following some simple rules for when to negate a term and how to formulate the new resultant expression. The two terms should not differ in any more than one position. In comparing terms if there is one difference between the two values, only then do we transfer that term to our new table, the digit that differed will now be represented by a dash. The reason for this will become clear as we explore how this allows us to remove variables from each logical term that is transferred.
For our first comparison we have 0000 compared to 0001, which in boolean algebra appears as follows:
a·b·c·d + a·b·c·d = a·b·c·(d+d) = a·b·c
Which we write into the table as 000_ seen in the third cell of the first row of our next table. Moving onto the second row in the comparison between minterm 1 and 6 we find our first instance of a term that can not be transferred, there are three digits that differ between these expressions, as such we must ignore them and we will not include (1,6) in the new table. It can be useful whilst making these tables to tick off terms as they are used as we will need to insure that every term is used at some point.
| Group | minterm | abcd |
|---|---|---|
| 0 | (0,1) (0,2) (0,8) | 000_ 00_0 _000 |
| 1 | (1,3) (1,9) (2,3) (2,6) (8,9) | 00_1 _001 001_ 0_10 100_ |
| 2 | (3,7) (6,7) (6,14) | 0_11 011_ _110 |
| 3 | (7,15) (14,15) | _111 111_ |
Once the table is complete we can check off all of our terms by ticking them to see that none have been missed, if a term has not been checked off, then it will need to be kept aside as it will be required in our final table.
Again we make a new table, performing the same operations to generate each term excepting that this time we must also check the position of the dash, representing a previously coupled pair of digits, therefore the dash must also be in the same position in both terms, for it not to be counted as a difference. Once again we look for expressions in which only one digit differs between the two.
| Group | minterm | abcd |
|---|---|---|
| 0 | (0,1,2,3) (0,1,8,9) | 00__ _00_ |
| 1 | (2,3,6,7) | 0_1_ |
| 2 | (6,7,14,15) | _11_ |
Whilst making this table we might observe that the grouping (0,2,1,3) does generate a term, however as it is the case that all of the variables within this term have already been used, we have no need to write it down, but we can tick the term off of our list; The same goes for (0,8,1,9). This completes our table and there are no further reduction by the grouping of temrs that can be made so no other table is required. There may be cases where another table could have been used here.
Moving on to the next step, this next table is known as the prime implicant table. The first thing that we need to add to this final table are any of the groups from any of the previous tables that have not yet been ticked. As in our example we do not have any un-ticked terms in any of our previous tables, and all of the terms in the last table are as expected, irreducible; we will now move these over to our prime implicant table.
The next step is to mark any of the variables which appear in the table in only one term thus only one single appearance, we will put a tick next to the term and a ring around the X, these particular prime implicants are essential and will be used in the final expression. We can now go on to mark any of the variables contained within these terms by putting a red dash through them in the table header, these have already been included in the expressoin and as such are no longer expressly required.
| PI | minterm | 0 | 1 | 2 | 3 | 6 | 7 | 8 | 9 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a·b | (0,1,2,3) | X | X | X | X | ||||||
| b·c | (0,1,8,9) | X | X | X | X | ||||||
| a·c | (2,3,6,7) | X | X | X | X | ||||||
| b·c | (6,7,14,15) | X | X | X | X |
| P1 | minterm | 2 | 3 |
|---|---|---|---|
| a·b | (0,1,2,3) | X | X |
| a·c | (2,3,6,7) | X | X |
From this table we generate a reduced prime implicant table in which we put only those variables that have not been highlighted in the previous tables' header and transfer over to this any terms that reference any or all of those variables.
To arrive at our final answer we will take all the essential prime implicate terms previously marked with a tick along with any terms in our final table such that we have include all of the specified variables, in our case we can choose either one of two terms, both cover all of the variables. From these we can construct our final expression; Which could be either one of the following:
b·c+b·c+a·b
orb·c+b·c+a·c
In order to prove that this method has worked, we can also solve this using the k-map method, note that the cells have been numbered with subscript numerals to denote our variables, whereas the order of the k-map is defined using grey code.
| cd | |||||
|---|---|---|---|---|---|
| ab | 00 | 01 | 11 | 10 | |
| 00 | 1 ₀ | 1 ₁ | 1 ₃ | 1 ₂ | |
| 01 | 0 ₄ | 0 ₅ | 1 ₇ | 1 ₆ | |
| 11 | 0 ₁₂ | 0 ₁₃ | 1 ₁₅ | 1 ₁₄ | |
| 10 | 1 ₈ | 1 ₉ | 0 ₁₁ | 0 ₁₀ | |
b·c + b·c + a·b
f(w,x,y,z) = Σm(1,3,13,15) + Σd(8,9,10,11)
We need to know how to deal with expressions when they comprise of variables in which we have no interest, or otherwise said, 'don't care' terms. We will start by laying out our terms for reference again. This time we will clearly separate those minterms in which we have an interest and those about which we do not care, marking each with an asterisk.
| minterm | wxyz | № of 1's |
|---|---|---|
| 1 | 0001 | 1 |
| 3 | 0011 | 2 |
| 13 | 1101 | 3 |
| 15 | 1111 | 4 |
| 8* | 1000 | 1 |
| 9* | 1001 | 2 |
| 10* | 1010 | 2 |
| 11* | 1011 | 3 |
| Group | minterm | wxyz | № of 1's |
|---|---|---|---|
| 1 | 1 8* | 0001 1000 | 1 |
| 2 | 3 9* 10* | 0011 1001 1010 | 2 |
| 3 | 13 11* | 1101 1011 | 3 |
| 4 | 15 | 1111 | 4 |
Once again we redefine our table using the terms ordered by the number of 1's in each binary word, in increasing order, then we precede to move over to the next table any variables in adjacent groups that differ by no more than one digit.
| Group | minterm | wxyz |
|---|---|---|
| 1 | (1,3) (1,9*) (8*,9*) (8*,10*) | 00_1 _001 100_ 10_0 |
| 2 | (3,11*) (9*,13) (9*,11*) (10*,11*) | _011 1_01 10_1 101_ |
| 3 | (13,15) (11*,15) | 11_1 1_11 |
| Group | minterm | wxyz |
|---|---|---|
| 1 | (1,3,9*,11*) (8*,9*,10*,11*) | _0_1 10__ |
| 2 | (9*,13,11*,15) | 1__1 |
The expressions (1,9*,3,11*) and (8*,10*,9*,11*) already have all of their terms grouped in our next table, so there is no need for us to rewrite it, but still put a tick beside the terms used, to denote having observed them and any others that similarly have already been covered. Once our table is formed we can then check to see whether any groups of eight terms can be made, for this we would require that two underscores be found in the same place in two expressions.
From these tables we can now form our first prime implicant table, this time we will not write any of the exclusivly don't care terms. As none of our terms in previous tables priorto the last have not been ticked, we will not need to bring in any terms from those. Our second minterm expression in the last table is comprised of only terms that we do not care about and as such we will ignore it, using only those expressions that contain the terms that we are intersted by.
| PI | minterm | 1 | 3 | 13 | 15 |
|---|---|---|---|---|---|
| x·z | (1,3,9*,11*) | X | X | ||
| w·z | (9*,13,11*,15) | X | X |
f(w,x,y,z) = x·z + w·z
Once again to be certain of this method, we will check our result against a k-map. Here 'd' represents variables that we do not care about and _ are simply not in the expression.
| yz | |||||
|---|---|---|---|---|---|
| wx | 00 | 01 | 11 | 10 | |
| 00 | _ ₀ | 1 ₁ | 1 ₃ | _ ₂ | |
| 01 | _ ₄ | _ ₅ | _ ₇ | _ ₆ | |
| 11 | _ ₁₂ | 1 ₁₃ | 1 ₁₅ | _ ₁₄ | |
| 10 | d ₈ | d ₉ | d ₁₁ | d ₁₀ | |
x·z + w·z