Make your own free website on Tripod.com
 Search: Lycos Tripod      50 Cent
share this page Share This Page  report abuse Report Abuse  build a page Edit your Site  show site directory Browse Sites  hosted by tripod
    Previous | Top 100 | Next hosted by tripod

Chapter 6 - Karnaugh Maps

Introduction to Karnaugh maps (K-maps)

In case you are wondering, it's pronounced "Karno", named after the French mathematician who developed them. They formalise the techniques for simplification that we learned in the previous chapter, and allow us to produce the smallest, most efficient AND-OR network for any particular truthtable.

Suppose we have a circuit with two variables, A and B. We can write the possible outputs of the circuit either in a truthtable or in a square grid, as shown below:

A
B
Output
0
0
0
0
1
1
1
0
1
1
1
0

You may recognise the truthtable above. It's the truthtable for the Exclusive-Or gate. Each of the outputs has been transferred to the grid, so that the top-left square represents the combination of inputs A = B = 1, the top-right square represents the combination A = 0, B = 1 etc. This is the K-map for two inputs. We don't use a K-map for only two variables much as its scope is so limited. In fact, this is the only time in this report that you'll see me refer to it. We can draw a similar K-map for three inputs, A, B and C:

A
B
C
Output
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1

Here it is a little more complex as we have to show each value of A and each value of B twice. The left-most column of the square grid represents possible input where both A and B are 0 (with the upper cell representing C = 1 and the lower one C = 0). The next column along represents the possible inputs where A = 0 and B = 1 etc. I have coloured the 1s in the grid specially so you can match them to the truthtable. We can even draw a Karnaugh map for four variables. I will dispense with the truthtable as you probably have the correct idea:

Looking along the edges of the square, you can see that it's important that the digits be staggered. The pattern of digits along the edge labelled A does not match that along the edge labelled B. Instead, the pattern is "offset" by one digit. Similarly, the edge labelled D has the same pattern as that on the edge labelled C except that it is offset by one place. This is done to ensure that the K-map can represent all combinations of inputs. The following grids, for instance, would not be valid Karnaugh maps:

Of course, it gets a little harder if you want to represent five variables in a Karnaugh map. in that case you would probably have to draw two 4-by-4 grids, one representing E = 0, and the other E = 1.

Rules for drawing loops

So, how do these diagrams help us to simplify circuits? Well, to answer that question, we need to see how we can draw loops around the elements as shown in this example:

Each loop represents a particular AND gate with its own particular inputs. Here are the rules

  1. Loops can overlap.
  2. Loops are only ever drawn to enclose 1s, never 0s.

       
       

  3. Loops are only ever drawn horizontally or vertically on the K-map, never diagonally.
  4. Loops are only ever drawn to enclose 2, 4 or 8 (or conceivably 16) 1s. It must be a power of 2:

      
    Two loops, each enclosing four 1s is legal.
      
    One loop enclosing six 1s is not!

    (In those last two examples, I have followed the time-honoured tradition of lazy engineers and omitted to draw the 0s in the K-map. Wherever you see an empty square, just imagine that there is a 0 in it. This is quite a common practice).

  5. Loops cannot "bend" to form an L-shape. They must form plain squares or rectangles.

       
       

  6. Loops can extend off the diagram to one side as long as they reappear on the other side and obey all the rules above:

       

    This is akin to sailing around the world. You disappear off one side of the map and reappear on the other side.

  7. There may, of course, be some 1s which cannot be legally included in loops, as shown in the diagram below. These are just left unlooped:

       

Before we go on to how these loops may be interpreted, I would like to show you one more example of a legally looped map and one more example of an illegally looped one:

   
   

Translating K-maps into circuits

Each one of the loopings and un-looped 1s represents an AND gate. An unlooped 1 represents an AND gate with the same number of inputs as have been included in the diagram:

This 1 represents an AND gate responding to A = 1, B = 0 and C = 1

Loops which include two items correspond to AND gates with all the inputs except one. The input that drops out is the one that changes as you pass from one end of the loop to the other. For instance in this K-map:

The loop covers a transition from C = 0 to C = 1 with all the other inputs equal to 1. This corresponds to the gate shown - it has inputs which activate when A = B = D = 1, but no input for C. In the notation, the two ones would represent A.B.C.D + A.B.C.D which collapses to give A.B.D.

The same thing applies for loops that cover four 1s, except that in this case 2 inputs drop out - the two that change as you move around the loop. This applies whether the loop is a 4-by-1 loop or a 2-by-2 loop:

Corresponds to C = D = 1 regardless of the state of A and B.
Corresponds to A = C = 0 regardless of the state of B and D.

Don't be put off if the loop goes off one end of the map and reappears at the other side. You still lose inputs:

In fact, a loop covering 8 items would give a single input, which would not have to be fed into an AND gate. Instead, it would be fed straight into the OR gate into which all the other AND gates fed:

A + B.C.D + B.C.D

In this case, that first term (the A) derives from the loop containing eight 1s on the left of the Karnaugh map.

More examples

Here are some more Karnaugh maps and the algebraic expressions that they produce:

A.B + B.D + A.D
A.C + A.B + A.C
A.B.D + B.C.D + A.C.D + A.B.C.D + A.B.C.D + A.B.C.D
In this case, no looping is possible and so there are 4 separate terms - well, you can't get a coconut every time!

A.B.C + A.B.C + A.B.C + A.B.C



Go back

Main Menu

Questions

Go on