Fixing a Quine-McCluskey Implementation

Overview

In this exercise you will start with most of a Quine-McCluskey implementation in Java, and fill in a few parts to make it work properly. The code can be downloaded here (Correct version of Quine.java) (More heavily commented version of all the code here). There are three places where I have erased code that you will need to repair. Here is a brief description of what you will find in each of the files.

Quine.java: This is the top level file that has the code for reading a Boolean function from standard input, passing it to the appropriate code to build a table and compute a minimum cover, then finally print out the Boolean expression for the cover.
ImplicationTable.java: This file has the code that defines the implication table and the method for reading the prime implicants out of the table. An implication table is just a list of columns.
Column.java: This file contains the code for building the initial column of the table from a list of terms, and the code for building later columns from earlier columns.
Group.java: A column is composed of groups. Each group is a set of implicants, where all implicants contain the same number of 1's (but perhaps different numbers of dashes). This file contains part of the code needed to merge two adjacent groups from column N to make one group in column N+1.
Implicant.java: Implicants are implemented as lists of "bits", where each bit corresponds to an input variable. Each bit can be either one, zero or "both" (represented as a dash in the prime implicant charts in the book). This file contains code for comparing and combining implicants in various ways.
Bit.java: This is the interface for bits.
BitZero.java, BitOne.java, BitBoth.java: These three files contain implementations for the different kinds of bits. Each implements methods for comparing and combining individual bits, which are used in the comparison and combination of implicants.
PrimImplicantChart.java: This file contains the definition of the prime implicant chart. It also contains the code for picking a subset of the prime implicants that still cover the input function.

Interface and Technical Details

On departmental Linux machines, you can compile the minimizer by typing:

javac *.java

at the command line, after untaring the package.

The program expects it's input on standard input, so if you have a Boolean function specification in file "fun.txt", you can run the minimizer on it by typing:

java Quine < fun.txt

at the command line.

echo "3 M 1 4 5 D 2" | java Quine

also works, as does simply typing

java Quine

and then typing the function. If you use this last method, you have to finish with "ctrl-d", which is the end-of-file key combination.

The format of the function specifications is:

[Num Variables] m/M [Term]+ {d/D [Term]+}

Where "Num Variables" and "Term" are just integers. The former determines how many input variables the function takes, and the [Term]+ numbers determine which min/max terms and don't cares are included in the function. The m or M determines whether the function is given in minterm or maxterm notation. A complete example for a function that takes a BCD number encoded in the usual way and returns true iff it is between 3 and 6, inclusive.

4 m 3 4 5 6 d 10 11 12 13 14 15

The minimizer should produce output that looks like:
Corrected variable order version:

(B~D)+(~BCD)+(B~C)

or, this, for maxterm style inputs:

(B+D)(B+C)(~B+~C+~D)

Old, incorrect variable order version:

(~AC)+(AB~C)+(~BC)

or, this, for maxterm style inputs:

(A+C)(B+C)(~A+~B+~C)

What You Have to Do

I have removed three critical bits of code from my working version of the Quine-McCluskey minimizer:

Line 30 of Implicant.java
Line 41 of ImplicantionTable.java. Notice that the algorithm here for finding the prime implicants is slightly different from that described in the book and in lecture. Instead of marking the table with check marks and stars as the implicant minimization proceeds, we simply fill up the table with implicants, and then process it from right to left, ensuring that we only add the prime implicants to our set of primes.
Line 56 of PrimeImplicantChart.java. Notice that the algorithm here for finding the minimum set of prime implicants to cover the function is different from that described in the book and in lecture. This algorithm uses a brute force approach; it tries every possible subset of possible prime implicants and chooses the smallest subset that covers the function. This algorithm takes exponential time in the size of the set of prime implicants, but that's fine for now.

In each file, I have marked the number of lines that my solution takes up with comment characters (//) at the beginning of the line. Your solution does not need to have exactly that many lines, but it should be a rough guideline for how much code you need to write. There are helper methods in the Implicant and Bit classes that you may find useful.

Turn-in

You can choose either of the turn-in options below. The grader will check both. If you submit to both, whichever has the later time-stamp will be graded.

Web-based submission instructions:

Use the Catalyst tool "Collect It" to submit your programming assignment.

Unix-based submission instructions:

You will use the turnin program to turn in the programming part of homework 4. You should submit your modified versions of Implicant.java, ImplicantionTable.java, and PrimeImplicantChart.java. On any of the department Linux workstations or servers, you should be able to type:

turnin -c cse370 Implicant.java ImplicantionTable.java PrimeImplicantChart.java

The turnin program will copy the files to the appropriate directory and put a time stamp on them.

Challenge/"Extra Credit"

By far the hardest part of Quine-McCluskey, in terms of computation time, is selecting a good subset of the prime implicants to cover the function. In fact, this part of the algorithm is NP-hard, which means that it is very unlikely that there exists an algorithm to solve it exactly that runs in less than exponential time, in the number of prime implicants.

The algorithm for selecting a subset of the prime implicants in the base version of the code is very naive and will take exponential time on most input functions. It is guaranteed to find a cover with the fewest possible prime implicants, though.

If you are interested in an extra challenge, you can try to develop a better implicant selection algorithm. Your algorithm can either try to exploit special cases so that it works efficiently in some cases, but is still exponential in the worst case, or it can use some heuristics so that it will run efficiently (not exponentially) in all cases, but might not find the smallest legal subset.

For the challenge part of this programming exercise, you can either program up a complete solution, or just write down some ideas about how one might solve the problem. The amount of "challenge credit" you get will be proportional to how clever and correct your solution is. Read over the policy on challenge exercises before spending a lot of time on this part! You will not get any "normal" class points, no matter how clever your solution. The challenge is mostly for students who find the problem intriguing and want to play with it more.