Karnaugh Maps Notes

IC 220

These notes are meant to supplement Appendix A in the textbook to describe how K-maps are used to minimize a sum-of-products (SOP) formula, and thereby reduce the number and size of gates in a circuit.

Minimization

The goal is to turn a truth table, with any number of inputs and a single output, into a sum-of-products formula and corresponding circuit with gates.

One way to do this is to write a single product for each “1” in the truth table, then add them all up into a single OR.

For example, given the following truth table:

A B C x
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

The first “1” in the column for x would be the single term \(\overline{A}\cdot\overline{B}\cdot{}C\). Applying this repeatedly, a SOP formula for the whole truth table is

\[\overline{A}\cdot\overline{B}\cdot{}C + A\cdot\overline{B}\cdot\overline{C} + A\cdot\overline{B}\cdot{}C + A\cdot{}B\cdot{}C\]

However, this is not the only way to write this formula as a sum of products. Generally, we would like to minimize the formula so that:

We could try and apply rules of boolean logic to simplify and minimize this formula “by hand”. But that can be difficult, and it’s hard to know when we’ve minimized enough. Fortunately there is another way.

Karnaugh Maps (K-Maps)

Karnaugh Maps (K-Maps) are one way to come up with a minimized SOP formula for a boolean function. It proceeds by building a truth-table with groupings of variables, which helps to minimize the results when forming a sum of products.

For example, we can rewrite the truth table from above as follows

\(\overline{B}\cdot\overline{C}\) \(\overline{B}\cdot{}C\) \(B\cdot{}C\) \(B\cdot\overline{C}\)
\(\overline{A}\) 0 1 0 0
\(A\) 1 1 1 0

Now we can group adjacent 1’s in rows and columns. For example, these two 1’s share A and not-B in common.

\(\overline{B}\cdot\overline{C}\) \(\overline{B}\cdot{}C\) \(B\cdot{}C\) \(B\cdot\overline{C}\)
\(\overline{A}\) 0 1 0 0
\(A\) (1) (1) 1 0

So the group of two 1’s circled above corresponds to the single boolean AND term \(A\cdot\overline{B}\).

Here is a group that shares A and C in common:

\(\overline{B}\cdot\overline{C}\) \(\overline{B}\cdot{}C\) \(B\cdot{}C\) \(B\cdot\overline{C}\)
\(\overline{A}\) 0 1 0 0
\(A\) 1 (1) (1) 0

And finally, these two share not-B and C in common:

\(\overline{B}\cdot\overline{C}\) \(\overline{B}\cdot{}C\) \(B\cdot{}C\) \(B\cdot\overline{C}\)
\(\overline{A}\) 0 (1) 0 0
\(A\) 1 (1) 1 0

The result is this minimized equation for the original truth table:

\[x = A\cdot\overline{B} + A\cdot{}C + \overline{B}\cdot{}C\]

K-map group rules

Not any group of adjacent ones can form a valid group. For example, you might have been tempted to group together the three 1’s on the bottom row of the previous example. But we can’t do that, because there wouldn’t be a single AND term that would correspond to those three 1’s.

Specifically, here are the “rules” for K-map groups that ensure each one corresponds to a single AND gate:

To make sure that we get a minimized SOP formula for the entire function, we must also ensure that:

4-way K-Maps

We can also do a K-map for 4 variables (or more!). Below is a 2x2 K-map for 4 input variables. Note that there is still only one output for a single K-map; if you have more outputs in your circuit, you need to do a different K-map for each output.

Let’s minimize the following truth table with 4 inputs:

A B C D x
0 0 0 0 1
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 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1

We can arrange the output of this truth table into a 2x2 K-map as follows:

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) 1 0 0 0
\(\overline{A}\cdot{}B\) 0 0 0 1
\(A\cdot{}B\) 0 1 1 0
\(A\cdot\overline{B}\) 1 1 1 1

Now let’s start making groups to find a minimal SOP formula.

First, can cover the entire bottom row with \(A\cdot\overline{B}\).

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) 1 0 0 0
\(\overline{A}\cdot{}B\) 0 0 0 1
\(A\cdot{}B\) 0 1 1 0
\(A\cdot\overline{B}\) (1) (1) (1) (1)

Then there is a bock of 4 in the which has \(A\cdot{}D\) in common

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) 1 0 0 0
\(\overline{A}\cdot{}B\) 0 0 0 1
\(A\cdot{}B\) 0 (1) (1) 0
\(A\cdot\overline{B}\) 1 (1) (1) 1

The next one is tricky to see - we can wrap around to cover two 1’s with \(\overline{B}\cdot\overline{C}\cdot\overline{D}\) in common

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) (1) 0 0 0
\(\overline{A}\cdot{}B\) 0 0 0 1
\(A\cdot{}B\) 0 1 1 0
\(A\cdot\overline{B}\) (1) 1 1 1

Finally, we are left with one “1” which must be left by itself because it’s entirely surrounded by 0’s, \(\overline{A}\cdot{}B\cdot{}C\cdot\overline{D}\).

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) 1 0 0 0
\(\overline{A}\cdot{}B\) 0 0 0 (1)
\(A\cdot{}B\) 0 1 1 0
\(A\cdot\overline{B}\) 1 1 1 1

This leaves us with the following minimized sum of products

\[A\cdot\overline{B} + A\cdot{}D + \overline{B}\cdot\overline{C}\cdot\overline{D} + \overline{A}\cdot{}B\cdot{}C\cdot\overline{D}\]

5-way K-maps (new section added for project help)

With 5 variables our truth table will have \(2^5=32\) rows. Here is an example truth table with 5 input variables:

A B C D E      X
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 1
0 0 0 1 1 1
0 0 1 0 0 1
0 0 1 0 1 1
0 0 1 1 0 1
0 0 1 1 1 1
0 1 0 0 0 0
0 1 0 0 1 0
0 1 0 1 0 1
0 1 0 1 1 1
0 1 1 0 0 0
0 1 1 0 1 0
0 1 1 1 0 0
0 1 1 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 0 0 1 0 0
1 0 0 1 1 1
1 0 1 0 0 1
1 0 1 0 1 1
1 0 1 1 0 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 0 0 1 1
1 1 0 1 0 0
1 1 0 1 1 1
1 1 1 0 0 0
1 1 1 0 1 1
1 1 1 1 0 0
1 1 1 1 1 1

Now that there are 32 truth table entries, we split the K-map into two parts depending on the first variable. So we basically get one 4x4 K-map with \(A=0\) and another 4x4 K-map with \(A=1\). Here’s what that looks like:

5way0

Now when we make groups, we have one more dimension to make the groups bigger - by having the same group on both sides of the K-map. In this case, we can group the second row on each side

5way1

This group in red corresponds to the term \(\overline{B}\cdot{}C\). Notice that it does not include \(A\) in the term, which is because the group goes across both sides of the K-map.

We can still have groups that are on one side of the K-map only, in which case \(\overline{A}\) or \(A\) has to be part of the term. A second group goes over the middle two columns of the right side:

5way2

This term for this second group is \(A\cdot{}E\).

One more group is needed to complete this K-map. This one is only on the left side:

5way3

The final formula is \(X = \overline{B}\cdot{}C + A\cdot{}E + \overline{A}\cdot{}\overline{C}\cdot{}D\)

K-Maps with “Don’t Cares!”

For many kinds of circuits, there are certain combinations of inputs which are impossible for some reason. Then we don’t care what the output is in those cases, because we can assume those inputs will never happen.

We draw these as an “X” in the truth table and the K-map. These can have either a 0 or 1, whichever helps the minimization.

\(\overline{C}\cdot\overline{D}\) \(\overline{C}\cdot{}D\) \(C\cdot{}D\) \(C\cdot\overline{D}\)
\(\overline{A}\cdot\overline{B}\) X 0 0 0
\(\overline{A}\cdot{}B\) 1 0 0 X
\(A\cdot{}B\) 1 1 1 1
\(A\cdot\overline{B}\) 1 0 0 0

With don’t-cares, we must cover all the 1’s, but we don’t have to cover all the X’s. And the X’s can be part of a group, or not.

In this case, we can cover all the 1’s, without including any 0’s, by just making one group for the first column and one group for the third row. That leaves one X inside a group, and one out of the groups, which is fine because we don’t care what the X’s are. Here is the corresponding minimized formula:

\[\overline{C}\cdot\overline{D} + A\cdot{}B\]

Other resources

Here are some pretty good YouTube videos if you want more guidance on the K-maps: