K-map grouping is always done in 2^n - Why?

Replies

• 

  Jeffrey Arulraj

  Well in logic expression say
  
  A'B+AB we group like this B(A'+A) so that the Logical law can be applied and the resultant can be verified as B
  
  Like wise in any of the laws direct simplification is done only when a pair of variable and its complement exist in an equation
  
  That is why we take them as pairs of 2^n
• 

  pikachu1994

  Can u explain it more?
• 

  rahul69

  Well the concept is simple, as there are only Two States , 1 and 0 (eg: A and A'), so for covering all the combinations, it is constructed in the form of 2^n
• 

  pikachu1994

  jeffrey samuel

  Well in logic expression say
  
  A'B+AB we group like this B(A'+A) so that the Logical law can be applied and the resultant can be verified as B
  
  Like wise in any of the laws direct simplification is done only when a pair of variable and its complement exist in an equation
  
  That is why we take them as pairs of 2^n

  Thank you

  rahul69

  Well the concept is simple, as there are only Two States , 1 and 0 (eg: A and A'), so for covering all the combinations, it is constructed in the form of 2^n

  Thank you
• 

  Jeffrey Arulraj

  We need even no of common entries to cancel them out
  At any time we need a variable and its complement
  
  Just check this out
  
  ABC+ABC'+AB'C+A'B'C
  
  When simplifying this equation we do this
  AB(C+C') + B'C(A+A')
  
  Here in this part A and C are variable and A' and C' are their complements when we add the two we get 1
  ie A+A' = 1 (by Boolean law)
  
  We do the same in a Kmap we root out terms which exist in both as a variable and its complement to simplify the equation That is why pairs always are in 2 ^ n terms
  
  Take a simple eg simplify this f=sum of (m0,m1,m2)
  
  This needs a two variable Kmap and eqn is rewritten as f=sigma(0,1,2)
  
  A\B 0 1
  0 1 1
  1 1
  
  We pair both vertically to get an expression B'
  And horizontally to get the expression A'
  
  So F=A'+B'
  
  Now solve the same problem as minterms
  F=A'B'+A'B+AB'
  F=B'(A+A')+A'B
  F=B'+A'B AS (A+A'=1)
  F=B'+A' AS{X+YZ=(X+Y).(X+Z)}
  
  Here X=B' ::Y=A':: Z=B
  and so (B'+B)(B'+A')=B'+A'
  
  This is a long and tedious process by which we can clearly see why we pair in even no of terms
  
  In the case of higher pair rates like 4 or 8 we do the pairing in steps till we get the simpler expressions
• 

  pikachu1994

  jeffrey samuel

  We need even no of common entries to cancel them out
  At any time we need a variable and its complement
  
  Just check this out
  
  ABC+ABC'+AB'C+A'B'C
  
  When simplifying this equation we do this
  AB(C+C') + B'C(A+A')
  
  Here in this part A and C are variable and A' and C' are their complements when we add the two we get 1
  ie A+A' = 1 (by Boolean law)
  
  We do the same in a Kmap we root out terms which exist in both as a variable and its complement to simplify the equation That is why pairs always are in 2 ^ n terms
  
  Take a simple eg simplify this f=sum of (m0,m1,m2)
  
  This needs a two variable Kmap and eqn is rewritten as f=sigma(0,1,2)
  
  A\B 0 1
  0 1 1
  1 1
  
  We pair both vertically to get an expression B'
  And horizontally to get the expression A'
  
  So F=A'+B'
  
  Now solve the same problem as minterms
  F=A'B'+A'B+AB'
  F=B'(A+A')+A'B
  F=B'+A'B AS (A+A'=1)
  F=B'+A' AS{X+YZ=(X+Y).(X+Z)}
  
  Here X=B' ::Y=A':: Z=B
  and so (B'+B)(B'+A')=B'+A'
  
  This is a long and tedious process by which we can clearly see why we pair in even no of terms
  
  In the case of higher pair rates like 4 or 8 we do the pairing in steps till we get the simpler expressions

  Thanks
• 

  simplycoder

  Just 2 cents from my side, if you observe carefully, the adjacent squares have only one bit which is complement of itself for example take 4 variable K-map.
  
  | 0 | | 1 | | 3 | | 2 |
  - - - - - - - -
  
  | 4 | | 5 | | 7 | | 6 |
  - - - - - - - -
  | 12 | | 13 | | 15 | | 14 |
  - - - - - - - -
  | 8 | | 9 | | 11 | | 10 |
  - - - - - - - -
  
  So see that fact that 0 represented by 0000, 1 by 0001 only one bit is different.
  now take 1 and 3 0001 and 0011
  
  This is valid for all the positions in horizontal as well as vertical configuration.
  So you can try for all of them,
  this type of encoding is called as Gray code