Espresso - Boolean Minimization
Manpage: espresso(1)
SYNOPSIS
espresso [options] [file]
DESCRIPTION
Espresso takes as input a two-level representation of a
two-valued (or multiple-valued) Boolean function, and pro
duces a minimal equivalent representation. The algorithms
used are new and represent an advance in both speed and
optimality of solution in heuristic Boolean minimization.
Espresso reads the file provided (or standard input if no
files are specified), performs the minimization, and
writes the minimized result to standard output. Espresso
automatically verifies that the minimized function is
equivalent to the original function. Options allow for
using an exact minimization algorithm, for choosing an
optimal phase assignment for the output functions, and for
choosing an optimal assignment of the inputs to input
decoders.
The default input and output file formats are compatible
with the Berkeley standard format for the physical
description of a PLA. The input format is described in
detail in espresso(5). Note that the input file is a log
ical representation of a set of Boolean equations, and
hence the input format differs slightly from that
described in pla(5) (which provides for the physical rep
resentation of a PLA). The input and output formats have
been expanded to allow for multiple-valued logic func
tions, and to allow for the specification of the don't-
care set which will be used in the minimization.
A complete list of the command line options is given
below. Be warned that many of the command line options
are not intended for general use.
-d Enables debugging. Useful only for those famil
iar with the algorithms used.
-Dcheck Checks that the function is a partition of the
entire space (i.e., that the ON-set, OFF-set and
DC-set are pairwise disjoint, and that their
union is the Universe).
-Dd1merge Performs a quick distance-1 merge on the input
file. This is useful when the input file is
very large (e.g., a truth table with more than
1000 terms) because distance-1 merge is O(n log
n) rather than the EXPAND step of Espresso which
is O(n * n). The output should then be run
through Espresso to complete the minimization.
A range of variables to be merged can also be
specified using -rn-m (the default is to merge
over all variables).
-Decho Echoes the function to standard output. This
can be used to get the complement of a function
when combined with -o.
-Dequiv Identify output variables which are equivalent.
Takes into account the don't-care set and checks
for equivalence of both the ON-set and OFF-set.
-Dexact Exact minimization algorithm (guarantees minimum
number of product terms, and heuristically mini
mizes number of literals). Potentially expen
sive.
-Dmany Reads and minimizes PLA's until end-of-file is
detected. PLA's in the same file are separated
by .e.
-Dmap Draw the Karnaugh maps for a binary-valued func
tion.
-Dmapdc Derive from the binary-valued variable DONT_CARE
a don't-care set, and then delete this variable.
All input conditions for which an output changes
when DONT_CARE changes define the don't-care
conditions for that output. This is a hack to
support don't-cares from high-level languages
without a notion of don't-cares.
-Dopo Perform output phase optimization (i.e., deter
mine which functions to complement to reduce the
number of terms needed to implement the func
tion). After choosing an assignment of phases
for the outputs, the function is minimized. A
simple algorithm is used which may become very
expensive for a large number of outputs (e.g.,
more than 40).
-Dopoall Minimize the function with all possible phase
assignments. A range of outputs to cycle
through can be given with -rn-m (the default is
to use all outputs). The option -S1 will per
form an exact minimization for each phase
assignment. Be warned that opoall requires an
exponential number of minimizations !
-Dpair Choose an assignment of the inputs to two-bit
decoders, and minimize the function. The func
tion MUST be minimized first to achieve good
results. There are actually 4 different algo
rithms, of increasing cost, which may be
selected with -S1, -S2, or -S3. The default is
-S0 which seems to give the best results for the
cost.
-Dpairall Minimize the function with all possible assign
ments of inputs to two-bit decoders. The option
-S1 will perform an exact minimization for each
assignment of inputs to decoders, and the option
-S2 will perform an output-phase assignment for
each assignment of inputs to decoders. Be
warned that pairall requires an exponential num
ber of minimizations !
-Dseparate
Remove the don't-care set from the ON-set of the
function.
-Dso Minimize each function one at a time as a sin
gle-output function. Terms will not be shared
among the functions. The option -S1 will per
form an exact minimization for each single-out
put function.
-Dso_both Minimize each function one at a time as a sin
gle-output function, but choose the function or
its complement based on which has fewer terms.
The option -S1 will perform an exact minimiza
tion for each single-output function and its
complement to determine which has fewer terms.
-Dstats Provide simple statistics on the size of the
function.
-Dverify Checks for Boolean equivalence of two PLA's.
Reads two filenames from the command line, each
containing a single PLA.
-DPLAverify
Checks for Boolean equivalence of two PLA's by
first permuting the columns based on the user
supplied variable names. Reads two filenames
from the command line.
-eeat Normally comments are echoed from the input file
to the output file. This options discards any
comments in the input file.
-efast Stop after the first EXPAND and IRREDUNDANT
operations (i.e., do not iterate over the solu
tion).
-ekiss Sets up a kiss-style minimization problem. This
is a hack.
-eness Essential primes will not be detected.
-enirr The result will not necessarily be made irredun
dant in the final step which removes redundant
literals.
-enunwrap The ON-set will not be unwrapped before begin
ning the minimization.
-eonset Recompute the ON-set before the minimization.
Useful when the PLA has a large number of prod
uct terms (e.g., an exhaustive list of
minterms).
-epos Swaps the ON-set and OFF-set of the function
after reading the function. This can be used to
minimize the OFF-set of a function. .phase (see
espresso(5)) in the input file can also specify
an arbitrary choice of output phases.
-estrong Uses the alternate strategy SUPER_GASP (as a
replacement for LAST_ GASP) which is more expen
sive, but occasionally provides better results.
-o[type] Selects the output format. By default, only the
ON-set (i.e., type f) is output after the mini
mization. [type] can be one of f, d, r, fd, dr,
fr, or fdr to select any combination of the ON-
set (f), the OFF-set (r) or the DC-set (d).
[type] may also be eqntott to output algebraic
equations acceptable to eqntott(1OCTTOOLS), or
pleasure to output an unmerged PLA (with the
.label and .group keywords) acceptable to plea
sure(1OCTTOOLS).
-s Will provide a short summary of the execution of
the program including the initial cost of the
function, the final cost, and the computer
resources used.
-t Will produce a trace showing the execution of
the program. After each main step of the algo
rithm, a single line is printed which reports
the processor time used, and the current cost of
the function.
-x Suppress printing of the solution.
-v [type] Specifies verbose debugging detail. Not gener
ally useful.
DIAGNOSTICS
Espresso will issue a warning message if a product term
spans more than one line. Usually this is an indication
that the number of inputs or outputs of the function is
specified incorrectly.
SEE ALSO
kiss(1OCTTOOLS), pleasure(1OCTTOOLS), pla(5OCTTOOLS),
espresso(5OCTTOOLS)
R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-
Vincentelli, Logic Minimization Algorithms for VLSI Syn
thesis, Kluwer Academic Publishers, 1984.
R. Rudell, A. Sangiovanni-Vincentelli, "Espresso-MV: Algo
rithms for Multiple-Valued Logic Minimization," Proc.
Cust. Int. Circ. Conf., Portland, May 1985.
R. Rudell, "Multiple-Valued Minimization for PLA Synthe
sis," Master's Report, University of California, Berkeley,
June 1986.
R. Rudell, A. Sangiovanni-Vincentelli, "Exact Minimization
of Multiple-Valued Functions for PLA Optimization", Int.
Conf. Comp. Aid. Des., Santa Clara, November 1986.
AUTHOR
Please direct any questions or comments to:
Richard Rudell
205 Cory Hall
Dept. of EECS
University of California
Berkeley, California 94720
Arpanet mail address is rudell@ic.Berkeley.EDU.
COMMENTS
Default is to pass comments and unrecognized options from
the input file to standard output (sometimes this isn't
what you want).
It is no longer possible to specify the type on the com
mand line.
There are a lot of options, but typical use doesn't need
them.
This manual page refers to Version 2.3 of Espresso. The
major change from Version 2.2 to Version 2.3 is the addi
tion of a fast sparse-matrix covering algorithm for the
-Dexact mode.
The -Dopo option becomes very slow for many outputs (>
20).