ESPRESSO(1) 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 produces a minimal equivalent representation. The algo- rithms used are new and represent an advance in both speed and optimality of solution in heuristic Boolean minimiza- tion. 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. 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. 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 min- imization 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. opo - choose a good assignment of output function 12/28/84 1 ESPRESSO(1) ESPRESSO(1) phases, and minimize the function qm - generate all prime implicants of a function, compute the "reduced prime implicant table" and perform a simple greedy covering of this table. Will also provide a bound on the size of the mini- mum solution if option -d is used. stats - provide simple statistics on the size of the function The remaining subprograms (contain, compact, essen, expand, intersect, irred, lexsort, mincov, miniexpord, miniredord, pop, primes, reduce, sharp, taut, union, unravel, verify + surely oth- ers by now) are intended for those heavily into manipulating Boolean functions. -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. -out [s] Selects the output format. By default, only the ON-set (i.e., type f) is output after the mini- mization. [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). -pos Swaps the ON-set and OFF-set of the function after reading the function. (This can be used to mini- mize the OFF-set of a function.) -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 12/28/84 2 ESPRESSO(1) ESPRESSO(1) 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 pla(5), espresso(5) Logic Minimization Algorithms for VLSI Synthesis, R. Bray- ton, G. Hachtel, C. McMullen, and A. Sangiovanni- Vincentelli, Kluwer Academic Publishers, 1984. 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). 12/28/84 3