Quine-McCluskey algorithm (Java)

From LiteratePrograms

The Quine-McCluskey algorithm is a two-level logic minimization method. It takes a boolean formula and attempts to reduce it to an equivalent, more succinct boolean formula. For example, suppose A, B and C are boolean variables, and the logical negation of X is written as $\bar{X}$ . Then we could reduce this boolean formula f:

$f(A,B,C) = \bar{A}\bar{B}\bar{C} + \bar{A}B + AB\bar{C} + AC$

To this equivalent formula:

$f(A,B,C) = B + AC + \bar{A}\bar{C}$

This boolean formula minimization problem is also solved by Karnaugh maps, but in a less systematic and scalable way.

1 Formula representation
2 The resolution rule
3 Finding the prime implicants
4 Finding a covering set
5 Sample code
6 References

[edit]

Formula representation

We will represent each term of a boolean formula by a simple array of bytes. Array position i will correspond to variable i, and each may have one of three values:

One (1), indicating the variable holds;
Zero (0), indicating the negation of the variable holds;
DontCare, indicating that the variable is not present in the term and so can assume either value.

We represent a formula as a simple ArrayList of its term arrays. For example, we could construct the example formula above using this code:

ArrayList<byte[]> formula = new ArrayList<byte[]>();
byte[] t1 = {0,        0,        0       };
byte[] t2 = {0,        1,        DontCare};
byte[] t3 = {1,        1,        0       };
byte[] t4 = {1,        DontCare, 1       };
formula.add(t1);
formula.add(t2);
formula.add(t3);
formula.add(t4);

We create simple Term and Formula classes to wrap this state and define the DontCare constant:

<<Term.java>>=
import java.util.*;
Term import statements

class Term {
    public static final byte DontCare = 2;

    public Term(byte[] varVals) {
        this.varVals = varVals;
    }

    public int getNumVars() {
        return varVals.length;
    }

    Term public methods

    private byte[] varVals;
}

<<Formula.java>>=
import java.util.*;
Formula import statements

class Formula {
    public Formula(List<Term> termList) {
        this.termList = termList;
    }

    Formula public methods

    Formula helper methods

    private List<Term> termList;
    additional Formula data members

    Formula test main
}

Note that this code uses generics (List<Term>), a relatively new Java feature only available in version 1.5.0 and above. To use it with older versions of Java, remove all the "<Term>" marks.

For debugging convenience we also add simple functions to convert each of these types to strings:

<<Term public methods>>=
public String toString() {
    String result = "{";
    for(int i=0; i<varVals.length; i++) {
        if (varVals[i] == DontCare)
            result += "X";
        else
            result += varVals[i];
        result += " ";
    }
    result += "}";
    return result;
}

<<Formula public methods>>=
public String toString() {
    String result = "";
    result += termList.size() + " terms, " + termList.get(0).getNumVars() + " variables\n";
    for(int i=0; i<termList.size(); i++) {
        result += termList.get(i).toString() + "\n";
    }
    return result;
}

[edit]

The resolution rule

The Quine-McCluskey algorithm relies fundamentally on the resolution rule of propositional logic, which states that if F is a boolean formula and A is a boolean variable, then:

$(F \vee A) \wedge (F \vee \bar{A}) \equiv F$

In the bit representation, we can use this formula to combine two terms if:

They are identical except for one position, and
That one position is 0 in one term and 1 in the other.

For example:

{0, 0, DontCare, 1}, {0, 1, DontCare, 1} -> {0, DontCare, DontCare, 1}

We can write a method to check the conditions and perform the combination given two terms:

<<Term public methods>>=
public Term combine(Term term) {
    int diffVarNum = -1; // The position where they differ
    for(int i=0; i<varVals.length; i++) {
        if (this.varVals[i] != term.varVals[i]) {
            if (diffVarNum == -1) {
                diffVarNum = i;
            } else {
                // They're different in at least two places
                return null;
            }
        }
    }
    if (diffVarNum == -1) {
        // They're identical
        return null;
    }
    byte[] resultVars = varVals.clone();
    resultVars[diffVarNum] = DontCare;
    return new Term(resultVars);
}

At a high level, Quine-McClusky has three basic steps:

Apply this rule many times to produce smaller terms until no more can be produced.
Identify the terms that cannot be combined with any other term to produce a smaller term. We call these the prime implicants.
Select a subset of these prime implicants that implies all of the original terms.

[edit]

Finding the prime implicants

A naive implementation would examine every pair of terms, applying the rule wherever it can until it's performed all possible reductions. We can cut down the search dramatically by noting two facts:

Any two terms satisfying the conditions must have the same number of DontCare terms, since their only allowed difference is required to involve 0 and 1.
Given any two terms satisfying the conditions, one of them must have exactly one more 1 than the other.

To take advantage of these, we rearrange the data into a two-dimensional table of lists. This table has the property that each term falling in the list located at index table[i][j] has i DontCares and j 1 bits. We set it up like this:

<<create term table>>=
int numVars = termList.get(0).getNumVars();
ArrayList[][] table = new ArrayList[numVars + 1][numVars + 1];
for(int dontKnows=0; dontKnows <= numVars; dontKnows++) {
    for(int ones=0; ones <= numVars; ones++) {
        table[dontKnows][ones] = new ArrayList();
    }
}
for(int i=0; i<termList.size(); i++) {
    int dontCares = termList.get(i).countValues(Term.DontCare);
    int ones      = termList.get(i).countValues((byte)1);
    table[dontCares][ones].add(termList.get(i));
}

We add one to the array dimensions so that the indexes can take on all values between zero and numVars, inclusive. The countValues method on Term simply determines how many variables have the specified value:

<<Term public methods>>=
public int countValues(byte value) {
    int result = 0;
    for(int i=0; i<varVals.length; i++) {
        if (varVals[i] == value) {
            result++;
        }
    }
    return result;
}

Now, we only need to attempt to combine terms falling into lists that are next to each other in the table. We still have to try all combinations of these two lists, but hopefully they will be short. If we find a pair of terms that can be combined, we know where its result will go in the table: it will have one more DontKnow than the input terms and a number of ones equal to the lesser of the number of ones in the two input terms. This is critical not only to avoid unnecessary counting, but also because it tells us that we can make a single scan from top to bottom and find all possible combinations: no table entry that we've already visited will be modified.

<<generate new terms with combine() while updating prime implicant list>>=
for(int dontKnows=0; dontKnows <= numVars - 1; dontKnows++) {
    for(int ones=0; ones <= numVars - 1; ones++) {
        ArrayList<Term> left   = table[dontKnows][ones];
        ArrayList<Term> right  = table[dontKnows][ones + 1];
        ArrayList<Term> out    = table[dontKnows+1][ones];
        for(int leftIdx = 0; leftIdx < left.size(); leftIdx++) {
            for(int rightIdx = 0; rightIdx < right.size(); rightIdx++) {
                Term combined = left.get(leftIdx).combine(right.get(rightIdx));
                if (combined != null) {
                    if (!out.contains(combined)) {
                        out.add(combined); 
                    }
                    update prime implicant list
                }
            }
        }
    }
}

Once we've found two terms that can be combined, we know that neither of them is a prime implicant. We keep track of this as we go by removing the two input terms from termList and adding their combination:

<<update prime implicant list>>=
termList.remove(left.get(leftIdx));
termList.remove(right.get(rightIdx));
if (!termList.contains(combined)) {
    termList.add(combined);
}

When we're done, the list will contain only prime implicants.

For the contains() call above to work correctly, we must ensure that equals() has the correct semantics on Term:

<<Term public methods>>=
public boolean equals(Object o) {
    if (o == this) {
        return true;
    } else if (o == null || !getClass().equals(o.getClass())) {
        return false;
    } else {
        Term rhs = (Term)o;
        return Arrays.equals(this.varVals, rhs.varVals);
    }
}

Whenever overriding equals(), we must override hashCode() accordingly:

<<Term public methods>>=
public int hashCode() {
    return varVals.hashCode();
}

We place the functionality discussed in this section in a method on Formula, below. Because we'll need the original terms in the next section, we save them first.

<<additional Formula data members>>=
private List<Term> originalTermList;

<<Formula public methods>>=
public void reduceToPrimeImplicants() {
    originalTermList = new ArrayList<Term>(termList);
    create term table
    generate new terms with combine() while updating prime implicant list
}

[edit]

Finding a covering set

Our next goal is to find a subset of the prime implicants that imply all the terms of the original formula. The first step is to exhaustively test which of the original terms are implied by which of the prime implicants. To determine if a term A implies another term B, we need only ensure that all variables set to 0 or 1 in A are set the same in B; for example, {DontCare, 1, 0, DontCare} implies {0, 1, 0, DontCare}. We implement this test with a new method on Term:

<<Term public methods>>=
boolean implies(Term term) {
    for(int i=0; i<varVals.length; i++) {
        if (this.varVals[i] != DontCare &&
            this.varVals[i] != term.varVals[i]) {
            return false;
        }
    }
    return true;
}

We use this to construct our new table, a two-dimensional array of booleans where table[i][j] is true only if implicant number i implies original term number j:

<<create implies table>>=
int numPrimeImplicants = termList.size();
int numOriginalTerms   = originalTermList.size();
boolean[][] table = new boolean[numPrimeImplicants][numOriginalTerms];
for (int impl=0; impl < numPrimeImplicants; impl++) {
    for (int term=0; term < numOriginalTerms; term++) {
        table[impl][term] = termList.get(impl).implies(originalTermList.get(term));
    }
}

At this point, we are looking at an instance of the NP-hard set cover problem. The only known complete solutions to this problem are exponential, but there are also simple and effective heuristic strategies that are more efficient.

If at any point a particular original term is implied only by a single implicant, we call that an essential prime implicant and we must use it. We remove both the row corresponding to the essential prime implicant and the columns of all original terms implied by it, since these are taken care of. We continue doing this until every remaining term is implied by multiple prime implicants.

<<Formula helper methods>>=
private int extractEssentialImplicant(boolean[][] table) {
    for (int term=0; term < table[0].length; term++) {
        int lastImplFound = -1;
        for (int impl=0; impl < table.length; impl++) {
            if (table[impl][term]) {
                if (lastImplFound == -1) {
                    lastImplFound = impl;
                } else {
                    // This term has multiple implications
                    lastImplFound = -1;
                    break;
                }
            }
        }
        if (lastImplFound != -1) {
            extractImplicant(table, lastImplFound);
            return lastImplFound;
        }
    }
    return -1;
}

The extractImplicant method takes clear of zeroing out the row and columns associated with the given implicant. It only needs to zero the columns, since this takes care of the row as well (every column containing a true in that row is cleared).

<<Formula helper methods>>=
private void extractImplicant(boolean[][] table, int impl) {
    for (int term=0; term < table[0].length; term++) {
        if (table[impl][term]) {
            for (int impl2=0; impl2 < table.length; impl2++) {
                table[impl2][term] = false;
            }
        }
    }
}

Finally, we cover the remaining original terms using the remaining prime implicants. There are couple different possible strategies to take:

Backtracking search: at each step we try all possible choices, using the "essential prime implicant" rule above to reduce where possible. Once a solution is found we backtrack to the last decision point with choices remaining and try the next choice. This is a slow, exponential-time solution, but will always give a minimum-size (optimal) formula. After finding all possible solutions, we choose the smallest one. We do not currently implement this solution.

Heuristic selection: Whenever faced with a decision, we choose the prime implicant that implies the largest number of remaining original terms. Again, we use the "essential prime implicant" rule to reduce where possible. It can be proven that the resulting solution is at most ln n times larger than the optimal (minimum) solution, where n is the largest number of original terms implied by any one prime implicant.

<<Formula helper methods>>=
private int extractLargestImplicant(boolean[][] table) {
    int maxNumTerms = 0;
    int maxNumTermsImpl = -1;
    for (int impl=0; impl < table.length; impl++) {
        int numTerms = 0;
        for (int term=0; term < table[0].length; term++) {
            if (table[impl][term]) {
                numTerms++;
            }
        }
        if (numTerms > maxNumTerms) {
            maxNumTerms = numTerms;
            maxNumTermsImpl = impl;
        }
    }
    if (maxNumTermsImpl != -1) {
        extractImplicant(table, maxNumTermsImpl);
        return maxNumTermsImpl;
    }
    return -1;
}

<<extract implicants heuristically until done>>=
ArrayList<Term> newTermList = new ArrayList<Term>();
boolean done = false;
int impl;
while (!done) {
    impl = extractEssentialImplicant(table);
    if (impl != -1) {
        newTermList.add(termList.get(impl));
    } else {
        impl = extractLargestImplicant(table);
        if (impl != -1) {
            newTermList.add(termList.get(impl));
        } else {
            done = true;
        }
    }
}
termList = newTermList;

It's also possible to have intermediate solutions that combine heuristics with limited search - but a solution that is at once optimal and polynomial time is not achievable unless P=NP.

We place this functionality in another method on Formula, which will contain a reduced formula when it returns:

<<Formula public methods>>=
public void reducePrimeImplicantsToSubset() {
    create implies table
    extract implicants heuristically until done
    originalTermList = null;
}

[edit]

Sample code

We define a couple methods that allow Formula and Term to read themselves from a stream. In order for the algorithm to function correctly we don't allow don't-cares in the input, but these are easy to eliminate by just enumerating all possible combinations.

<<Term public methods>>=
public static Term read(Reader reader) throws IOException {
    int c = '\0';
    ArrayList<Byte> t = new ArrayList<Byte>();
    while (c != '\n' && c != -1) {
        c = reader.read();
        if (c == '0') {
            t.add((byte)0);
        } else if (c == '1') {
            t.add((byte)1);
        }
    }
    if (t.size() > 0) {
        byte[] resultBytes = new byte[t.size()];
        for(int i=0; i<t.size(); i++) {
            resultBytes[i] = (byte)t.get(i);
        }
        return new Term(resultBytes);
    } else {
        return null;
    }
}

<<Formula public methods>>=
public static Formula read(Reader reader) throws IOException {
    ArrayList<Term> terms = new ArrayList<Term>();
    Term term;
    while ((term = Term.read(reader)) != null) {
        terms.add(term);
    }
    return new Formula(terms);
}

These I/O classes require an import statement:

<<Formula import statements>>=
import java.io.*;

<<Term import statements>>=
import java.io.*;

Now we invoke this code from the test main function, which simply opens a file stream based on the command-line arguments and passes it in to Formula.read():

<<Formula test main>>=
public static void main(String[] args) throws IOException {
    Formula f = Formula.read(new BufferedReader(new FileReader(args[0])));
    f.reduceToPrimeImplicants();
    System.out.println(f.toString());
    f.reducePrimeImplicantsToSubset();
    System.out.println(f.toString());
}

We print out the formula both after reduction to prime implicants and after the final result is found. We try the code on the formula first given at the top of the article. If we expand out all the don't-cares, we get this input file:

<<input_example.txt>>=
000
010
011
110
101
111

The output corresponds precisely to the reduced form given at the top of the article:

3 terms, 3 variables
{0 X 0 }
{1 X 1 }
{X 1 X }

3 terms, 3 variables
{0 X 0 }
{X 1 X }
{1 X 1 }

Next, we try the code on a sample borrowed from George Vastianos' article on Quine-McCluskey (see references) containing 11 terms, each involving 4 variables. Here's the input file:

<<vastianos_example_1.3.txt>>=
0000
0001
0010
0011
0101
0111
1000
1010
1100
1101
1111

This is just an enumeration of all states which should yield true, fully expanded. The output, as we expect, is:

6 terms, 4 variables
{1 X 0 0 }
{1 1 0 X }
{0 0 X X }
{X 0 X 0 }
{0 X X 1 }
{X 1 X 1 }

4 terms, 4 variables
{X 0 X 0 }
{X 1 X 1 }
{0 0 X X }
{1 X 0 0 }

The first 6 terms are the prime implicants. The last 4 terms are the minimal reduced formula, corresponding to:

$f(A,B,C,D) = \bar{B}\bar{D} + BD + \bar{A}\bar{B} + A\bar{C}\bar{D}$

The code was executed on Sun's Java 1.5.0 under Gentoo Linux on a 2.8 GhZ Pentium 4 machine. Total runtime was 0.096 seconds. If we try a larger example, such as Vastianos's Minimisation example 4 (section 2.3.1.4) with 64 terms of 64 variables each, it still takes only 0.159 seconds, scaling quite well. The reduced formula it produces has 18 terms, the same number found by Vastianos' program.

[edit]