Karnaugh Maps |
-
In a Karnaugh Map of any
size, crossing a vertical or horizontal cell boundary is a change of only
one variable - no matter how many variables there are.
-
Each single cell that
contains a 1 represents a minterm in the function, and each minterm can
be thought of as a "product" term with N variables.
-
To combine variables,
use groups of 2, 4, 8, etc. A group of 2 in an N-variable Karnaugh
map will give you a "product" term with N-1 variables. A group of
4 will have N-2 variables, etc.
-
You will never have a
group of 3, a group of 5, etc. Don't even think about it. See
the points above.
Let's look at some examples of groups in a 4-variable
Karnaugh Map.
Example 1
- A Group of 2
Here is a group of 2 in a 4-variable map.
Note that Y and Z are 00 and 01 at the top
of the two columns in which you find the two 1s.
The variable, Z, changes from a 0 to a 1 as you move from the left cell
to the right cell. Consequently, these two 1s
are not dependent upon the value of Z, and Z will not appear in the product
term that results when we combine the 1s in
this group of 2. Conversely, W, X and Y will be in the product term.
Notice that in the row in which the 1s appear,
W = 0 and X = 1. Also, in the two columns in which the 1s
appear we have Y = 0. That means that the term represented by these
two cells is:
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):-
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.
-
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.
|