K-maps (Karnaugh Maps)


  • A Tool to generate minimal size circuits
  • Graphical means of performing equivalent of algebraic implications
  • Places candidate terms for simplification together


    Example: Simplify the function f(xyz)=Sum(2,3,7). 

       x y z | f
-----------
 0 0 0 | 0
 0 0 1 | 0
 0 1 0 | 1
 0 1 1 | 1
 1 0 0 | 0
 1 0 1 | 0
 1 1 0 | 0
 1 1 1 | 1


Drawing K-maps

  • Terms which differ in only one variable are placed adjacent to each other.
  • Edges connected: toroidal topology.


K-maps for Sum-of-Product Design

  • A minimal sum-of-product design can be created as follows:
  • Create the K-map, entering a 1 or 0 in each square according to the desired logic function
  • Beginning with large rectangles and going to small rectangles, add rectangles until all     minterms are 'covered' (all '1's are included).
  • Generate the algebraic terms corresponding to the rectangles


Examples:



K-maps for Product-of-Sum Design


Product-of-sums design uses the same principles, but applied to the zeros of the function.

Example:

Designing with Don't-Care Values

    In some situations, we don't care about the value of a logic function.
    For example, if we use wxyz to represent a number from 0 to 9, we need not worry about the function value produced for wxyz = 10...15.
    For these situations, the function can be assigned an output in order to make the resulting circuit as simple as possible.
    Suppose we wish to implement the function
    f(wxyz)=Sum(3,5,6,7)
    and we have the don't-care condition of
    d=Sum(10,11,12,13,14,15).

    The sum-of-products implementation:

    The product-of-sums implementation: