Karnaugh and Mahoney – Map Methods for Minimizing Boolean Expressions

Posted by admin  at October 19th, 2013

Karnaugh and Mahoney:

Map Methods for Minimizing Boolean Expressions

David Bonal

Abstract

In order to reduce a complicated Boolean expression, a vast knowledge of Boolean algebra is required.  Humans are very good at being able to compute data using graphical methods.  It is through the use of Karnaugh and Mahoney maps, that allows humans to be able to take a very complicated Boolean expression and minimize the expression using graphical methods.  So, the graphical methods provide another means of performing Boolean expression minimization without having to know the vast amounts of Boolean algebra.  It will be shown in this paper that there are two types of maps which produce minimized Boolean expressions. The goal of this paper is to provide a tutorial in how to use the two map methods, which will be a general rewrite of several sections in chapter three of Jerry D. Daniels’s Digital Design from Zero to One.

1  Introduction

Digital circuit design using combinational logic requires that the designer knows all of the possible combinations the inputs to the circuit can be, and what the output will be for each specific combination.  Truth tables provide a means of accomplishing this task.  For every  inputs to the circuit requires that there will be  possible combinations of input and output.  One can simply use the SOP or POS (described in Chapter 2 of Daniels) realizations to convert the  lines of the truth table into a non-minimized Boolean expression.   By using Karnaugh and Mahoney maps, the truth tables are converted into a graphical map.  One can gather sub-rectangles in the maps for reduced products of inputs [D] which will result in the most minimized Boolean expression.  The use of Karnaugh maps will be illustrated in the next section.  A more advanced mapping scheme, by the name of Mahoney will allow a graphical representation of an infinite sized truth table.  Mahoney maps will be presented in section three.  In section four,  an examination of why this paper presents better information than Daniels text will be given.

2  Karnaugh Maps

A Karnaugh map (K-map) is a rectangular form of a truth table with internal connecting squares.  Each square inside the truth table represents a minterm or maxterm of the truth table.  The size of the rectangle is 2 x 2 for 2 inputs, 4 x 2 for 3 inputs, 4 x 4 for 4 inputs, and for more than 4 inputs the maps become very difficult. The inputs of the truth table are represented on the K-map by all possible combinations of the input.  These inputs surround the top and left-hand side of the K-map by a positional binary code called Gray code.  Gray code only allows a one bit change between each successive input.  So, for a two bit input, the Gray code would be 00, 01, 11, 10, allowing only a one bit change between successive entries as shown in Fig. 2.1.

Once the minterms or maxterms are placed into the internal connecting squares the minimal expression can be gathered.  The goal is to gather the largest sub-rectangle of 1’s or 0’s as in Fig. 2.1.  The sub-rectangle must have a multiple of  1’s or 0’s in a cube or rectangle as illustrated in Fig. 2.1.  Multiple sub-rectangles can overlap, and sub-rectangles can wrap-around to the outside corners as in Ex. 2.1.  Once the gathering is finished, the law of adjacency is applied, and a product is formed by determining which bits do not change in the sub-rectangle as seen in Ex. 2.1.  Multiple formations of these products will result in an SOP.  By gathering 0’s instead of 1’s, the output of the Boolean expression will be the inverse of the 1’s gathering.  After the 0’s are gathered, applying  DeMorgan’s law to the SOP will form a POS expression.

Example 2.1

Find the minimum SOP and POS expressions using a K-map from the given truth table in Fig. 2.2.

Answer In order to solve this, the truth table must be converted into a K-map.  The largest subcubes and rectangles will be found for both the 1’s and the 0’s.

Figure 2.3 is the resultant K-map from the truth table.   The gathering of the 1’s is indicated by the solid ellipses, and the gathering of the 0’s is indicated by the dotted ellipses.  Now, it is possible to get the reduced expressions by determining which bits are changing in each sub- rectangle. Only the bits that remain the same in the gathering will be placed into the expression.

The simplest SOP is

By looking at the gathering of the 0’s, the simplest POS is

using DeMorgan’s law we get

and finally the POS is

3  Mahoney Maps:  Implementing the Sign of Zoro

A Mahoney Map (M-map) uses mirror images of itself, and places the minterms and maxterms in a Z formation within the map to reduce Boolean expressions.  M-maps can be easily expanded to handle an infinite line truth table. All M-maps are based on Fig.3.1. The maps can be continually expanded by taking the mirror image of the map and folding it to the right (Fig 3.2), and then on the next expansion the folding would occur to the bottom of the previous map (Fig. 3.3).  This folding is repeated until the desired size of map is produced.  The inputs to the M-map will use the actual variable names starting with the inverted variable.    Filling the map proceeds by following the Z formation.  One minterm or maxterm is placed into each square following the path of the Z.  The first four output terms of the lowest valued bit combinations in the truth table are placed onto the first Z formation, the second group of four output terms are placed on the next Z, this process continues until all of the output terms have been placed onto the map.   Every time a new fold is added, a new input variable is placed counterclockwise to the previous variable as in Fig. 3.4.  Once all of the output terms have been placed onto the map, the same gathering of either the 1’s or 0’s as was used in section 2, Karnaugh Maps, can be used to get the simplified Boolean expression.  By looking at the variables that don’t change in each sub-rectangle will lead to prime implicants.

Example 3.1

Find the minimum SOP and POS expression using an M-map from the given truth table in Fig. 3.5.

Answer  By following the folding pattern as stated previously, a four bit M-map is generated.  The output terms of the truth table are placed into the M-map successively following the Z formation, and the grouping order that is shown on Figure 3.3.

Figure 3.6 is the resultant M-map from the truth table.   The gathering of the 1’s is indicated by the solid ellipses, and the gathering of the 0’s is indicated by the dotted ellipses.  Now, it is possible to get the reduced expressions by determining which bits are changing in each sub-rectangle. Only the bits that remain the same in the gathering will be placed into the expression.

The simplest SOP is

By looking at the gathering of the 0’s, the simplest POS is

using DeMorgan’s law we get

and finally the POS is

4  Why Is This Better

Jerry D. Daniels, the author of Digital Design from Zero to One, gave an explanation of how to use Karnaugh maps in chapter three.  Daniels went into much depth of explaining K-maps through the use of Venn Diagrams.  There is a lot of useless information presented in Daniels before the practical concept of K-maps is presented.  The Daniels text is designed to present clear, concise information on how to solve various problems.  The use of Venn Diagrams to introduce K-maps was useless for the practical engineer.  The explanation in section two of this paper, presents all of the concepts that Daniels introduced on the basic uses of K-maps, but the only difference is that this paper killed less trees.  What took two pages in this paper, Daniels required thirteen.

This paper also introduced the concept of Mahoney maps.  M-maps are in many ways much better than K-maps in that they are easily expanded to as many inputs as is required.  Daniels, as well as many other authors, does not include any information on these very useful maps.  So, by including the information on M-maps extended the paper, but enhanced the overall content by a large factor.

5 Conclusion

Karnaugh and Mahoney maps provide a graphical means of reducing complicated Boolean expressions. K-maps are limited due to their difficulty of trying to represent more than five input truth tables.  M-maps can be easily expanded to infinite variable inputs.  Gathering of 1’s or 0’s in both maps requires that the sub-rectangle have no less than  2^n 1’s or 0’s.  The minimum expression can be found in both maps by determining which bits do not change in the sub-rectangle.  This paper provides information for  the pragmatic engineer wanting to minimize Boolean expressions.  Overall, M-maps provide a much more flexible approach to Boolean expression minimization’s.

References

[D]     Daniels, Jerry D. 1996.  Digital Design from Zero to One. New York: John Wiley & Sons.

[K]     Krehbiel, Paul.  Private communication.  5 Dec. 1996.