1. Digital Logic
2. Topic: Computer-Based Logic Minimum

Introduction

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.

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.

Important Ideas

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