CS 467 -- Advanced Logic Design
Espresso - Two-Level Optimization
Espresso
Another tool, separate from the Foundation tools, that can be used as a circuit design aid is a program called espresso. Espresso performs minimization of Boolean expressions using a heuristic algorithm. Because the algorithm is heuristic, espresso will not always find the exact minimum for a function, although for small functions the answer is almost always exact. In practice, espresso finds an answer very close to the minimum using dramatically shorter execution times than exact techniques such as Quine-McCluskey. Espresso, and its descendants MIS and SIS, are widely used in both academia and industry, and you will find espresso algorithms at the core of many successful logic synthesis programs. Espresso has a wide variety of uses, and a huge number of switches to control its operation. In this class you will likely use espresso in its simplest form to minimize Boolean expressions into two-level sum of products form.
The input format for espresso that we will use is a simple listing of product terms from a sum-of-products Boolean expression. The file will begin with lines to tell espresso how many inputs the function has and how many outputs it uses. These are followed by the product terms, and the output values, one per line. It's like a truth table except that you only have to enter the entries where the output is valid, and you can use a ``-'' to represent a don't-care in the product term. That is, if you have a function F(A,B,C,D) of four variables, and one of the product terms is AB, you can denote this as 11- - in the input file.
Here's an example. It is a function of four variables given by the expression
The input file that would be used for espresso is as follows:
.i 4 .o 1 .ilb A B C D .ob F 0001 1 0011 1 0101 1 0111 1 1001 1 0110 - 1100 - 1101 - .e
The first line tells espresso that there are 4 inputs, the second that
there is only a single output. The following lines are the minterms in
the expression, listed one per line. The order I have chosen is ABCD
so that I can simply write the binary number of each minterm to
represent that minterm. The 1 following the space is the desired
output value, and the ``-'' defines the don't-care terms. The last
line signals the end of the function. Note that a 1 in the minterm
representation represents that variable in true form, and a 0 is the
complemented form. For example, the first minterm in this file is
Note also that you
can have, if you like, don't cares in the input file. If the
expression you are trying to minimize is not in standard sum of
products form, some of the terms may not contain all the input
variables, and would have a ``-'' in any columns for the variables
that are not used. You can also have multiple outputs and let espresso
minimize the whole thing. In this case you could have 0's or ``-''`s
in the output listing.
Espresso is run on this input file by redirecting the input to be from that file, and redirecting the output to another file. The program itself is in /cse/courses/cse467/1998au/bin. You can add this to your system search path using ``set path = ($path /cse/courses/cse467/1998au/bin)'' before trying to run espresso. Assuming that /cse/courses/cse467/1998au/bin is on your path, and that the test file shown above is called test.es, and you would like the output of espresso to go to test.out, then the command would be:
espresso < test.es > test.out
The result, contained in test.out, of running espresso on this test case is:
.i 4 .o 1 .p 2 --01 1 0--1 1 .e
You can see that espresso has added a line to tell how many product
terms are left, in this case 2, and has listed the remaining product
terms in the reduced expression. Remember that the ``-'' is a
don't-care condition and signals that that variable need not appear in
that product term. The reduced expression is therefore 
. Luckily for espresso, this is the same
as the expression that results from K-map manipulation.
There are more examples of espresso files in your textbook, and also in the /cse/courses/cse467/1998au/examples directory.