Simplifying Circuits with Karnaugh Maps

Another way of finding the simplest solution to a logic gate problem is the use of the Karnaugh map.  Here is a truth table for an output with four different inputs, or a four-bit word.  You may wonder what this last term means:

• A word is a set of binary digits.  Computers use sixteen or thirty-two bit words, which means that they process groups of 16 or 32 binary digits.  8 binary digits is called a byte.  Here we have a group of four digits, not a very good medium for a computer.

• A bit is a binary digit, 1 or 0 (ON or OFF)

Look at this truth table:

There are seven rows in this truth table where the output is 1.  So we can write the Boolean expression:

This is a pretty ghastly expression.  Of course we can simplify it using the methods we saw above, but Karnaugh maps are much more helpful in this case.

Notice the order of the letters.  D is the most significant bit, and A is the least.

In the Karnaugh map we split up the truth table into a 4 x 4 matrix, with the rows identified by DC, and the columns identified with BA.  Notice the order of the two bit words.  One bit is the same as the neighbours.  The sum of adjacent bits has to be different.

If you can’t remember these, just learn the order, 00, 01, 11, 10.

We need to fill the table from the truth table above.  For example 00, 01 (Black arrows) gives a 1 and 01, 10 (Blue arrows) gives a 0. 

So we fill the table:

We can identify clusters of 1s:

These clusters have been marked P, R, S.  Let us look at group P.  We get a 1 in both cells when DC is 10.  We get a 1 in one of the cells when BA = 11, or when BA = 10. So we can write the Boolean expression for cluster P as:

We can rewrite this as:

Question 5.  Explain why P = D.C-bar.B   Click HERE for the answer.

Now let's do the same for R.

Question 6.  What is the Boolean expression for R?  Click HERE for the answer.

Question 7.  Explain why we can write R = D-bar.A.  Click HERE for the answer.

Now look at S.

Question 8.  What is the Boolean expression for S?  Click HERE for the answer.

Now we can put P, R, and S together:

Can we simplify this any further?  No (unless I have been very thick and overlooked a simple principle;  if so, please let me know your simplification).

To design the circuit, we need to think of the three inputs to OR gates:

1. D AND NOT C AND B

2. NOT D AND A

3. D AND C AND NOT A AND NOT B

We will build this up bit by bit, starting with Q.  Q = P + R + S.  Q is equal to P OR R OR S.

This is the output end of the circuit.  Now we will draw P = D.C-bar.B

Now we will draw R = D-bar.A

Then we can draw out S = D.C.B-bar.A-bar

Finally we can put the whole thing together:

In this last example, we have designed a rather complex system from a Karnaugh map.  We could test it out with a giant truth table, but it would get rapidly rather tedious.  For a more complex circuit it would be impossible.

BACK to Combinational Logic

Click HERE to go on to Building Circuits with NAND gates