LESSON 03 – KARNAUGH MAPS

LESSON NOTE

THE PROBLEM WITH SoP EQUATIONS

Most of the time, SoP equations are solutions that are unnecessarily complicated and use far too many gates. The example below shows this.

EXAMPLE OF EXCESSIVE GATE USAGE IN SoP EQUATIONS

Consider the SoP equation below:

ABC + ĀBC = Q

As long as B and C are 1, it doesn’t matter if A is 0 or 1. So we can eliminate A all-together from the solution.

And in fact, the optimal solution would be:

BC = Q

Note that this is an easy equation to simplify. Usually, it’s more difficult than this.

The issue with standard SoP equations that they need to be simplified. And simplifying these can be easy at times, but at other times, it can be messy.

KARNAUGH MAP

A solution to simplify a SoP equation is to use a Karnaugh map.

A Karnaugh map is simply a graphical representation of a truth table. However, the way that the graphical data is arranged allows us to simplify by grouping – something that our human brain is pretty good at doing.

EMPTY KARNAUGH MAPS

We will focus on using Karnaugh maps for 3-input and 4-input circuits. Things get complicated when you try to use a Karnaugh map for 5 or 6 input circuits.

Below are the two ways that you can arrange a 3-input Karnaugh map. They are both identical so you can use whichever one you prefer.

Here is a blank 4-input Karnaugh map:

Notice that in Karnaugh maps, the inputs are on the outside and the corresponding value of Q appears on the inside. So the value of Q when all inputs are zero appears at the top left.

Also, notice that the input values are not in the order you would expect. The “11” comes before the “10”. This is important. We will see why later.

EXAMPLE

Convert the following truth table to a Karnaugh map:

A	B	C	Q
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Solution:

We start with an empty 3-input Karnaugh map.

We consider the rows with Q=1 in the truth table. We place the 1s in the corresponding spots in the Karnaugh map.

The rest of the Q values in the truth table are zeros so we can fill the rest of the Karnaugh map with zeros.

GROUPING IN A KARNAUGH MAP

Once we have a Karnaugh map, we can groups all the 1s together. With these groups, we will be able to create a new simplified SoP equation.

Here are the rules about grouping:

· Group sizes must be a power of two – so 1, 2, 4, 8, 16, …

· Groups must be rectangular or square (vertically or horizontally).

· Groups can wrap to opposite side. For example, they start at the bottom and wrap to the top.

· Groups that are fully inside another group can be ignored.

· Groups that have their 1s covered by other groups can be ignored.

· You must always maximize your group sizes – even if it comes to partial overlap of groups.

EXAMPLES OF GROUPING

Given the following Karnaugh maps (on the left), circle the groups.

a)

b)

c)

FROM GROUPS TO TERMS

The purpose of groups is to figure out new simplified terms for a new SoP equation. Each group is a new term.

Going from a group to a term is very easy. We simply consider each of the 1s in the group and check which of their inputs are the same. Those inputs form the term.

EXAMPLES OF GOING FROM GROUPS TO TERMS

Give the term for each of the groups in the Karnaugh maps below.

a)

b)

SIMPLIFIED SoP EQUATION

We get our simplified SoP equation by simply adding (which is really an “or” operation) the terms together.

So for the following Karnaugh map,

The simplified SoP equation is: