The ESPRESSO logic minimizer is a computer program using
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
and specific
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s for efficiently reducing the
complexity
Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generall ...
of digital
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
circuits.
ESPRESSO-I was originally developed at
IBM by
Robert K. Brayton et al. in 1982.
and improved as ESPRESSO-II in 1984.
Richard L. Rudell later published the variant ESPRESSO-MV in 1986
and ESPRESSO-EXACT in 1987.
Espresso has inspired many derivatives.
Introduction
Electronic devices are composed of numerous blocks of digital circuits, the combination of which performs the required task. The efficient implementation of
logic function
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...
s in the form of
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
circuits (such that no more logic gates are used than are necessary) is necessary to minimize production costs, and/or maximize a device's performance.
Designing digital logic circuits
All digital systems are composed of two elementary functions:
memory elements for storing information, and
combinational circuit
In automata theory, combinational logic (also referred to as time-independent logic or combinatorial 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 i ...
s that transform that information.
State machines, like counters, are a combination of memory elements and
combinational logic
In automata theory, combinational logic (also referred to as time-independent logic or combinatorial 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 i ...
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
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a com ...
, 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 display
A seven-segment display is a form of electronic display device for displaying decimal numeral system, numerals that is an alternative to the more complex dot matrix displays.
Seven-segment displays are widely used in digital clocks, electronic ...
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 is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit d ...
.
Classical minimization methods
Minimizing
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
s by hand using the classical
Karnaugh maps
The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...
is a laborious, tedious and error prone process. It isn't suited for more than six input variables and practical only for up to four 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
Willard Quine
Willard Van Orman Quine (; known to his friends as "Van"; June 25, 1908 – December 25, 2000) was an American philosopher and logician in the analytic tradition, recognized as "one of the most influential philosophers of the twentieth century" ...
and
Edward McCluskey. Starting with the
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
for a set of logic functions, by combining the
minterm
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include ...
s 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 implicant
In Boolean logic, the term implicant has either a generic or a particular meaning. In the generic use, it refers to the hypothesis of an implication (implicant). In the particular use, a product term (i.e., a conjunction of literals) ''P'' is an ...
s 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
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a genera ...
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
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
* Exponential decay, decrease at a rate proportional to value
*Exp ...
ly 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 different approach to this issue is followed in the ESPRESSO algorithm, developed by Brayton et al. at the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...
.
It is a resource and performance efficient algorithm aimed at solving the heuristic
hazard
A hazard is a potential source of harm
Harm is a moral and legal concept.
Bernard Gert construes harm as any of the following:
* pain
* death
* disability
* mortality
* loss of abil ity or freedom
* loss of pleasure.
Joel Feinberg giv ...
-free two-level logic minimization problem.
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 mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
, in practice this is very closely approximated, while the solution is always free from
redundancy. 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
PLA may refer to:
Organizations Politics and military
* People's Liberation Army, the armed forces of China and of the ruling Chinese Communist Party
* People's Liberation Army (disambiguation)
** Irish National Liberation Army, formerly called ...
(Programmable Logic Array) or a
PAL
Phase Alternating Line (PAL) is a colour encoding system for analogue television. It was one of three major analogue colour television standards, the others being NTSC and SECAM. In most countries it was broadcast at 625 lines, 50 fields (25 ...
(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
In computer engineering, logic synthesis is a process by which an abstract specification of desired circuit behavior, typically at register transfer level (RTL), is turned into a design implementation in terms of logic gates, typically by a com ...
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 a
field-programmable gate array
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
(FPGA) or an
application-specific integrated circuit
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficie ...
(ASIC).
Software
ESPRESSO
The original ''ESPRESSO'' program is available as
C source code from the
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...
website. The last release was version 2.3 dated 1988.
The ''ESPRESSO-AB'' and ''EQNTOTT'' (equation to truth table) program, an updated version of ESPRESSO for modern
POSIX
The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines both the system- and user-level application programming interf ...
systems, is available in
Debian Linux distribution
A Linux distribution (often abbreviated as distro) is an operating system made from a software collection that includes the Linux kernel and, often, a package management system. Linux users usually obtain their operating system by downloading one ...
(.deb) file format as well the C source code. The last release was version 9.0 dated 2008.
A Windows and C++20 compatible was ported to github in 2020.
Logic Friday
''Logic Friday'' is a free
Windows
Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for serv ...
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. The last release was version 1.1.4 dated 2012.
Minilog
''Minilog'' is a free Windows program that provides logic minimization 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.
ESPRESSO-IISOJS
''ESPRESSO-IISOJS'' is a JavaScript implementation of ESPRESSO-II for single output functions. It employs
unit propagation
Unit propagation (UP) or Boolean Constraint propagation (BCP) or the one-literal rule (OLR) is a Algorithm, procedure of automated theorem proving that can simplify a set of (usually propositional logic, propositional) Clause (logic), clauses.
Def ...
as an additional optimization technique for the various algorithms in ESPRESSO-II that are based on the unate recursive paradigm. Another addition is allowing control over when literals can be raised which can be exploited to effectively minimize
Kleene logic functions.
References
Further reading
*
{{DEFAULTSORT:Espresso Heuristic Logic Minimizer
Electronic design automation software
Electronics optimization
Free simulation software
Electronic circuit simulators