BOOM 2.7 Manual


BOOM (BOOlean Minimization) is a tool for minimizing two-valued Boolean functions. The output is a near-minimal or minimal two-level disjunctive form. The input and output of BOOM are compatible with Berkeley standard PLA format.

BOOM 2.7 runs as a Win32 console application.

Minimum requirements:

Command line syntax

BOOM [options] [source] [destination] [report]

-FRn Define FC-Min:BOOM ratio n (0-100), 0 is default help
-DFn Define the FC-Min Depth Factor, 10 is default help
-DDx Define the FC-Min Depth Factor Direction x:
0 DF = 1:n (from -DFn)
1 DF = n:1 (from -DFn), default
help
-CMn Define CD-Search mutations ratio n (0-100) help
-RMn Define implicant reduction mutations ratio n (0-100) help
-Ex Select implicant expansion type:
0 Sequential search
1 Distributed multiple IE
2 Distributed exhaustive IE
3 Multiple IE (default)
4 Exhaustive IE
help
-CPx Select the covering problem solution algorithm:
0 LCMC
1 Contributive addition (default)
2 Contributive removal
3 Exact cover
help
-Sxn Define stopping criterion x of value n:
t stop after n seconds
i stop after n iterations (default is Si1)
n stopping interval equal to n
q stop when quality of solution meets n
help
-Qx Define optimization criterion x:
t terms
l literals
o output cost
b literals+output cost (default)
g number of gates
G number of gate equivalents
help
-single Single-output minimization help
-endcov Cover at the end only help
-SD Substitute output don't cares help
-Ox[n] Define output format:
P PLA (default)
V VHDL (ports as individual variables). If n is specified, the function is split into max. n-input gates
W VHDL (ports as vectors). If n is specified, the function is split into max. n-input gates
v Verilog
B BLIF
E Equations
H HTML (table)
help
-nocheck Don't check the input function for consistence help
-noIR Implicant reduction is not performed. help
-namevars Implicitly name the variables help

Special Functions (cannot be combined with minimization):

-info Prints the information about the PLA function help
-Tcheck Checks the input function for consistence help
-Tsplit Splits intersecting terms help
-Tminterm Splits function into minterms help

FC-Min:BOOM ratio

Defines the ratio between BOOM and FC-Min.
0 means that only BOOM will be run, 100 that only FC-Min
FC-Min is intended for multi-output functions. Don't run FC-Min for functions having 1-3 outputs. It is not efficient here. For functions with more output variables, FC-Min is faster than CD-Search.

FC-Min depth factor

Defines the depth factor. For low values, the minimization will be faster, however solutions having a bigger number of terms will be produced.
High values slow down the minimization, however better solutions are often found.
It applies to FC-Min only.
For more info see "Fišer, P. - Kubátová, H.: Boolean Minimizer FC-Min: Coverage Finding Process".

FC-Min Depth Factor Direction

Switches between 1:x and x:1 for the Depth factor.
It applies to FC-Min only.

CD-Search mutations ratio

This argument specifies the ratio of forced randomness of the CD-search. In some cases, by increasing this value you may reach better solution.
It applies to BOOM only.

Implicant reduction mutations ratio

This argument specifies the ratio of forced randomness of the IR phase. In some cases, by increasing this value you may reach better solution.
It applies to BOOM only.

Implicant expansion

You can specify the implicant expansion method. It applies to BOOM only.
The Sequential Search is the fastest one, however, to reach good results you need to run BOOM for more iterations.
The Multiple Expansion is more efficient, since it produces more PIs in one iteration. It is suggested to use this option.
The Exhaustive Expansion produces all the PIs from one implicant in each iteration. Sometimes can be very slow (the complexity is exponential).
The distributed versions of IE split the expansion among several consecutive iterations. The expansion is then faster, but more iterations have to be done.

Covering problem solution

This switch selects the covering problem solution algorithm.
The LCMC heuristic is the fastest one, but not too efficient. The Contributive Addition heuristic is the most sophisticated one, thus it is suggested to use it. The Contributive Removal can be sometimes slow and inefficient, but for some special cases it is better than Contributive Addition.
The Exact Cover always finds the best solution (of the CP problem, not the whole minimization!), but can be extremely slow for large problems.

Stopping criterion

BOOM performs an iterative minimization. The more iterations are processed, the better the result that can be archieved. The number of iterations can be specified by the user. Moreover, the minimization can be stopped after a given time, or when a satisfactory result is reached.
The stopping criteria can be combined, if in a reasonable way.

Optimization criterion

During iterative minimization the best result found so far is remembered. The measure of the quality can be specified by the user.

Single-output minimization

Does not perform a multi-output minimization, thus BOOM tries to find a solution having a least number of terms in each output function separately.
Terms having only one '1' vaule in the output plane are produced.

Cover at the end only

When this option is selected, the covering problem is solved only once at the end of the minimizaion process. Thus, the whole process is sped up. This option cannot be combined with optimization criteria based stopping condition.

Substitute output don't cares

Normally, when a term in the resulting PLA is not a necessary implicant of some output function (but it is necessary for other function), it is assigned as an output don't care.
When this option is on, the don't cares are substituted with zero values.

Output format

Defines the format, in which will be the output function saved. Standard PLA, VHDL, Verilog and BLIF formats are supported. Additionally, the function can me saved as a set of equations or as a HTML truth table.

Don't check the input function for consistence

The function is implicitly checked for consistency before the minimization is run. This option switches the consistency check off. It slightly reduces the total minimization time, but it may cause the program hang, if an inconsistent function is submitted as an input.

Don't perform the implicant reduction

This option prevents CD-search from generating group implicants. This phase is often very time-demanding, especially for functions with many outputs. However, when FC-Min is employer as well (i.e., by -FR50 option), the group implicants are produced by it, so the IR phase needs not be necessarily performed.

Implicitly name the variables

If the names of the variables are not specified in the input file, the program automatically names the input variables as x0 - xn, the output variables as y0 - ym.

Information about the PLA function

Prints the info on the number of the variables, terms and the complexity of the given function.

Checks the input function for consistence

For the PLA, type fr, there is a possibility of inconsistence. Thus, both the 0 and 1 values are defined for some minterm. In this case the minimization cannot be performed. However, the minimization process will start, but most probabely it will fail or it will never stop. Hence checking the funcion for inconsistence is recommended.

Splits intersecting terms

Splits the function (PLA type fr) so that no terms are intersecting.
It may be rather time-consuming for functions with a large number of inputs.

Splits function into minterms

Splits the function (PLA type fr) into minterms, by evaluating its output for each of 2n minterms.
It may be rather time-consuming for functions with a large number of inputs.

Source function

The source for minimization will be a PLA file. Type .fr is required (on-set and off-set specified).

Destination function

The output of BOOM is a PLA file type .fd. This corresponds to the physical PLA representation of the function. When no destination is specified, the function is printed to the standard output.

Report file

The minimization report is written to a file, if specified.

Example

We have a Boolean function of 4 input variables and 3 output variables described by the following Karnaugh maps:

1 1 1 X
0 0 1 0
0 0 1 0
0 1 0 X
0 1 0 X
0 1 1 1
1 1 1 0
1 0 1 X
0 0 1 X
0 0 0 1
0 1 1 0
0 1 0 X

This function can be described by a PLA file as follows:

.i 4
.o 3
.p 14
.type fr
1100 010
1011 010
0100 000
1110 000
1000 010
1111 111
0000 100
0011 101
0110 011
0101 010
0111 110
1101 011
0001 110
1001 101
.e

This will be an input for the BOOM minimizer. This function can be minimized by the following command:

BOOM fnct.pla

The function will be minimized to the form:

.i 4
.o 3
.p 9
-111 110
00-- 100
1-00 010
0-10 011
001- 001
1-11 010
11-1 011
0-01 010
1001 101
.e

Other Examples


BOOM src.pla out.pla
 Minimizes function src.pla and the output is written to the out.pla file.
Standard setting is used (1 iteration, CD-Search only, no mutations, Multiple IE, Contributive Addition CP).		 
BOOM -Si10 -FR50 src.pla out.pla
 Minimizes function src.pla and the output is written to the out.pla file.
10 iterations, 50% CD-Search and 50% FC-Min, depth factor set to 10:1, no mutations, Multiple IE, Contributive Addition CP, optimization criterion are literals+output cost.		 
BOOM -St10 -CM10 -FR10 -DF5 -QG src.pla out.pla
 Minimizes function src.pla and the output is written to the out.pla file.
Stops after 10 seconds, 10% CD-Search mutations, 90% CD-Search and 10% FC-Min, depth factor set to 5:1, Multiple IE, Contributive Addition CP, optimization criterion are gate equivalents.		 
BOOM -Sq100 -Qt -single src.pla out.pla
 Minimizes function src.pla and the output is written to the out.pla file.
Single-output minimization is performed, until the solution reaches 100 terms or less.