This section
presents a technique for simplifying logical
expressions.
It will:
„ Define Karnaugh and establish the
correspondence between
Karnaugh
maps and truth tables and logical expressions.
„ Show how to use Karnaugh maps to
derive minimal sumof-products and product-of-sums expressions.
„
Introduce the concept of "don't
care" entries and show how
to extend
Karnaugh map techniques to include maps with
don't care
entries.
Karnaugh Map
Definitions
†A Karnaugh map is a two-dimensional
truth-table.Unlike
ordinary (i.e., one-dimensional) truth tables,however,
certain logical network simplifications can be easily
recognized from a Karnaugh map.
The interpretation
of a type 1 map is that the rows or columns
labeled with a variable correspond to region of the map
where that variable has value 1.
Exercise:
Plot the following expression on a Karnaugh map.
Z = (A•B)⊕(C+D)
Minimal
Sum-Of-Products Expressions
†Ordering of Squares
„ The important feature of the
ordering of squares is that the
squares are
numbered so that the binary representations for
the numbers
of two adjacent squares differ in exactly one
position.
‹This is due to the use of a Gray code
(one in which adjacent
numbers
differ in only one position) to label the edges of a type 2
map.
‹The labels for the type 1 map must be
chosen to guarantee this
property.
„
Note that squares at opposite ends
of the same row or
column also
have this property (i.e., their associated
numbers
differ in exactly one position).
For
k-variable maps, this reduction technique can also be applied
to groupings of 4,8,16,...,2k rectangles all of whose
binary numbers agree in (k-2),(k-3),(k-
4),...,0
positions, respectively.
Rules for
Grouping:
„ The number of squares in a grouping
is 2i for some i such
that 1 ≤ i ≤
k.
„ There are exactly k-i variables that
have constant value for
all squares
in the grouping.
†Resulting Product Terms:
„ If X is a variable that has value 0
in all of the squares in the
grouping,
then the literal X' is in the product term.
„ If X is a variable that has value 1
in all of the squares in the
grouping,
then the literal X is in the product term.
„ If X is a variable that has value 0
for some squares in the
grouping and
value 1 for others, then neither X' nor X are
in the
product term.
In order to
minimize the resulting logical expression,
the
groupings should be selected as follows:
„ Identify those groupings that are
maximal in the sense that
they are not
contained in any other possible grouping. The
product
terms obtained from such groupings are called
prime
implicants.
‹A distinguished 1-cell is a cell that
is covered by only one prime
implicant.
‹
An essential prime implicant is one
that covers a distiquished 1-
cell.
„
Use the fewest possible number of
maximal groupings
needed to
cover all of the squares marked with a 1.
†Examples:
Rules for
Grouping:
„ Same as for sum-of-products, except
that zero's are
grouped
instead of ones.
†Resulting Sum Terms:
„ If variable X has value 0 for
allsquares in the group, then
the literal
X is in the sum term.
„ If variable X has value 1 for all
squares in the group, then
the literal
X' is in the sum term.
„ If variable X has value 0 for some
squares in the group and
value 1 for
the others, then that variable does not appear in
the sum
term.
†Prime Implicate:
„ Maximal grouping of zeros
