Saturday, 11 February 2012

K-maps


  • K -maps can be used to simplify functions up to 6 variables
  • K-maps are graphical representation of truth table
  • In k-map each square is adjacent to all the neighboring squares (cells whose binary representation differ by only one bit).
2-variable k-map:
3-variable k-map:
 
4-variable k-map:
5-variable k-map:
Minimization of switching functions using k-map:
  •  Minimal expression is nothing but function having minimum number of sum terms or product terms with minimum number of literals.
  • Two min terms are said to be adjacent if they differ by only one bit position in binary representation.
Procedure of minimization:
  • Always group squares in terms of powers of 2(i.e. 2, 4, 8, 16…)
  • Make as large groups as possible
  • Use as few no. of groups as possible to cover all min terms.
SOP Form:
Implicant: implicant is a product term that could be used to cover min terms of a function
Ex: a’bc, ab, b’ etc
Prime implicant: prime implicant is an implicant that is not part of any other implicant of the function. As min terms are combined prime implicants are formed
Essential prime implicant: is a prime implicant that covers at least one min term that is not covered by any other prime implicant.
Cover: cover of a function is a set of prime implicants for which each min term of the function is contained in by at least one prime implicant.


Ex:  minimize f= ∑ (3, 4, 5, 6, 7, 11, 12, 13, 15)
f= CD+A’B+BC’

POS form:
Implicate:  is a sum term that is um of one or more literals that could be used to cover max terms of the function.
Prime implicate:  prime implicate is an implicate that is not covered by any other implicate of the function.
Essential prime implicate: an essential prime implicate is a prime implicate that covers at least one max term that is not covered by any other prime implicate.
Ex: minimize f= π (0, 1, 2, 3, 6, 9, 14)
f=(C+D) (A+B’+D) (A’+B+D’)

Finding complement of a function using k-map:
Place one’s in the positions of min terms that are not given in the problem and minimize the k-map. The result is complement of the function.
Ex: find complement of f=∑ (3, 4, 5, 6, 7, 11, 12, 13, 15)
F’= ∑ (0, 1, 2, 8, 9, 10, 14)
 f=B'D'+ACD'+B'C'

Back                                               Contents                                               Next


No comments:

Post a Comment