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.

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