# Karnaugh Maps Notes

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:

- It has the fewest number of terms added together (fewest number of AND gates); and
- Each term has as few variables as possible (fewest number of inputs to each AND gate).

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:

- Groups must contain only 1’s inside.
- Groups must be a rectangle — although this rectangle
**can wrap around the top or bottom of the table** - The sides of the rectangle must be a power of two: 1, 2, or 4.

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

- Every 1 is covered by at least one group.
- There are as few groups as possible.
- Each group is as large as possible.

# 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:

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

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:

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:

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:

https://www.youtube.com/watch?v=CpsJoAwreqo Only 5 minutes long, this one is pretty quick but gives a good explanation. They use some terms that are different from ours, such as the fancy word “Implicant” where we have been using the word “Group”.

**Caution**:There is a small error near the end of the video. The group in red should be \(\overline{a}\cdot{}b\cdot{}c\), not \(\overline{a}\cdot{}b\cdot{}d\) as it is shown.

https://www.youtube.com/watch?v=3vkMgTmieZI This one is a little longer, and goes through more example in more details.

https://www.youtube.com/watch?v=95xLK7gHGlE Same presenter as the first video, but this one goes into how Don’t-Cares work with K-maps.