1. Digital Logic
2. Topic: Introduction to Logic Minimization

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

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 you have a choice of logic circuits for any given logic relationship, you should first define which circuit is the best and develop a method to ensure you 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. In this case, most efficient circuit is the one that uses the minimum number of transistors, leaving speed and power for later consideration. Because the minimum-transistor measure of efficiency was chosen, the focus is on minimum circuits. The best method of determining which of several circuits is the minimum is to count the needed transistors. For now, a simpler method can be used‚ 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.

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, 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, you can 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).