| Karnaugh Maps |
Problem
P1.
Here is a Karnaugh map with two entries. Determine the
product term represented by this map.
Larger groups in Karnaugh Maps of any size
can lead to greater simplification. Let's consider the group shown shaded
below. There are four terms covered by the shaded area.
In the upper left:-
These terms can be combined (assuming they
are all ones in the Karnaugh Map!). The result is
By combining the first two
terms above (the two terms at the top of the Karnaugh Map):-
- By combining the last two
terms above (the two terms at the bottom of the Karnaugh Map):-
- Then, these two germs can be
combined to give:
Notice how making the grouping larger reduces
the number of variables in the resulting terms. That simplification helps when
you start to connect gates to implement the function represented by a Karnaugh
map.
By now you should have inferred the rules
for getting the sum-of-products form from the Karnaugh map.
- The number of ones in a group
is a power of 2. That's 2, 4, 8 etc.
- If a variable takes on both
values (0 and 1) for different entries (1s) in the Karnaugh Map, that
variable will not be in the sum-of-products form. Note that the variable
should be one in half of the K-Map ones and it should be zero (inverted) in
the other half.
- If a variable is always 1 or
always zero (it appears either inverted all the time in all entries that are
one, or it is always not inverted) then that variable appears in that form
in the sum-of-products form.
Now, let's see if you can apply those rules.
Problem
P2.
Here is a Karnaugh Map with four entries. What is the
sum-of-products form for the four ones shown?
P3.
Here is a Karnaugh Map with four entries. What is the
sum-of-products form for the four ones shown?
P4.
Here is a Karnaugh Map with four entries. What is the
sum-of-products form for the four ones shown?
P5.
Here is a Karnaugh Map with
eight entries. What is the sum-of-products form
for the four ones shown?
Some Further Observations
There are a few further observations that
should be made. Note the following.
- There may well be more than
one solution of equal complexity.
- Here is an example
Karnaugh Map. There are two groups that are obvious - one in orange,
and one in light blue.
- In this example, the two
terms shown are:
- There is still one
entry to account for. There is a 1
that can be joined to either of two other entries to form a group.
There is no best way to go on this. Either way will take the same
number of gates, inputs, etc.
And another observation
- If there are more than four
variables, it is still possible to use Karnaugh Maps, and you will find
larger Karnaugh Maps discussed in many textbooks. However, as the number of
variables increases it becomes more difficult to see patterns, and computer
methods start to become more attractive.
|
