Borys Bradel's Boolean Function Minimizer Applet

This applet creates a minimum-cost logic function either from a set of sum-of-products terms or through a BLIF (something UC-Berkeley came up with). I created this applet as a project for one of my courses. The applet uses a standard algorithm that combines minterms and eliminates any redundancies step by step until no more changes occur. Currently, most industrial algorithms use a heurstic algorithm which combines and splits minterms randomly while keeping track of how good the results are; the better combinations are kept and used as starting points for refinements, while the bad combinations are discarded. These heuristic algorithms do not guarantee optimum results, but for large circuits, they are faster. Please note that this applet has not been tested extensively.

I created the top interface before I knew about the BLIF interface. The top interface requires you to first specify the number of variables, and then only use the variables that appear inside the list box. The function that you input must have either a space or a plus sign between any variables. A variable can have an exclemation mark right before it to indicate that it is negated (note that there cannot be a space between an exclemation mark and its variable). Minterms can be input by putting m(#,#,#,#,#,....) as a single product expression. Don't cares can be implemented in the exact same way (the following examples will make this more clear).

Here are some examples:
!x1 !x2 x3 + !x1 x2 x3 + x1 !x2 x3+x1 x2 !x3+x1 x2 x3
x1+m(15)
m(1,3,4,5,9,11,13,15)
!x1 !x3 + !x1 x2 + d(6,7)
!x1 !x2 !x3 + x2 x3 x4+d(8,9,12,13)
!x1 !x2 !x3 + x2 x3 x4+d(8,9,12,11)
x1 x2 + !x2

The syntax for a BLIF is as follows:
.names name_1 name_2 ... name_n function_name
digit_1 digit_2 ... digit_n space cube_value
digit_1 digit_2 ... digit_n space cube_value
...
digit_1 digit_2 ... digit_n space cube_value
The digit_# can be either 0,1,x, or X while the cube_values can be 1,d, or D.
For example:
.names x1 x2 x3 x4 f
xx00 1
110x 1
1x11 1
10x0 1

The output for both interfaces is of the form:
Vector: The solution is: size #
cube_1
cube_2
....
cube_i

Note that the heuristic bound does nothing, since the program will always look for the best cover exhaustively. Also note that to change the variable number or variable name, you first have to change the text field, and then press a button. The same is true for the input areas. First you type in the input then you must press a button.

Sorry, you cannot view the applet because you do not have a Java 1.1-enabled browser.

This web page is maintained by Borys Bradel. Last update: Sep. 24, 2001
Address: http://www.eecg.utoronto.ca/~bradel/projects/booleancover/index.html