Quine–McCluskey algorithm

The Quine–McCluskey algorithm is a method used for minimization of boolean functions. It is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.

The method involves two steps:

Finding all prime implicants of the function.
Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.

Complexity

Although more practical than Karnaugh mapping when dealing with more than four variables, the Quine-McCluskey algorithm also has a limited range of use since the problem it solves is NP-complete: the runtime of the Quine-McCluskey algorithm grows exponentially with the input size. It can be shown that for a function of n variables the upper bound on the number of prime implicants is 3ⁿ/n. If n = 32 there may be over 6.1 * 10¹⁴, or 617 trillion prime implicants. Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods.

Example

Step 1: finding prime implicants

Minimizing an arbitrary function:

f(A, B, C, D) =

\Sigma

(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:

$f_{A,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(8,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-     |

Step 2: prime implicant chart

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 minimized boolean equation. In some cases, the essential prime implicants do not cover all minterms, in which case additional procedures for chart reduction can be employed. The simplest "additional procedure" is trial and error, but a more systematic way is Petrick's Method. In this case, the essential prime implicants handle all of the minterms, so then, the combined minterms are just summed to give this equation:

$f_{A,B,C,D}=BC'D'+AB'+AC$

The final equation is functionally equivalent to this original (very area-expensive) equation: