Quine–McCluskey algorithm

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

3

n

/

n

{\displaystyle 3^{n}/{\sqrt {n}}}

, e.g. for 32 variables there may be over 534 × 1012 prime implicants. 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. For one natural class of functions

f

{\displaystyle f}

, 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.

Step two of the algorithm amounts to solving the set cover problem; NP-hard instances of this problem may occur in this algorithm step.

Example

Input

In this example, the input is a Boolean function in four variables,

f

:

{

0

,

1

}

4

→

{

0

,

1

}

{\displaystyle f:\{0,1\}^{4}\to \{0,1\}}

which evaluates to

1

{\displaystyle 1}

on the values

4

,

8

,

10

,

11

,

12

{\displaystyle 4,8,10,11,12}

and

15

{\displaystyle 15}

, evaluates to an unknown value on

Step 1: Finding the prime implicants

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:

fA,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

which is not minimal. So to optimize, all minterms that evaluate to one are first placed in a minterm table. Don't-care terms are also added into this table (names in parentheses), so they can be combined with minterms:

At this point, one can start combining minterms with other minterms in adjacent groups; as in, we compare minterms in nth group with (n+1)th group. So for the m4 minterm in with only one Number of 1s, we compare it to m9, m10, and m12 which have two Number of 1s.

If two terms differ by only a single digit, that digit is replaced with a dash indicating that the digit doesn't matter. 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. Terms that can't be combined any more are marked with an asterisk (*).

When going from Size 2 to Size 4, treat - as a third bit value. Match up the -'s first. The terms represent products and to combine two product terms they must have the same variables. One of the variables should be complemented in one term and uncomplemented in the other. The remaining variables present should agree. So to match two terms the -'s must align and all but one of the other digits must be the same. For instance, -110 and -100 can be combined to give -1-0, as can -110 and -010 to give --10, but -110 and 011- cannot since the -'s do not align. -110 corresponds to BCD' while

011- corresponds to A'BC, and BCD' + A'BC is not equivalent to a product term.

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 (these are the ones that have been marked with a "*" in the previous step), and along the top go the minterms specified earlier. The don't care terms are not placed on top—they are omitted from this section because they are not necessary inputs.

To find the essential prime implicants, we look for columns with only one "✓". If a column has only one "✓", this means that the minterm can only be covered by one prime implicant. This prime implicant is essential.

For example: in the first column, with minterm 4, there is only one "✓". This means that m(4,12) is essential (hence marked by #). Minterm 15 also has only one "✓", so m(10,11,14,15) is also essential. Now all columns with one "✓" are covered. The rows with minterm m(4,12) and m(10,11,14,15) can now be removed, together with all the columns they cover.

The second prime implicant can be 'covered' by the third and fourth, and the third prime implicant can be 'covered' by the second and first, and neither is thus essential. 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 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:

fA,B,C,D = BC'D' + AB' + AC

or

fA,B,C,D = BC'D' + AD' + AC

Both of those final equations are functionally equivalent to the original, verbose equation:

fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

Algorithm

Step 1: Finding the prime implicants

The pseudocode below recursively computes the prime implicants given the list of minterms of a Boolean function. It does this by trying to merge all possible minterms and filtering out minterms that have been merged until no more merges of the minterms can be performed and hence, the prime implicants of the function have been found.

// Computes the prime implicants from a list of minterms.

// each minterm is of the form "1001", "1010", etc and can be represented with a string.

function getPrimeImplicants(list minterms) is

primeImplicants ← empty list

merges ← new Boolean array of length equal to the number of minterms, each set to false

numberOfmerges ← 0

mergedMinterm, minterm1, minterm2 ← empty strings

for i = 0 to length(minterms) do

for c = i + 1 to length(minterms) do

minterm1 ← minterms[i]

minterm2 ← minterms[c]

// Checking that two minterms can be merged

if CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) then

mergedMinterm ← MergeMinterms(minterm1, minterm2)

if primeImplicants Does Not Contain mergedMinterm then

Step 2: Prime implicant chart

The pseudocode below can be split into two sections:

Creating the prime implicant chart using the prime implicants

Reading the prime implicant chart to find the essential prime implicants.

The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corresponding 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. The prime implicant chart can be created using the following steps:

Iterate through each key (prime implicant of the dictionary).

Replace each dash in the prime implicant with the \d character code. This creates a regular expression that can be checked against each of the minterms, looking for matches.

Iterate through each minterm, comparing the regular expression with the binary representation of the minterm, if there is a match append a "1" to the corresponding string in the dictionary. Otherwise append a "0".

Repeat for all prime implicants to create the completed prime implicant chart.

When written in pseudocode, the algorithm described above is:

function CreatePrimeImplicantChart(list primeImplicants, list minterms)

primeImplicantChart ← new dictionary with key of type string and value of type string

// Creating the empty chart with the prime implicants as the key and empty strings as the value.