Espresso heuristic logic minimizer

Last updated

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.

Contents

Introduction

Electronic devices are composed of numerous blocks of digital circuits, the combination of which performs the required task. The efficient implementation of logic functions in the form of 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 circuits 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 display 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. [9]

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 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. [10] 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 and Edward 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. [11] [12]

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 global minimum, 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 (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 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]

Related Research Articles

<span class="mw-page-title-main">Logic gate</span> Device performing a Boolean function

A logic gate is an idealized or physical device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output.

<span class="mw-page-title-main">Multiplexer</span> A device that selects between several analog or digital input signals

In electronics, a multiplexer, also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The selection is directed by a separate set of digital inputs known as select lines. A multiplexer of inputs has select lines, which are used to select which input line to send to the output.

<span class="mw-page-title-main">Digital electronics</span> Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.

<span class="mw-page-title-main">Combinational logic</span>

In automata 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 history of the input. In other words, sequential logic has memory while combinational logic does not.

Electronic design automation (EDA), also referred to as electronic computer-aided design (ECAD), is a category of software tools for designing electronic systems such as integrated circuits and printed circuit boards. The tools work together in a design flow that chip designers use to design and analyze entire semiconductor chips. Since a modern semiconductor chip can have billions of components, EDA tools are essential for their design; this article in particular describes EDA specifically with respect to integrated circuits (ICs).

<span class="mw-page-title-main">Quine–McCluskey algorithm</span> Algorithm for the minimization of Boolean functions

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 general principle this approach had already been demonstrated by the logician Hugh McColl in 1878, was proved by Archie Blake in 1937, and was rediscovered by Edward W. Samson and Burton E. Mills in 1954 and by Raymond J. Nelson in 1955. Also in 1955, Paul W. Abrahams and John G. Nordahl as well as Albert A. Mullin and Wayne G. Kellner proposed a decimal variant of the method.

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 the complete sum of prime implicants or Blake canonical form, and the algebraic normal form.

In digital circuit design, register-transfer level (RTL) is a design abstraction which models a synchronous digital circuit in terms of the flow of digital signals (data) between hardware registers, and the logical operations performed on those signals.

Formal equivalence checking process is a part of electronic design automation (EDA), commonly used during the development of digital integrated circuits, to formally prove that two representations of a circuit design exhibit exactly the same behavior.

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 computer program called a synthesis tool. Common examples of this process include synthesis of designs specified in hardware description languages, including VHDL and Verilog. Some synthesis tools generate bitstreams for programmable logic devices such as PALs or FPGAs, while others target the creation of ASICs. Logic synthesis is one aspect of electronic design automation.

<span class="mw-page-title-main">Standard cell</span>

In semiconductor design, standard-cell methodology is a method of designing application-specific integrated circuits (ASICs) with mostly digital-logic features. Standard-cell methodology is an example of design abstraction, whereby a low-level very-large-scale integration (VLSI) layout is encapsulated into an abstract logic representation.

Design flows are the explicit combination of electronic design automation tools to accomplish the design of an integrated circuit. Moore's law has driven the entire IC implementation RTL to GDSII design flows from one which uses primarily stand-alone synthesis, placement, and routing algorithms to an integrated construction and analysis flows for design closure. The challenges of rising interconnect delay led to a new way of thinking about and integrating design closure tools.

The algorithmic state machine (ASM) method is a method for designing finite state machines (FSMs) originally developed by Thomas E. Osborne at the University of California, Berkeley (UCB) since 1960, introduced to and implemented at Hewlett-Packard in 1968, formalized and expanded since 1967 and written about by Christopher R. Clare since 1970. It is used to represent diagrams of digital integrated circuits. The ASM diagram is like a state diagram but more structured and, thus, easier to understand. An ASM chart is a method of describing the sequential operations of a digital system.

In digital logic, a hazard is an undesirable effect caused by either a deficiency in the system or external influences in both synchronous and asynchronous circuits. Logic hazards are manifestations of a problem in which changes in the input variables do not change the output correctly due to some form of delay caused by logic elements This results in the logic not performing its function properly. The three different most common kinds of hazards are usually referred to as static, dynamic and function hazards.

In digital logic, a don't-care term for a function is an input-sequence for which the function output does not matter. An input that is known to never occur is a can't-happen term. Both these types of conditions are treated the same way in logic design and may be referred to collectively as don't-care conditions for brevity. The designer of a logic circuit to implement the function need not care about such inputs, but can choose the circuit's output arbitrarily, usually such that the simplest circuit results (minimization).

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 design.

The Richards controller is a method of implementing a finite state machine using simple integrated circuits and combinational logic. The method was named after its inventor, Charles L. Richards. It allows for easier design of complex finite state machines than the traditional techniques of state diagrams, state transition tables and Boolean algebra offer. Using Richards's technique, it becomes easier to implement finite state machines with hundreds or even thousands of states.

<span class="mw-page-title-main">Karnaugh map</span> Graphical method to simplify Boolean expressions

The Karnaugh 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 logical diagram aka Marquand diagram but with a focus now set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams or, rarely, as Svoboda charts, and Karnaugh maps as Karnaugh–Veitch maps.

State encoding assigns a unique pattern of ones and zeros to each defined state of a finite-state machine (FSM). Traditionally, design criteria for FSM synthesis were speed, area or both. Following Moore's law, with technology advancement, density and speed of integrated circuits have increased exponentially. With this, power dissipation per area has inevitably increased, which has forced designers for portable computing devices and high-speed processors to consider power dissipation as a critical parameter during design consideration.

Finite state machines (FSMs) are widely used to implement control logic in various applications such as microprocessors, digital transmission, digital filters and digital signal processing. Even for designs containing a good number of datapath elements, the controller occupies a sizeable portion. As the devices are mostly portable and hand-held, reducing power dissipation has emerged as the primary concern of today's VLSI designers. While the datapath elements can be shut down when they are not being used, controllers are always active. As a result, the controller consumes a good amount of system power. Thus, power-efficient synthesis of FSM has come up as a very important problem domain, attracting a lot of research. The synthesis method must be able to reduce both dynamic power and leakage power consumed by the circuit.

References

  1. ↑ Hayes, John Patrick (1993). Digital Logic Design. Addison Wesley. ISBN   0-201-15461-7.
  2. ↑ Brayton, Robert King; Hachtel, Gary D.; Hemachandra, Lane A.; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). "A comparison of logic minimization strategies using ESPRESSO: an APL program package for partitioned logic simulation". Proceedings of the IEEE International Symposium on Circuits and Systems, 1982. New York, New York, USA: IEEE: 42–48.
  3. 1 2 "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.
  4. 1 2 Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logic Minimization Algorithms for VLSI Synthesis (9th printing 2000, 1st ed.). Boston, Massachusetts, USA: Kluwer Academic Publishers. ISBN   0-89838-164-9.
  5. 1 2 Bolton, Martin (1990). "4.3.3 ESPRESSO-II". Written at University of Bristol, Bristol, UK. In Dagless, Erik L. (ed.). Digital Systems Design with Programmable Logic. Electronic Systems Engineering Series (1 ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. pp. 112, 115–116. ISBN   0-201-14545-6. LCCN   90000007. ISBN   978-0-201-14545-8 ark:/13960/t2f83p38r. Retrieved 2021-04-17.
  6. ↑ Rudell, Richard L. (1986-06-05). "Multiple-Valued Logic Minimization for PLA Synthesis" (PDF). Memorandum No. UCB/ERL M86-65. Berkeley, USA.
  7. ↑ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (September 1987). "Multiple-valued logic minimization for PLA optimization". IEEE Transactions on Computer-Aided Design . 6 (5): 727–750. doi:10.1109/TCAD.1987.1270318. S2CID   13525177.
  8. ↑ Rudell, Richard L. (April 1989). Logic Synthesis for VLSI Design (PhD thesis). Berkeley: University of California. (ESPRESSO-EXACT)
  9. ↑ De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill Science Engineering. ISBN   0-07-016333-2.
  10. ↑ Lewin, Douglas (1985). Design of Logic Systems . Van Nostrand (UK). ISBN   0-442-30606-7.
  11. ↑ Katz, Randy Howard; Borriello, Gaetano (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. ISBN   0-8053-2703-7.
  12. ↑ Lala, Parag K. (1996). Practical Digital Logic Design and Testing. Prentice Hall. ISBN   0-02-367171-8.
  13. ↑ Theobald, Michael; Nowick, Steven M. (1998). Fast Heuristic and Exact Algorithms for Two-Level Hazard-Free Logic Minimization. Columbia University (Report). doi: 10.7916/D8N58V58 . Retrieved 2021-10-04.
  14. ↑ "Espresso C source code (1988)". University of California, Berkeley . 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
  15. ↑ "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.
  16. ↑ "Espresso heuristic logic minimizer C++20 Windows source". GitHub .
  17. ↑ "Logic Friday program (2012)". sontrak. 2018-09-21. Archived from the original on 2013-10-22. Retrieved 2018-09-21.
  18. ↑ "Espresso-IISOJS". GitHub .

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.