K-Maps with Multiple Outputs
Logic Minimization
Minimizing Circuits with Multiple Outputs
Circuits that have more complex inputs and outputs than we have previously discussed require less tedious and error-prone methods of analysis. Here we will discuss how multiple output systems are analyzed.
So far we have examined methods for minimizing simpler circuits that produce a single output based on some number of inputs. But since logic systems very often produce more than one output from the same set of inputs, we must examine the more general case of minimizing a circuit with N inputs and M outputs. In these more general and more complex designs, pencil and paper methods become unwieldy, and the use of computer-based methods becomes more imperative. In particular, logic systems involving more than 5 or 6 inputs and/or two or more outputs are best minimized using computer-based methods. And further, the use of computer-based tools can relieve designers from many tedious and labor-intensive design chores, thereby allowing more time to be spent investigating design requirements and experimenting with various design approaches. With computer-based methods, after various high-level design approaches have been analyzed, the best can be readily implemented using computer tools like minimizers, synthesizers, and optimizers.
An example of a four-input, three-output logic system is shown in Figs. 1 and 2. A design problem like this could be attacked as if it were composed of three unique, independent logic circuits, all of which just happen to use the same four inputs. This is illustrated in the figure below, where optimal solutions for each of the three circuits have been found independently of the others. These local minimum solutions are shown below labeled with the‚ LM‚ subscript. This one-at-a-time solution method is certainly the simplest, but it ignores any global optimization opportunities that may exist. Specifically, it may turn out that a more optimal overall solution can be found if all of the logic functions are analyzed at once, and (possibly) if one or two of the individual functions are allowed to be sub-optimal.
The process of finding a global minimum, as mentioned, can be quite tedious. We will discuss and illustrate the pencil-and-paper process here, but in practice we will use computer-based methods. The process starts by listing all possible product terms (including non-minimal terms) that could be used to define each output. Because these lists contain all possible terms that could be included in a logic circuit, they can be rather long. From these lists, all product terms and/or minterms that could be used in more than one equation are identified. Each of these shared product terms is inserted one by one into all local minimum equations that they can be used in, and after each insertion the system is re-checked to see if using the shared term results in a more minimum global solution. When all shared terms have been evaluated in local minimum equations, the process is complete and a true global minimum results.
The result of this process is illustrated below, where local minimum and global minimum solutions are shown for each output (see for example the XLM and XGM equations below). The X and Z outputs have local minimum circuits that are different than the global minimum circuits, but the Y output is the same regardless. For the X and Z outputs, the green loops show the sub-optimal groupings in individual maps used to arrive at a true global minimum. The GM equations that use locally suboptimal loops show their unique product terms in shaded boxes. Together, the global minimum requires 10 gates and 34 inputs, while the local minimums require a total of 12 gates and 37 inputs.
Computer-based algorithms like Espresso automatically search for global minimum solutions for multi-output logic systems, and these methods are far more practicable than the lengthy and error-prone pencil-and-paper methods.
