#

###

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

Back to Espresso Evaluation Page