Entry page for S0110 Digital Electronics site: week 22

INTRODUCTION TO KARNAUGH MAPS

This method of simplifying problems is really a graphical method which applies Boolean Agebra in a systemtic way. Perhaps an example is the best way of understanding how it works.

Suppose we have a control system which is very important, say part of an aircraft control. Our way of improving safety is to have several identical systems, at least three, and to take the majority of the three outputs. The idea is that the system will continue to work correctly in the event of a fault. Statistically ONE being faulty and TWO correct is much more likely than TWO being faulty and only ONE correct! So how is this done in a logic circuit. First we need to express the problem lgoically so a TRUTH table can be used here. Three systems so there will be three variables, A, B and C. The output should be a 1 when at least two of the three inputs are 1.

Truth Table for Problem

     C      B      A       OUTPUT
     0      0      0         0
     0      0      1         0
     0      1      0         0
     0      1      1         1
     1      0      0         0
     1      0      1         1
     1      1      0         1
     1      1      1         1

We could look at the table and make a few guesses as to the function OR we could use a method!

Look for the 1's in the the output and write down the inputs that cause them.
They are A.B.NOT C, A.NOT B.C, NOT A.B.C and A.B.C.
We could use this as a circuit design, but it would need FOUR 3 INPUT AND gates, THREE INVERTERS and ONE 4 INPUT OR gate to combine them. Could there be a simpler circuit? We can use KARNAUGH MAPS to find out.

Use of KARNAUGH MAPS

The MAP has locations for all the combinations of variables possible.

Blank KARNAUGH MAP

NOTE: the order of the values of the COLUMNS is "strange" in that "11" comes before "10".

The 1's from the TRUTH table are "plotted" on it.

Filled KARNAUGH MAP

Then these 1's are "grouped" together into the blocks with the largest even number possible, as shown below.

Grouped KARNAUGH MAP

Filled KARNAUGH MAP with "grouping"

Now write down the logical values of the groups "x", "y" and "z". Group "x" is completely in the C = 1 Column, completely in the B = 1 Column BUT has both A and NOT A Columns in it. The value must be C.B as A does not seem to matter! [PROOF: A + NOT A = 1, so (B.C).(A + NOT A) = (B.C).1 = B.C ]
Looking at "y", value is A.C and in "z", value is A.B. So the final simplified function is B.C + A.C + A.B. Can this really be right? Time for another TRUTH Table!

C   B   A   OUTPUT  A.B   A.C   B.C   FUNCTION
                    "x"   "y"   "z"    "x+y+z"                                     
0   0   0     0      0     0     0        0
0   0   1     0      0     0     0        0
0   1   0     0      0     0     0        0
0   1   1     1      1     0     0        1
1   0   0     0      0     0     0        0
1   0   1     1      0     1     0        1
1   1   0     1      0     0     1        1
1   1   1     1      1     1     1        1

The OUTPUT column is the same as FUNCTION x+y+z, which is A.B + A.C + B.C, so the circuit will simplify to THREE 2 INPUT AND gates and ONE 3 INPUT OR gate to combine them.

Going back to the original example problem, the system would be safer if we had four identical sections and took the majority of those. How do we do that with the KARNAUGH MAP? First we need to see how FOUR variables are coded on a MAP.

Blank FOUR Variable KARNAUGH MAP

Now we need a TRUTH Table to find the 1's to plot for this problem.

     D   C   B   A   OUTPUT
     0   0   0   0     0
     0   0   0   1     0
     0   0   1   0     0
     0   0   1   1     0
     0   1   0   0     0
     0   1   0   1     0
     0   1   1   0     0
     0   1   1   1     1
     1   0   0   0     0
     1   0   0   1     0
     1   0   1   0     0
     1   0   1   1     1
     1   1   0   0     0
     1   1   0   1     1
     1   1   1   0     1
     1   1   1   1     1

Now "plot" all the 1's on the MAP and group as before.

Grouped FOUR Variable KARNAUGH MAP

Filled FOUR Variable KARNAUGH MAP with "grouping"

The groups are indicated by "w", "x", "y" and "z", so we now write down what they are from the MAP. They are "w" = B.C.D, "x" = A.B.D, "y" = A.B.C and "z" = A.C.D. Could it really be this simple? Time for another TRUTH Table. O/P is the OUTPUT from the problem TRUTH Table and FUNC is the result of "w" + "x" + "y" + "z".

D   C   B   A  O/P "w" "x" "y" "z" FUNC
0   0   0   0   0   0   0   0   0   0
0   0   0   1   0   0   0   0   0   0
0   0   1   0   0   0   0   0   0   0
0   0   1   1   0   0   0   0   0   0
0   1   0   0   0   0   0   0   0   0
0   1   0   1   0   0   0   0   0   0
0   1   1   0   0   0   0   0   0   0
0   1   1   1   1   0   0   1   0   1
1   0   0   0   0   0   0   0   0   0 
1   0   0   1   0   0   0   0   0   0  
1   0   1   0   0   0   0   0   0   0
1   0   1   1   1   0   1   0   0   1
1   1   0   0   0   0   0   0   0   0 
1   1   0   1   1   0   0   0   1   1
1   1   1   0   1   1   0   0   0   1
1   1   1   1   1   1   1   1   1   1

Again the FUNCTION is equal to the output of the four variable problem, so the circuit can be built from FOUR 3 INPUT AND gates combined by ONE 4 INPUT OR gate. These two examples show how KARNAUGH MAPs are used, and how they apply to real digital electronic problems.