This page will introduce the two major algorithms used to analyze and minimize logic systems. Both are still valid and used algorithms, however, one is more widely used than the other. This page will not go into detail on the inner workings of these algorithms, but it will give a basic overview.

Several logic minimization algorithms have been developed over the
years, and many of them have been incorporated into computer-based
logic minimization programs. Some of these programs, such as those
based on the *Quine-McCluskey* algorithm; find a true minimum
by exhaustively checking all possibilities. Programs based on
exhaustive search algorithms require long execution times when dealing
with large numbers of inputs and outputs. Other programs, such as the
popular *Espresso program* developed at UC Berkeley, use
heuristic (or rule-based) methods instead of exhaustive searches.
Although these programs run much faster (especially on moderate to
large systems), they terminate upon finding a “very good” solution
that may not always be minimal. In many real-world engineering
situations, finding a greatly minimized solution quickly is often the
best approach.

Espresso is by far the most widely used minimization algorithm, followed by Quine-McCluskey. These two algorithms will be briefly introduced, but not explained. Many good references exist in various texts and on the web that explain exactly how the algorithms function—you are encouraged to seek out and read these references to further your understanding of logic minimization techniques.

The Quine-McCluskey logic minimization algorithm was developed in the mid-1950s, and it was the first computer-based algorithm that could find truly minimal logic expressions. The algorithm finds all possible groupings of 1's through an exhaustive search, and then from that complete collection finds a minimal set that covers all minterms in the on-set (the on-set is the set of all minterms for which the function output is asserted). Because this method searches for all possible solutions, and then selects the best, it can take a fair amount of computing time, In fact, even on modern computers, this algorithm can execute for minutes to hours on moderately sized logic systems. Many free-ware programs exist that use the Q-M algorithm to minimize a single equation or multiple equations simultaneously.

Espresso was first developed in the 1960s, and it has become the most commonly used logic minimization program used in industry. Espresso is strictly “rule-based”, meaning that it does not search for a guaranteed minimum solution (although in many cases, the true minimum is found). An espresso input file must be created before Espresso can be run. The input file is essentially a truth table that lists all the minterms in the non-minimized function. Espresso returns an output file that shows all the terms required in the output expression. Espresso can minimize a single logic function of several variables, or many logic functions of several variables. Espresso makes several simplifying assumptions about a logic system, and it therefore runs very quickly, even for large systems.

Digimin is a windows wrapper that allows both Boozer and Espresso to
be run in a Microsoft Windows^{®} environment. Digimin also provides
an easy to use truth table entry mechanism and provides output in the form of SOP
and POS equations. Digimin, available from the class website, is easy and
intuitive to use—simply run it, add functions (by selecting Action
-> add function), and then add variables to the functions (by
selecting Action -> add variables). When all functions and variables
have been added, simply choose the MIN function and the Espresso or
Boozer algorithm.

Since the 1990s, *Hardware Definition Languages* (HDLs) and
their associated design tools and methods have been replacing all
other forms of digital circuit design. Today, the use of HDLs in
virtually all aspects of digital circuit design is considered standard
practice. We will introduce the use HDLs in a later module, and as we
will see, any circuit defined in an HDL environment is automatically
minimized before it is implemented. This feature allows a designer to
focus strictly on a circuit's behavior, without getting slowed down in
the details of finding efficient circuits. Although it is important to
understand the structure and function of digital circuits, experience
has shown that engineers can be far more productive by specifying only
a circuit's behavior, and relying on computer-based tools to find
efficient circuit structures that can implement those behaviors.

- Some minimization programs like the Quine-McCluskey find the true minimum by checking all possibilities.
- Other programs, such as the popular Espresso program developed at UC Berkeley, use heuristic (or rule-based) methods instead of exhaustive searches.
- Since the 1990's, Hardware Definition Languages (HDLs) and their associated design tools and methods have been replacing all other forms of digital circuit design.

*Other product and company names mentioned herein are trademarks or trade names of their respective companies. © 2014 Digilent Inc. All rights reserved.*