Quine–McCluskey algorithm

The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952[1][2] and extended by Edward J. McCluskey in 1956.

[3] As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878,[4][5][6] was proved by Archie Blake in 1937,[7][8][9][6] and was rediscovered by Edward W. Samson and Burton E. Mills in 1954[10][6] and by Raymond J. Nelson in 1955.

[11][6] Also in 1955, Paul W. Abrahams and John G. Nordahl[12] as well as Albert A. Mullin and Wayne G. Kellner[13][14][15][16] proposed a decimal variant of the method.

[17][14][15][16][18][19][20][21] The Quine–McCluskey algorithm 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 F has been reached.

[22][23][24] The running time of the Quine–McCluskey algorithm grows exponentially with the number of variables.

For a function of n variables the number of prime implicants can be as large as

Functions with a large number of variables have to be minimized with potentially non-optimal heuristic methods, of which the Espresso heuristic logic minimizer was the de facto standard in 1995.

, the precise complexity of finding all prime implicants is better-understood: Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for finding all prime implicants of a formula in conjunctive normal form.

We encode all of this information by writing This expression says that the output function f will be 1 for the minterms

First, we write the function as a table (where 'x' stands for don't care): One can easily form the canonical sum of products expression from this table, simply by summing the minterms (leaving out don't-care terms) where the function evaluates to one: which is not minimal.

For instance 1000 and 1001 can be combined to give 100-, indicating that both minterms imply the first digit is 1 and the next two are 0.

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 (these are the ones that have been marked with a "*" in the previous step), and along the top go the minterms specified earlier.

If a column has only one "✓", this means that the minterm can only be covered by one prime implicant.

If a prime implicant is essential then, as would be expected, it is necessary to include it in the minimized boolean equation.

The simplest "additional procedure" is trial and error, but a more systematic way is Petrick's method.

In the current example, the essential prime implicants do not handle all of the minterms, so, in this case, the essential implicants can be combined with one of the two non-essential ones to yield one equation: or Both of those final equations are functionally equivalent to the original, verbose equation: The pseudocode below recursively computes the prime implicants given the list of minterms of a boolean function.

In this example the CheckDashesAlign and CheckMintermDifference functions perform the necessary checks for determining whether two minterms can be merged.

The pseudocode below can be split into two sections: The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corrresponding value is an empty string that will store a binary string once this step is complete.

Each bit in the binary string is used to represent the ticks within the prime implicant chart.

Using the function, CreatePrimeImplicantChart, defined above, we can find the essential prime implicants by simply iterating column by column of the values in the dictionary, and where a single "1" is found then an essential prime implicant has been found.

Using the algorithm above it is now possible to find the minimised boolean expression, by converting the essential prime implicants into the canonical form ie.

The pseudocode assumes that the essential prime implicants will cover the entire boolean expression.