# Logic Simplification With Karnaugh Maps

The
logic simplification examples that we have done so could have been
performed with Boolean algebra about as quickly. Real world logic
simplification problems call for larger Karnaugh maps so that we may do
serious work. We will work some contrived examples in this section,
leaving most of the real world applications for the Combinatorial Logic
chapter. By contrived, we mean examples which illustrate techniques.
This approach will develop the tools we need to transition to the more
complex applications in the Combinatorial Logic chapter.

The logic simplification examples that we have done so could have been
performed with Boolean algebra about as quickly. Real world logic
simplification problems call for larger Karnaugh maps so that we may do
serious work. We will work some contrived examples in this section,
leaving most of the real world applications for the Combinatorial Logic
chapter. By contrived, we mean examples which illustrate techniques.
This approach will develop the tools we need to transition to the more
complex applications in the Combinatorial Logic chapter.

We show our previously developed Karnaugh map. We will use the form on the right.

Note the sequence of numbers across the top of the map. It is not in binary sequence which would be 00, 01, 10, 11. It is 00, 01, 11 10,
which is Gray code sequence. Gray code sequence only changes one binary
bit as we go from one number to the next in the sequence, unlike
binary. That means that adjacent cells will only vary by one bit, or
Boolean variable. This is what we need to organize the outputs of a
logic function so that we may view commonality. Moreover, the column and
row headings must be in Gray code order, or the map will not work as a
Karnaugh map. Cells sharing common Boolean variables would no longer be
adjacent, nor show visual patterns. Adjacent cells vary by only one bit
because a Gray code sequence varies by only one bit.

If we sketch our own Karnaugh maps, we need to generate Gray code for
any size map that we may use. This is how we generate Gray code of any
size.

Note that the Gray code sequence, above right, only varies by one bit as
we go down the list, or bottom to top up the list. This property of
Gray code is often useful in digital electronics in general. In
particular, it is applicable to Karnaugh maps.

Let us move on to some examples of simplification with 3-variable
Karnaugh maps. We show how to map the product terms of the unsimplified
logic to the K-map. We illustrate how to identify groups of adjacent
cells which leads to a Sum-of-Products simplification of the digital
logic.

Above we, place the 1’s in the K-map for each of the product terms, identify a group of two, then write a

*p-term*(product term) for the sole group as our simplified result.
Mapping the four product terms above yields a group of four covered by Boolean A’

Mapping the four p-terms yields a group of four, which is covered by one variable C.

After mapping the six p-terms above, identify the upper group of four,
pick up the lower two cells as a group of four by sharing the two with
two more from the other group. Covering these two with a group of four
gives a simpler result. Since there are two groups, there will be two
p-terms in the Sum-of-Products result A’+B

The two product terms above form one group of two and simplifies to BC

Mapping the four p-terms yields a single group of four, which is B

Mapping the four p-terms above yields a group of four. Visualize the
group of four by rolling up the ends of the map to form a cylinder, then
the cells are adjacent. We normally mark the group of four as above
left. Out of the variables A, B, C, there is a common variable: C’. C’
is a 0 over all four cells. Final result is C’.

The six cells above from the unsimplified equation can be organized into
two groups of four. These two groups should give us two p-terms in our
simplified result of A’ + C’.

Below, we revisit the Toxic Waste Incinerator from the Boolean algebra
chapter. See Boolean algebra chapter for details on this example. We
will simplify the logic using a Karnaugh map.

The Boolean equation for the output has four product terms. Map four 1’s
corresponding to the p-terms. Forming groups of cells, we have three
groups of two. There will be three p-terms in the simplified result, one
for each group. See “Toxic Waste Incinerator”, Boolean algebra chapter
for a gate diagram of the result, which is reproduced below.

Below we repeat the Boolean algebra simplification of Toxic waste incinerator for comparison.

Below we repeat the Toxic waste incinerator Karnaugh map solution for
comparison to the above Boolean algebra simplification. This case
illustrates why the Karnaugh map is widely used for logic
simplification.

The Karnaugh map method looks easier than the previous page of

boolean algebra.

boolean algebra.

## No comments