User Commands ESPRESSO(1) NAME espresso - Boolean Minimization SYNOPSIS espresso [type] [file] [options] DESCRIPTION Espresso takes as input a two-level representation of a two-valued (or a 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 automati- cally verifies that the minimized function is equivalent to the original function. The default input and output file formats are compatible with the Berkeley standard format for the physical descrip- tion of a PLA. The input format is described in detail in espresso(5). Note that the input file is a logical 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 representation of a PLA). The input and output formats have been expanded to allow for multiple-valued logic functions, and to allow for the specification of the don't care set which will be used in the minimization. Type specifies the logical format for the function. The allowed types are -f, -r, -fr, -fd, -dr, and -fdr which have the same meanings assigned in espresso(5). The command line options described below can be specified anywhere on the command line and must be separated by spaces: -d Verbose detail describing the progress of the minim- ization is written to standard output. Useful only for those familiar with the algorithms used. -do [s] This option executes subprogram [s]. Some of the more useful ones are: check - 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) echo - implies "-out fdr" and echoes the function to standard output. This can be used to compute the complement of a function. map - draw the Karnaugh maps for a function. opo - choose a good assignment of output function phases, and then minimize the function. The chosen phase is reported in the output file. qm - generate all prime implicants of a function, compute the reduced prime implicant table, and per- form a heuristic covering of this table. Provides a bound on the size of the minimum solution. Will perform an exact minimization if option -exact is used. single_output - Minimize each function one at a time as a single-output function. Terms will not be shared among the functions. stats - provide simple statistics on the size of the function The remaining subprograms (absmin, allphase, badopo, compact, contain, d1merge, dcset, essen, expand, intersect, irred, lexsort, make_sparse, mincov, min- terms, npc, opotol, pair, pairsasao, pop, primes, reduce, sharp, taut, union, unravel, verify) are intended for those heavily into manipulating Boolean functions. -exact Use an exact algorithm to solve the covering prob- lems encountered during the execution of the algo- rithms. Not recommended for casual users. -fast Stop after the first EXPAND and IRREDUNDANT opera- tions (i.e., do not iterate over the solution). -kiss Sets up a kiss-style minimization problem. -ness Essential primes will not be detected and removed from the minimization. -nirr The final result will not necessarily be forced irredundant. -help Provides a quick summary of the available command line options. -onset Recompute the ON-set before the minimization. Use- ful when the PLA has a large number of product terms (e.g., an exhaustive list of minterms). -out [s] Selects the output format. By default, only the ON-set (i.e., type f) is output after the minimiza- tion. [s] 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). [s] may also be eqntott to output algebraic equations acceptable to eqntott(1), or pleasure to output an unmerged PLA (with the .label and .group keywords) acceptable to pleasure(1). -pos 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 in the input file can also specify an arbitrary choice of output phases. -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 algorithm, a single line is printed which reports the processor time used, and the current cost of the function. -x Suppress printing of the solution. 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(1), pleasure(1), pla(5), espresso(5) R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni- Vincentelli, Logic Minimization Algorithms for VLSI Syn- thesis, Kluwer Academic Publishers, 1984. R. Rudell, "Espresso-MV: Algorithms for Multiple-Valued Logic Minimization," Proc. Cust. Int. Circ. Conf., May 1985. AUTHOR Richard Rudell BUGS Always passes comments from the input file, and passes unrecognized options straight from the input file to stan- dard output (sometimes this isn't what you want). There are a lot of options, but the most typical use is the following: eqntott -r file.eqn | espresso >file.pla The -R option of eqntott should not be used (it is much too expensive).