Espresso heuristic logic minimizer
Encyclopedia
The Espresso logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital electronic gate circuits. Espresso was developed at IBM by Robert Brayton. Rudell later published the variant Espresso-MV in 1986 under the title "Multiple-Valued Logic Minimization for PLA Synthesis". Espresso has inspired many derivatives.
that transform that information. State machines, like counters, are a combination of memory elements and combinational logic
circuits. Since memory elements are standard logic circuits they are selected out of a limited set of alternative circuits; so designing digital functions comes down to designing the combinational gate circuits and interconnecting them.
In general the instantiation of logic circuits from high-level abstraction is referred to as Logic Synthesis
, which can be carried out by hand, but usually some formal method by computer is applied. In this article the design methods for combinational logic circuits are briefly summarized.
The starting point for the design of a digital logic circuit is its desired functionality, having derived from the analysis of the system as a whole, the logic circuit is to make part of. The description can be stated in some algorithmic form or by logic equations, but may be summarized in the form of a table as well. The below example shows a part of such a table for a 7-segment driver that translates the binary code for the values of a decimal digit into the signals that cause the respective segments of the display to light up.
The implementation process starts with a logic minimization phase, to be described below, in order to simplify the function table by combining the separate terms into larger ones containing fewer variables.
Next, the minimized result may be split up in smaller parts by a factorization procedure and is eventually mapped onto the available basic logic cells of the target technology. This operation is commonly referred to as Logic Optimization
.
The first alternative method to become popular was the tabular method developed by Quine and McCluskey. Starting with the truth table for a set of logic functions, by combining the minterms for which the functions are active—the ON-cover—or for which the function value is irrelevant—the Don't-Care-cover or DC-cover—a set of prime implicants
is composed. Finally a systematic procedure is followed to find the smallest set of prime implicants the output functions can be realised with.
Although this Quine–McCluskey algorithm is very well suited to be implemented in a computer program, the result is still far from efficient in terms of processing time and memory usage. Adding a variable to the function will roughly double both of them, because the truth table length increases exponentially with the number of variables. A similar problem occurs when increasing the number of output functions of a combinational function block. As a result the Quine–McCluskey method is practical only for functions with a limited number of input variables and output functions.
. Compared to the other methods, this one is essentially more efficient, reducing memory usage and computation time by several orders of magnitude. Its name reflects the way of instantly making a cup of fresh coffee. There is hardly any restriction to the number of variables, output functions and product terms of a combinational function block. In general, e.g. tens of variables with tens of output functions are readily dealt with.
The input for ESPRESSO is a function table of the desired functionality; the result is a minimized table, describing either the ON-cover or the OFF-cover of the function, depending on the selected options. By default the product terms will be shared as much as possible by the several output functions, but the program can be instructed to handle each of the output functions separately. This allows for efficient implementation in two-level logic arrays such as a PLA
(Programmable Logic Array) or a PAL
(Programmable Array Logic).
The ESPRESSO algorithm proved so successful that it has been incorporated as a standard logic function minimization step into virtually any contemporary logic synthesis tool. For implementing a function in multi-level logic, the minimization result is optimized by factorization and mapped onto the available basic logic cells in the target technology, whether this concerns an FPGA (Field Programmable Gate Array)
or an ASIC (Application Specific Integrated Circuit)
.
Publicad - free Publicad toolkit including Minilog logic minimization program.
A version of Espresso that has been updated for modern POSIX systems is available at [ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz]
Introduction
Digital electronic equipment has deeply penetrated everyone's life. Electronic devices are embedded in all kinds of appliances from coffee makers to automobiles. All such devices are composed of numerous blocks of digital circuits, the combination of which performs the required task. As a result, the efficient implementation of logic functions in the form of logical gate circuits has become an economical key factor in the success of many contemporary industrial products.Designing digital logic circuits
All digital systems are composed of two elementary functions: memory elements for storing information, and combinational circuitsCombinational logic
In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
that transform that information. State machines, like counters, are a combination of memory elements and combinational logic
Combinational logic
In digital circuit theory, combinational logic is a type of digital logic which is implemented by boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the...
circuits. Since memory elements are standard logic circuits they are selected out of a limited set of alternative circuits; so designing digital functions comes down to designing the combinational gate circuits and interconnecting them.
In general the instantiation of logic circuits from high-level abstraction is referred to as Logic Synthesis
Logic synthesis
In electronics, logic synthesis is a process by which an abstract form of desired circuit behavior, typically register transfer level , is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs, including VHDL and Verilog...
, which can be carried out by hand, but usually some formal method by computer is applied. In this article the design methods for combinational logic circuits are briefly summarized.
The starting point for the design of a digital logic circuit is its desired functionality, having derived from the analysis of the system as a whole, the logic circuit is to make part of. The description can be stated in some algorithmic form or by logic equations, but may be summarized in the form of a table as well. The below example shows a part of such a table for a 7-segment driver that translates the binary code for the values of a decimal digit into the signals that cause the respective segments of the display to light up.
Digit Code Segments
A B C D E F G
0 0000 1 1 1 1 1 1 0 -A-
1 0001 0 1 1 0 0 0 0 | |
2 0010 1 1 0 1 1 0 1 F B
3 0011 1 1 1 1 0 0 1 | |
4 0100 0 1 1 0 0 1 1 -G-
5 0101 1 0 1 1 0 1 1 | |
6 0110 1 0 1 1 1 1 1 E C
7 0111 1 1 1 0 0 0 0 | |
8 1000 1 1 1 1 1 1 1 -D-
9 1001 1 1 1 1 0 1 1
The implementation process starts with a logic minimization phase, to be described below, in order to simplify the function table by combining the separate terms into larger ones containing fewer variables.
Next, the minimized result may be split up in smaller parts by a factorization procedure and is eventually mapped onto the available basic logic cells of the target technology. This operation is commonly referred to as Logic Optimization
Logic optimization
Logic optimization, a part of logic synthesis, is the process of finding an equivalent representation of the specified logic circuit under one or more specified constraints...
.
Classical minimization methods
Minimizing Boolean functions by hand using the classical Karnaugh maps is a laborious, tedious and error prone process. It isn't suited for more than 6 input variables and practical only for up to 4 variables, while product term sharing for multiple output functions is even harder to carry out. Moreover, this method doesn't lend itself to be automated in the form of a computer program. However, since modern logic functions are generally not constrained to such a small number of variables, while the cost as well as the risk of making errors is prohibitive for manual implementation of logic functions, the use of computers became indispensable.The first alternative method to become popular was the tabular method developed by Quine and McCluskey. Starting with the truth table for a set of logic functions, by combining the minterms for which the functions are active—the ON-cover—or for which the function value is irrelevant—the Don't-Care-cover or DC-cover—a set of prime implicants
Implicant
In Boolean logic, an implicant is a "covering" of one or more minterms in a sum of products of a boolean function. Formally, a product term P in a sum of products is an implicant of the Boolean function F if P implies F...
is composed. Finally a systematic procedure is followed to find the smallest set of prime implicants the output functions can be realised with.
Although this Quine–McCluskey algorithm is very well suited to be implemented in a computer program, the result is still far from efficient in terms of processing time and memory usage. Adding a variable to the function will roughly double both of them, because the truth table length increases exponentially with the number of variables. A similar problem occurs when increasing the number of output functions of a combinational function block. As a result the Quine–McCluskey method is practical only for functions with a limited number of input variables and output functions.
Espresso algorithm
A radically different approach to this issue is followed in the ESPRESSO algorithm, developed by Brayton e.a. at the University of California, Berkeley. Rather than expanding a logic function into minterms, the program manipulates "cubes", representing the product terms in the ON-, DC- and OFF-covers iteratively. Although the minimization result is not guaranteed to be the global minimum, in practice this is very closely approximated, while the solution is always free from redundancyLogic redundancy
Logic redundancy occurs in a digital gate network containing circuitry that does not affect the static logic function. There are several reasons why logic redundancy may exist...
. Compared to the other methods, this one is essentially more efficient, reducing memory usage and computation time by several orders of magnitude. Its name reflects the way of instantly making a cup of fresh coffee. There is hardly any restriction to the number of variables, output functions and product terms of a combinational function block. In general, e.g. tens of variables with tens of output functions are readily dealt with.
The input for ESPRESSO is a function table of the desired functionality; the result is a minimized table, describing either the ON-cover or the OFF-cover of the function, depending on the selected options. By default the product terms will be shared as much as possible by the several output functions, but the program can be instructed to handle each of the output functions separately. This allows for efficient implementation in two-level logic arrays such as a PLA
Programmable logic array
A programmable logic array is a kind of programmable logic device used to implement combinational logic circuits. The PLA has a set of programmable AND gate planes, which link to a set of programmable OR gate planes, which can then be conditionally complemented to produce an output...
(Programmable Logic Array) or a PAL
Programmable Array Logic
The term Programmable Array Logic is used to describe a family of programmable logic device semiconductors used to implement logic functions in digital circuits introduced by Monolithic Memories, Inc. in March 1978. MMI obtained a registered trademark on the term PAL for use in "Programmable...
(Programmable Array Logic).
The ESPRESSO algorithm proved so successful that it has been incorporated as a standard logic function minimization step into virtually any contemporary logic synthesis tool. For implementing a function in multi-level logic, the minimization result is optimized by factorization and mapped onto the available basic logic cells in the target technology, whether this concerns an FPGA (Field Programmable Gate Array)
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...
or an ASIC (Application Specific Integrated Circuit)
Application-specific integrated circuit
An application-specific integrated circuit is an integrated circuit customized for a particular use, rather than intended for general-purpose use. For example, a chip designed solely to run a cell phone is an ASIC...
.
Minilog
Minilog is a logic minimization program exploiting this ESPRESSO algorithm. It is able to generate a two-level gate implementation for a combinational function block with up to 40 inputs and outputs or a synchronous state machine with up to 256 states. It is part of the Publicad educational design package, that can be downloaded from the websitePublicad - free Publicad toolkit including Minilog logic minimization program.
Logic Friday
Logic Friday is a free Windows program that provides a graphical interface to ESPRESSO, as well as to misII, another module in the Berkeley Octtools package. With Logic Friday users can enter a logic function as a truth table, equation, or gate diagram, minimize the function, and then view the results in both of the other two representations. Logic Friday is available at http://www.sontrak.com.Espresso sources
The source of the original Espresso program is available from the website of the University of California, Berkeley, at Pubs/Downloads/Espresso.A version of Espresso that has been updated for modern POSIX systems is available at [ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz]