= ESPRESSO(1)
:doctype: manpage

== NAME

espresso - Boolean Minimization


== SYNOPSIS

*espresso* [_file_]


== DESCRIPTION

_Espresso_ takes as input a two-level representation of a two-valued Boolean
function, and produces 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 standard input, performs the minimization, and writes the
minimized result to standard output.

The input and output format is described below in the *FILE FORMAT* section.


== FILE FORMAT

_Espresso_ accepts as input a two-level description of a Boolean function. This
is described as a character matrix with keywords embedded in the input to
specify the size and type of the matrix of the input function.

The following keywords are recognized by _espresso_. [d] denotes a decimal
number and [s] denotes a text string.

*.i [d]*::
  Required. Specifies the number of input variables. This keyword must come
  before any product terms and the *.o* keyword.
*.o [d]*::
  Required. Specifies the number of output functions. This keyword must come
  before any product terms.
*.type [s]*::
  Optional, default is *fd*. Sets the logical interpretation of the character
  matrix as described below. [s] is one of *fd* or *fr* for input files, and *f*
  for output files. This keyword must come before any product terms.
*.e (.end)*::
  Optional. Marks the end of the file. This keyword must come after any product
  terms.

When we speak of the ON-set of a Boolean function, we mean those minterms which
imply the function value is a 1. Likewise, the OFF-set are those terms which
imply the function is a 0, and the DC-set (don't care set) are those terms for
which the function is unspecified. A function is completely described by
providing its ON-set, OFF-set and DC-set. Note that all minterms lie in the
union of the ON-set, OFF-set and DC-set, and that the ON-set, OFF-set and DC-set
share no minterms.

The purpose of the _espresso_ minimization program is to find a logically
equivalent set of product-terms to represent the ON-set and optionally minterms
which lie in the DC-set, without containing any minterms of the OFF-set.

A term is represented by a "cube" which can be considered either a compact
representation of an algebraic product term which implies the function value is
a 1, or as a representation of a row in a PLA which implements the term. A cube
has an input part which corresponds to the input plane of a PLA, and an output
part which corresponds to the output plane of a PLA.

Each position in the input plane corresponds to an input variable where a 0
implies the corresponding input literal appears complemented in the product
term, a 1 implies the input literal appears un-complemented in the product term,
and - implies the input literal does not appear in the product term.

Each position in the out plane corresponds to a logic function.

A Boolean function can be described in one of the following two ways:

[arabic]
. *.type fd*: The ON-set and DC-set are provided. In this case, _espresso_
computes the OFF-set as the complement of the union of the ON-set and the
DC-set. If any minterm belongs to both the ON-set and DC-set, then it is
considered a don't care. For each output function, a *1* means this product term
belongs to the ON-set of this function, a *0* means this product term has no
meaning for this function (just a placeholder), and a *-* means this product
term belongs to the DC-set of this function.
. *.type fr*: The ON-set and OFF-set are provided. In this case, _espresso_
computes the DC-set as the complement of the union of the ON-set and the
OFF-set. It is an error for any minterm to belong to both the ON-set and
OFF-set. For each output function, a *1* means this product term belongs to the
ON-set of this function, a *0* means this product term belongs to the OFF-set of
this function, and a *-* means this product term has no meaning for this
function (just a placeholder).
. *.type f*: Output format, the ON-set is given. For each output function, a *1*
means this product term belongs to the ON-set, and a *0* means this product term
has no meaning for the value of this function (just a placeholder). This type
corresponds to an actual PLA where only the ON-set is actually implemented.

A 1-of-8 decoder (e.g. 74xx138 without enables) can be described completely in
minterms as:
....
.i 3
.o 8
.type fd
000 00000001
001 00000010
010 00000100
011 00001000
100 00010000
101 00100000
110 01000000
111 10000000
....


== SEE ALSO

pass:[R.] Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli,
_Logic Minimization Algorithms for VLSI Synthesis_, Kluwer Academic Publishers,
1984.
