Logic Minimization

Efficiency of Different Implementations of Same Logic Functions

Logic Minimization

Efficiency of Different Implementations of Same Logic Functions

Same Logic Function, Different Circuit Implementations

A digital logic circuit consists of a collection of logic gates; the input signals that drive them, and the output signals they produce. The behavioral requirements of a logic circuit are best expressed through truth tables or logic equations, and any design problem that can be addressed with a logic circuit can be expressed in one of these forms. Both of these formalisms define the behavior of a logic circuit—how inputs are combined to drive outputs—but they do not specify how to build a circuit that meets these requirements.

Only one truth table exists for any particular logic relationship, but many different logic equations and logic circuits can be found to describe and implement the same relationship. Different (but equivalent) logic equations and circuits exist for a given truth table because it is always possible to add unneeded, redundant logic gates to a circuit without changing its logical output. Take for example the logic system introduced in the previous module (reproduced in Fig. 1 below). The system's behavior is defined by the truth table in the center of the figure, and it can be implemented by any of the logic equations and related logic circuits shown.

Figure 1. Six different circuit implementations of same logic function.

All six circuits shown are equivalent, meaning they share the same truth table, but they have different physical structures. Imagine a black box with three input buttons, two LEDs, and two independent circuits driving the LEDs. Any of the six circuits in Fig. 1 shown above could drive either LED, and an observer pressing buttons in any combination could not identify which circuit drove which LED. For every possible combination of button presses, the LEDs would be illuminated in exactly the same manner regardless of which circuit was used. If we have a choice of logic circuits for any given logic relationship, it follows we should first define which circuit is the best and develop a method to ensure we find it.

The circuits in the blue boxes above are said to be “canonical” because they contain all required minterms and maxterms. Canonical circuits typically use resources inefficiently, but they are conceptually simple. Below the canonical circuits are standard POS and SOP circuits—these two circuits behave identically to the canonical circuits, but they use fewer resources. It would clearly be less wasteful of resources to build the standard POS or SOP circuits. Furthermore, replacing logic gates in the standard circuits with transistor-minimum gate equivalents (by taking advantage of NAND/NOR logic) results in the minimized POS and SOP circuits shown in the green boxes.

Find the Most Efficient Circuit

As engineers one of our primary goals is to implement circuits efficiently. The most efficient circuit can use the fewest number of transistors, or it can operate at the highest speeds, or it can use the least amount of power. Often, these three measures of efficiency cannot all be optimized at the same time, and designers must trade-off circuit size for speed of operation, or speed for power, or power for size, etc. Here, we will define the most efficient circuit as the one that uses the minimum number of transistors, and leave speed and power considerations for later consideration. Because we have chosen the minimum-transistor measure of efficiency, we will look for “minimum” circuits. The best method of determining which of several circuits is the minimum is to count the needed transistors. For now, we will use a simpler method—the minimal circuit will be defined as the one that uses the fewest number of logic gates (or, if two forms use the same number of gates, then the one that uses the fewest number of total inputs to all gates will be considered the simplest). The following examples show circuits with the gate/input number shown below. Inverters are not included in the gate or input count, because often, they are absorbed into the logic gates themselves.

Figure 2. Count the number of logic gate and inputs to evaluate the efficiency of logic circuits.

A minimal logic equation for a given logic system can be obtained by eliminating all non-essential or redundant inputs. Any input that can be removed from the equation without changing the input/output relationship is redundant. To find minimal equations, all redundant inputs must be identified and removed. In the truth table in Fig. 1 above, note the SOP terms generated by rows 1 and 3. The A input is '0' in both rows, and the C input is '1' in both rows, but the B input is '0' in one row and '1' in the other. Thus, for these two rows, the output is a '1' whether B is a '0' or '1' and B is therefore redundant.

The goal in “minimizing” logic systems is to find the simplest form by identifying and removing all redundant inputs. For a logic function of N inputs, there are $2^{2^N}$ logic functions, and for each of these functions, there exists a minimum SOP form and a minimum POS form. The SOP form may be more minimal than the POS form, or the POS form may be more minimal, or they may be equivalent (i.e., they may both require the same number of logic gates and inputs). In general, it is difficult to identify the minimum form by simply staring at a truth table. Several methods have evolved to assist with the minimization process, including the application of Boolean algebra, the use of logic graphs, and the use of searching algorithms. Although any of these methods can be employed using pen and paper, it is far easier (and more productive) to implement searching algorithms on computer.

Important Ideas

  • Only one truth table exists for any particular logic relationship, but many different logic equations and logic circuits can be found to describe and implement the same relationship.
  • For now, we will use a simpler method—the minimal circuit will be defined as the one that uses the fewest number of logic gates (or, if two forms use the same number of gates, then the one that uses the fewest number of total inputs to all gates will be considered simplest).

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