Karnaugh maps

Robert P. Webber, Longwood University

 

 

Once we have a canonical sum of products expression for a circuit, it would nice to have an algorithm for simplifying it.  Trial and error, or luck, are not very reliable!  Karnaugh maps are graphical tools for simplifying Boolean expressions.

 

There are two very useful equivalences for simplifying a sum of products form.  They are

 

           

 

and     

 

The first expression says that if a circuit has a sum of two products that differ only in one variable and its complement, we can eliminate those factors.  That is, if two terms differ in only one variable and its complement, the value of that variable will not affect the value of the term.  For instance,  .  Often, we can spot such reductions by hand.  However, if we have a canonical sum of products with four variables, say, it can be difficult to find two product terms that differ in only such factors.  A Karnaugh map can help.  It is a visual representation of the truth table that allows us to quickly find sum of products terms that differ in only factor and its complement.

 

A Karnaugh map is a rectangular grid whose variables are listed so only one change of value can occur between neighboring cells.  A Karnaugh map for two variables  x  and  y  is a  2 by  2  grid, since there are four possible combinations of values.

 

 

                            x     

                   0                1

                       

 

      0

y

 

      1

 

 

Notice that the square in the upper left corner, which corresponds to  00 , is adjacent to the squares corresponding to  01  and  10, which differ in only one value, but not to the square corresponding to  11, which differs in two values.

 

Next, write  1  in each square that corresponds to a row of the truth table with  1  in the result column.  For example, consider the function  f  defined by the table

 

            x          y          f

 

            0          0          0

            0          1          1

            1          0          0

            1          1          1

 

Its Karnaugh map is

 

                             x     

                   0                1

                       

1	1

 

      0

y

 

      1

 

 

Circle or highlight cells with adjacent 1s to make them stand out.

 

                            x     

                   0                1

                       

1	1

 

      0

y

 

      1

 

 

Looking at this map, there are two adjacent 1s, in the second row.  The variable that changes in that row is  x, so it can be eliminated.  Therefore, the circuit can be written simply as  y .

 

As a check, the canonical sum of products form is  , which simplifies to  .  Using the Karnaugh map avoids having to write the canonical sum of products form at all.

 

It might be easier to write   and  x  as the column headings and   and  y  as the row headings.

 

                    x’                x

 

1	1

    

    y’

 

 

     y

 

 

Use  x  and  y  as  1s and   and   as 0s if you do this.

 

For another example, consider the  xor  function.  Here’s the truth table.

 

            x          y          xor

 

            0          0          0

            0          1          1

            1          0          1

            1          1          0

 

A glance at the Karnaugh map shows that the canonical sum of products form  probably is as simple as we are going to get, because the  1s  are not adjacent.

 

                     x’                x

 

	1
1

 

   y’                                    

 

 

    y

 

 

 

Now let’s try a more complicated example:  the implication function.

 

            x          y          implies

 

            0          0          1

            0          1          1

            1          0          0

            1          1          1

 

The Karnaugh map is

 

 

                    x’                x

 

1
1	1

     y’

 

 

     y

 

 

 

We can use  x’y  twice!  By the idempotent law,  .  In the first column,  y  changes.  Eliminate it, leaving  x’.  In the second row,  x  changes.  Eliminate it, leaving  y .  The result is the simplified circuit  .

 

The Karnaugh map produces a minimal sum of products form.  It may be possible to simplify further using the laws of Boolean algebra, such as the distributive law, however.

 

Karnaugh maps also work for circuits with three variables.  There are eight possible combinations of values, which we arrange in a  2 by 4  array.

 

           x’y’(00)      x’y(01)    xy(11)      xy’(10)

 

z’(0)

 

 

 

z(1)

 

 

Notice we put  xy  in the third column.  Remember that adjacent cells must differ in only one value.  If we put  01  and  10  side by side, they would differ in two positions.

 

In three-variable maps, when two adjacent squares are marked with  1, one variable can be eliminated.  When four adjacent squares are marked with  1 (either arranged in a single row or arranged in a square), two variables can be eliminated.

 

Also notice that the left-most and right-most squares in a row differ in one variable, so we can consider them to be adjacent.  (They would be adjacent if we wrapped the map around a cylinder.)  Thus a highlighted expression can wrap around from left to right.

 

For example,

          x’y’    x’y       xy         xy’

 

1	1	1	1

     z’

                       

 

 

     z

 

 

simplifies to  z’ .

 

           x’y’    x’y       xy         xy’

 

1			1
1			1

     z’

 

 

 

     z

 

 

simplifies to  y’ .  Notice that we could also simplify to   if we grouped by twos instead of into a block of four.  How we group makes a difference!

 

We shouldn’t always use the largest possible grouping, however, as the next example shows.  It uses a  4 by 4  map, corresponding to a circuit with four variables.  There are  16  possible combinations, and we write them as shown.

 

  

              xy        xy’       x’y’       x’y

 

	1	1
		1	1
	1	1
		1	1

  zw

 

 

 

  zw’

 

 

 z’w’

 

 

z’w

 

 

 

If we group the cells in the third column, they simplify to  x’y’ .  The remaining four cells can be combined with adjacent cells, and the result is

 

 . 

 

The  x’y’  term is superfluous, because we used every square in the third column elsewhere.  That is, the result is simply

 

             .

 

In this case, it would be better to group by twos first.

 

Here’s an algorithm showing how to do it efficiently.

 

1.         Set up the map, putting 1’s in the proper cells.

2.         Form terms for and highlight any isolated marked cells (that is, cells that aren’t adjacent to any other marked cells).

3.         Combine unhighlighted, marked cells uniquely into two cell blocks, if possible, and highlight them.  If a marked cell can be part of a four cell (or larger) block, don’t highlight the two square block.

4.         Combine unhighlighted, marked cells uniquely into four cell blocks, if possible.

5.         Continue, combining unhighlighted cells uniquely into eight square blocks, 16 square blocks, etc., if possible.

6.         Combine any remaining unused cells into blocks as efficiently as possible.

 

Write Boolean expressions for the highlighted blocks and add them to get the simplified circuit.