Espresso heuristic logic minimizer
The ESPRESSO logic minimizer is a computer program using heuristic and specific algorithms for efficiently reducing the complexity of digital logic gate circuits.[1] ESPRESSO-I was originally developed at IBM by Robert K. Brayton et al. in 1982.[2][3] and improved as ESPRESSO-II in 1984.[4][5] Richard L. Rudell later published the variant ESPRESSO-MV in 1986[6] and ESPRESSO-EXACT in 1987.[7][8][5] 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
Designing digital logic circuits
All digital systems are composed of two elementary functions:
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
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.[9]
Classical minimization methods
Minimizing
The first alternative method to become popular was the tabular method developed by
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 different approach to this issue is followed in the ESPRESSO algorithm, developed by Brayton et al. at the University of California, Berkeley.[4][3] It is a resource and performance efficient algorithm aimed at solving the heuristic hazard-free two-level logic minimization problem.[13]
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
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
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 a field-programmable gate array (FPGA) or an application-specific integrated circuit (ASIC).
Software
ESPRESSO
The original ESPRESSO program is available as C source code from the University of California, Berkeley website. The last release was version 2.3 dated 1988.[14] The ESPRESSO-AB and EQNTOTT (equation to truth table) program, an updated version of ESPRESSO for modern POSIX systems, is available in Debian Linux distribution (.deb) file format as well the C source code. The last release was version 9.0 dated 2008.[15] A Windows and C++20 compatible was ported to GitHub in 2020.[16]
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. The last release was version 1.1.4 dated 2012.[17]
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 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.[18]
References
- ISBN 0-201-15461-7.
- IEEE: 42–48.
- ^ a b "Robert K. Brayton; Professor Emeritus, Professor in the Graduate School". University of California, Berkeley. 2018-09-23. Archived from the original on 2018-09-23. Retrieved 2018-09-23.
- ^ ISBN 0-89838-164-9.
- ^ ISBN 978-0-201-14545-8ark:/13960/t2f83p38r. Retrieved 2021-04-17.
- ^ Rudell, Richard L. (1986-06-05). "Multiple-Valued Logic Minimization for PLA Synthesis" (PDF). Memorandum No. UCB/ERL M86-65. Berkeley, USA.
- S2CID 13525177.
- ^ Rudell, Richard L. (April 1989). Logic Synthesis for VLSI Design (PhD thesis). Berkeley: University of California. (ESPRESSO-EXACT)
- ISBN 0-07-016333-2.
- ISBN 0-442-30606-7.
- ISBN 0-8053-2703-7.
- ISBN 0-02-367171-8.
- doi:10.7916/D8N58V58. Retrieved 2021-10-04.
- ^ "Espresso C source code (1988)". University of California, Berkeley. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
- ^ "Espresso-eb / eqntott C source code and program (2008)". Google Code. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
- ^ "Espresso heuristic logic minimizer C++20 Windows source". GitHub.
- ^ "Logic Friday program (2012)". sontrak. 2018-09-21. Archived from the original on 2013-10-22. Retrieved 2018-09-21.
- ^ "Espresso-IISOJS". GitHub.
Further reading
- Eschermann, Bernhard (May 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [Functional design of digital circuits - Methods and CAD techniques]. Springer-Lehrbuch (in German). ISBN 3-540-56788-7.