The roots of the project which culminates with the writing of
this book can be traced to the work on logic synthesis started in 1979 at
the IBM Watson Research Center and at University of California,
Berkeley. During the preliminary phases of these projects, the impor
tance of logic minimization for the synthesis of area and performance
effective circuits clearly emerged. In 1980, Richard Newton stirred our
interest by pointing out new heuristic algorithms for two-level logic
minimization and the potential for improving upon existing approaches.
In the summer of 1981, the authors organized and participated
in a seminar on logic manipulation at IBM Research. One of the goals
of the seminar was to study the literature on logic minimization and to
look at heuristic algorithms from a fundamental and comparative point
of view. The fruits of this investigation were surprisingly abundant: it
was apparent from an initial implementation of recursive logic minimiza
tion (ESPRESSO-I) that, if we merged our new results into a two-level
minimization program, an important step forward in automatic logic
synthesis could result. ESPRESSO-II was born and an APL implemen
tation was created in the summer of 1982. The results of preliminary
tests on a fairly large set of industrial examples were good enough to
justify the publication of our algorithms. It is hoped that the strength
and speed of our minimizer warrant its Italian name, which denotes both
express delivery and a specially-brewed black coffee.
We decided to publish this material as a monograph rather than
as a scries of papers for several reasons. We wanted to maintain a
unified point of view and develop the necessary foundational material;
to provide a reference for the mathematical results on which the proce
dures rest; and finally to describe in depth the algorithms themselves.