ESPRESSO(1OCTTOOLS) ESPRESSO(1OCTTOOLS) NAME espresso - Boolean Minimization 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 single-output function. Terms will not be shared among the functions. The option -S1 will perform an exact minimization for each single- output 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). 31 January 1988 ESPRESSO(1OCTTOOLS)