Quine-McCluskey algorithm is a method used for minimisation of Boolean functions. It is functionally identical to
Karnaugh mapping, but the tabular form makes it more convenient for computers, and it also gives a
deterministic way to check that the minimal form of a boolean function has been reached
The method involves two steps:
- Finding all prime implicants of the function.
- Using those prime implicants to find the essential prime implicants of the function, as well as using other prime
implicants that are necessary to cover the function.
Here's an example minimizing an arbitrary function:
- f(A, B, C, D) = Σ(4, 8, 9, 10, 11, 12, 14, 15)
A B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 1
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 1
m15 1 1 1 1 1
One can easily form the canonical sum-of-products expression from this table, simply by summing the minterms where the
function evaluates to one:
fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD
Of course, that's certainly not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm
table:
Number of 1s Minterm Binary Representation
--------------------------------------------
1 m4 0100
m8 1000
--------------------------------------------
2 m9 1001
m10 1010
m12 1100
--------------------------------------------
3 m11 1011
m14 1110
--------------------------------------------
4 m15 1111
At this point, one can start combining minterms with other minterms. If two terms vary by only a single digit changing, that
digit can be replaced with a dash indicating that that digit doesn't matter. Terms that can be combined no more are marked
with a "*".
Number of 1s Minterm 0-Cube | Size 2 Implicants | Size 4 Implicants
------------------------------|-------------------|----------------------
1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--*
m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0*
------------------------------| m(9,10) 10-0 |----------------------
2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-*
m10 1010 |-------------------|
m12 1100 | m(9,11) 10-1 |
------------------------------| m(10,11) 101- |
3 m11 1011 | m(10,14) 1-10 |
m14 1110 | m(12,14) 11-0 |
------------------------------|-------------------|
4 m15 1111 | m(11,15) 1-11 |
| m(14,15) 111- |
None of the terms can be combined any further than this, so at this point we construct an essential prime implicant table. Along the side goes the prime implicants that have just been generated, and along the top go the minterms specified earlier.
| | 4 | 8 | 9 | 10 | 11 | 12 | 14 | 15
|
| m(4,12)* | X | | | | | X | |
|
| m(8,9,10,11)* | | X | X | X | X | | |
|
| m(8,10,12,14) | | X | | X | | X | X |
|
| m(10,11,14,15)* | | | | X | X | | X | X
|
Here, each of the essential prime implicants has been starred. If a prime implicant is essential then, as would be expected, it is necessary to include it in the mininimized boolean equation. In this case, the EPIs handle all of the minterms, so then, the combined minterms are just summed to give this equation:
fA,B,C,D = BC'D' + AB' + AC
Which is equivalent to this original (very large) equation:
fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD
See also
External links