ABSTRACT
Typically, wemust have a circuit format inmind before a criterion for the simplest logic circuit can be defined. When implementing a logic function, it is often desirable that we keep the number of logic gates as well as the number of literals to a minimum. Boolean expressions with fewer logic operators imply fewer gates and fewer gate inputs per gate, thus enabling us to design inexpensive logic circuits. At the same time, we need to be cognizant of the fact that minimizing the number of operators may help us to minimize the cost, but that may cause larger propagation delays. But to minimize the overall propagation delay, one needs to reduce the number of operators on each critical path from input to output. Boolean functions can be simplified by algebraic means, but the process is often tedious and the designer cannot be certain that the manipulations have produced the minimum logical function. Depending on the sequence in which the Boolean theorems are used, we may end up with different reduced forms. A much easier and faster method of minimization is considered in this chapter. This method involves plotting function minterms on a two-dimensional map. This mapping scheme identifies all of the cases for a given set of input variables of the formA+A¯ = 1. When suchminterm groups have been identified, the redundant variables can be eliminated, thus yielding a simplified function for the output. Following the rules that are yet to be identified in this chapter, algebraic manipulations will be traded for graphical methods. The graphical technique, which was proposed by Veich and later modified by Karnaugh, allows minimized 2-level functions to be obtained with very little effort. This particular map is referred to as Karnaugh map, or K-map, for short. It must be noted though that designers may often use devices other than gates for real-
izing complex logic functions. For example, read-only-memory as well as programmable logic devices can be used to generatemultiple functions ofmultiple-input variableswithout regard to much minimization. Consequently, the traditional demand for absolute minimization has been diminished somewhat in recent years by the introduction of such devices. However, there aremany occasionswhen it is absolutely necessary to reduce complex logic functions. The choice between a simpler logic circuit and a faster logic circuit is generally a matter of judgement. Higher speed often means higher cost. The cost, on the other hand, is a composite function of the number of logic gates, the number of logic layers, and the number of inputs per gate in each of these layers. The exact ratio between the cost of a logic gate and the cost of logic gate input depends on the type of logic gate being used. In most cases, however, the cost of an additional logic gate will be several times that of an additional gate input on an already existing logic gate. When speed, for example, is
61313: “61313_c003” — 2007/10/3 — 16:23 — page 70 — #2
Digital Design: Basic Concepts and
the central issue, either a sum-of-product (SOP) or a product-of-sum (POS) expression is desirable for the most simplified logic function. For certain circuit technology, one may not assign any cost to inverting the variables. In such cases, both complemented and uncomplemented literals are assumed to be available when needed throughout the logic network. Unfortunately, K-map-based scheme is neither suited for solving problems involving
more than six input variables nor easily programmable. In this chapter, therefore, we also present a minimization algorithm, known as Quine-McCluskey’s (Q-M) tabular reduction technique, that is reasonably straightforward. It is possible to come up with more than one valid minimization of a function if K-maps are used because of the different ways the maps may be interpreted. The Q-M technique, in comparison, uses a systematic method to conduct an exhaustive search to determine all possible combinations of logically adjacent minterms. Typically, the technique converges to the same optimum solution for the logic function. However, the technique is often time consuming, especially for functions having multiple-input variables. But since it follows a systematic and algorithmic approach, it is possible to write software programs based on the Q-M method to allow computer-aided design of logic circuits. The Q-M technique can also be used to optimize multiple-output logic functions for circuits that have one or more common input variables.
