Logic Minimization using Karnaugh Maps

Authored for CIT 593/CIS 240 - Farmer

In class we have learned about Boolean Algebra. It is the means by which we can write logic
functions. We have also learned that the identities and laws of Boolean Algebra can help us
reduce or minimize a function in Boolean Algebra. This can be very useful before we implement
a logic function in gates or in CMOS, as it reduces the number of components necessary.

Logic minimization using Boolean Algebra requires a great deal of patience and can be tedious
as we see how/where to apply the identities and laws. There are several “short cut” techniques
to Boolean Logic functions, all which are built upon Boolean Algebra, but do not require direct
use of the laws and identities. Once such technique is called known as the Karnaugh Mapping
technique.

In class we saw an example of using Boolean Algebra to minimize the following logic function:

(A OR B) AND B = B

If use a truth table to represent the expression above, we would have:

A B (A OR B) AND B
0 0 0
0 1 1
1 0 0
1 1 1

Using a PLA, we would simply result in the algebraic expression shown using gates:

Clearly, not the most efficient implementation! But if you were just given the Truth Table, you
may not have noticed that the output is really just the input B (as our Boolean Algebra
minimization had told us). Also, you could read from the PLA the “sum of products” expression
like this:

Y = (A’ AND B) OR (A AND B)

Ultimately, you could use Boolean Algebra to prove that these two expressions are equivalent,
but clearly, the PLA is not giving us the simplest form of things!
If the Boolean Algebra reduction is not obvious to you, there is a simpler more visual way to
reduce the logic, and that is by creating a Karnaugh Map (K-Map) of the truth table. We do that
by reorganizing the truth table like this:

A
B 0 1
0 0 0
1 1 1

The outputs (in red) are in the boxes in the center, the inputs (A & B) are on the perimeter of the
table. Notice it lines up the original truth table, when A=0, B=1, the output is 1, etc. To use the
K-map above to minimize our logic, we group the outputs together that form a 1:

A
B 0 1
0 0 0
1 1 1

What we notice a little more clearly with this form is that the input A is redundant! Why is that?
To obtain a 1 in this group, B must equal 1, but A could be either 0 or 1. So it really doesn’t
matter what A is as long as B = 0 or 1, hence A’s redundancy. If we were to write out the
produce of sums that we see in the K-map above, we’d write them the same way we produce a
PLA. Namely, the terms that produce a 1 are:

(A’ AND B) OR (A AND B)

The groups on the K-map help us see what terms are redundant. It is giving us a visual way to
see the Boolean identity: X OR X’ = 1
Example 2 – Intersection of groups:

Let’s take the Boolean function:

Y=(A’ AND B’) OR (A AND B’) OR (A’ AND B)

If we generate its Truth table and put it in K-map form, we would have:

A
B 0 1
0 1 1
1 1 0

We can form two groups of 1s as follows:

A
B 0 1
0 1 1
1 1 0
The first group (along the top row), consists of two 1s which correspond to A=0, B=0 and A=1,
B=0. For this row, when B=0, the output is 1 (regardless of what A is). So while this group
corresponds to the two expressions: (A’ AND B’) OR (A AND B’), it is clear that this group is
independent of A and can be represented with only B’

The second group (along the first column), consists of two 1s which correspond to A=0, B=0
and A=0, B=1. For this column when A=0, the output is 1 (regardless of what B is). So while
this group corresponds to the two expressions: (A’ AND B’) OR (A’ AND B), it is clear that this
group is independent of B and can be reduced simply to A’.

The intersection of these two groups tells us that we have the output of “1” whenever A=0 OR
B=0, or more simply Y=A’ + B’

Using the K-map, we were able to reduce:

Y=(A’ AND B’) OR (A AND B’) OR (A’ AND B) = A’ + B’

Also notice, you could immediately implement simplified expression (A’ + B’) at the gate-level as
is, but to implement this in CMOS, you would probably wish to apply DeMorgan’s law first to put
this in terms of inversions and NAND gates.
Example 3 – Three input K-maps

K-Maps can be used for problems with up to 6 inputs. This example will show how to tackle a
problem with 3 inputs. Given the following truth table, ABC are inputs and Y is the output:

A B C Y
0 0 0 0
0 0 1 1
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 convert it into K-map form (notice the order of the columns, it’s not sequential!):

AB
C 00 01 11 10
0 0 0 1 0
1 1 1 1 1

We circle the groups of 1s (they must be in powers of 2: 1, 2, 4, etc)

AB Group 1
00 01 11 10
C
0 0 0 1 0
1 1 1 1 1 Group 2

Within each group identify the redundant terms:

For Group 1:
• The top box corresponds to: ABC’, the bottom box corresponds to inputs: ABC
o That’s A and C and C’ (but written quickly: ABC’)
• Much like we did with PLAs, we OR Group 1’s AND’ed inputs together: ABC’ + ABC
• Now we minimize the group’s expression by identifying which input doesn’t change in
the group: inputs A and B are not changing in the group, so C is the redundant input
• The group’s expression is then: AB (you can show ABC’+ABC=AB with algebra too!)
For Group 2:
• The inputs in this group are: A’B’C + A’BC + ABC + AB’C
• Now we minimize the group’s expression by identifying which input doesn’t change in
the group: Notice “C” is the only term common to all of them
• The group’s expression is then minimized to C only

We see that the two groups intersect, so we write each group’s minimized expression ORed
together: AB + C. That’s pretty impressive without truly applying Boolean Algebra!
Example 4 – Four Input K-Maps and Rules of Grouping

If one had a Boolean Algebra function or a Truth Table with 4 inputs, the K-Map would be
ordered as follows (notice again the input values in the columns and rows are not sequential,
what they are is “Gray coded” meaning only 1 number changes as you go from one to the next.
This makes the grouping possible!

AB
CD 00 01 11 10
00 1 1

01
11
10 1 1

In the K-map above, we actually have 1 group! If you could imagine a k-map in 3 dimensions, it
“Bends” around like a toroid. The terms in the group are: A’B’C’D + AB’C’D’ + A’B’CD’+AB’CD’,
but its gets reduced to simply: B’ as that’s the only term common to all 4 outputs.

So what are all the rules of grouping you ask? They are as follows:

1. Groups should be as large as possible.

2. You want to make as small a number of groups as possible
3. No 0s allowed in groups
4. No diagonals
5. Only power of 2 number of cells in each group.
6. Every 1 must be in at least one group (even if that’s a group of just 1 term)
7. Overlapping allowed
8. Wrap around allowed (like in the group of four example above)

With a little practice you will have a great technique for avoiding lots of Boolean Algebra Proofs!