|
There are several ways to attack a logic reduction problem. My favorite for small problems (2 terms to 5 max) is Karnaugh[1] mapping. The rules of mapping are to map the output terms into the boxes relating to each logic term.
The rules for setting up the map are that the terms can be associated any way we want, and in any order. But, only one of the associated terms is allowed to change from column-to-column or from row-to-row. In fact if you will look closely at the map to the right the order of change of the columns is different from the order of the rows. This was done purposely so that terms could be associated, but was not necessary. Although the map is flat, it should be thought of as a continous cylinder from side to side or top to bottom for association purposes.
From the given output formula (to be reduced):
| OUTPUT = | A\B\CD\ | + | A\BCD\ | + | AB\CD\ | + | ABC\D\ | + | ABCD\ | [2] |
Assuming this is a positive logic sum of products, the five terms can be plotted into the Karnaugh map (at the right) putting a '1' where each term is satisfied.
The next step is grouping, and is where the Karnaugh map shines since it is graphical. Rules for grouping are to associate common terms that are in a single column, a single row, or a group of adjacent columns and rows. Again, assuming positive logic we want to group together the '1's.
The first grouping are the four '1's in the column CD\. It does not matter what other state if the term CD\ is true then the output will be true. We, therfore, have our first term.
The second grouping are the two '1's at the row AB. But here, D\ must also be true. The output is independent only of C. The second and final reduced term is ABD\.
OUTPUT (reduced) = CD\ + ABD\