Category: K Maps

Categories
K Maps

K-maps for XOR and XNOR gates

 Even variable map: For 4 variables (even), we have XOR and XNOR compliment of each other and can be represented in K-maps as follow: For XNOR gate we have 2n/2 number of min terms with output as 1 (i.e. we have even number of 0s)

For XOR gate we have 2n/2 number of min terms with output as 1 (i.e. we have odd number of 1s)

From the K-maps also we can we that both the function are compliment of each other. Where we have 1 in one K-map, we have the 0 for the corresponding square in other K-map and vice versa.Odd variable map: For 3 variables (odd), we have XOR and XNOR equal to each other and can be represented in K-maps as follow: 

And equation is While the compliment of the above is represented by 

The above map can be represented by either  which is compliment of 

Categories
K Maps

Example: K MAPS FACTS

Q- Simplify the following Boolean function in (a) sum of products form (SOP)

(b) Product of sums form (POS)

F(x, y, z, w) = ∑(0, 1, 2, 5, 8, 9, 10)

Ans: We mark 1s in the squares corresponding to the terms present in the function and 0s for the terms missing from the function as follow:

1s marked represent min terms and 0s represent max terms

  1. Combine 1s and make groups of adjacent squares.

This is the wrong way of grouping as we always have to make largest groups.

So the correct way of grouping is as follow:

All the corner squares form one group of 4

Also rightmost two squares of top and bottom row form one group of 4

And third we have a group of 2

From this map table we get the simplified expression as F= y’w’+y’z’+x’z’w and so we get SOP form

  1. Combine 0s and try to make groups of maximum size

This is the wrong way of grouping as we always have to make largest groups.

So the correct way of grouping is as

From this map, we get the simplified expression of compliment function as  F’= xy+zw+yw’ in SOP form

Now take compliment of the function to get POS form

F= (xy+zw+yw’)’ = (x’ + y’) (z’ + w’) (y’ + w)

This is the required POS form.

Categories
K Maps

Some facts of K-map

  • The 1’s in the map represent min terms and 0’s represent max terms
  • If we combine 1’s and make groups, we get simplified function.
  • If we combine 0’s and then make groups, we get the simplified compliment function.
  • To derive the simplified function in POS form from K map, we combine 0s and then get expressions for compliment function and then take compliment. We’ll get the simplified function in POS form.
Categories
K Maps

Redundant groups

A groups of 1s or 0s whose all members are overlapped by other groups is called redundant group. We don’t consider this group while writing the simplified equations from the K-map.

In the above K-map the group which is represented by the oval is a redundant group and hence while writing the equations we ignore it or we don’t make this kind of group and the K-map representation becomes as given next:

The equation we get is

F= yz’w’ + x’z’w (ignoring the redundant group)

If we consider this group then equation would be F=  yz’w’ + x’z’w + x’yz’

And this is a not the simplified expression and hence WRONG.

K-map without the redundant group is:

Categories
K Maps

K Maps: DON’T CARES

When ever there are don’t cares present in the K-map then we have the option of including don’t care in the group to maximize the size of group and hence we get more minimized form but this is not compulsory to include each and every don’t care. So we can use don’t care to our advantage otherwise skip them.

 e.g. Minimize the K-map given below:

If we ignore don’t care then we make groups of 1 then we get the equations as

But if we use the don’t cares then we make groups as

And we see that we have used 2 don’t care and we make a group of 4 rather than 2 while we skip the 3rd don’t care as we do not have to use each don’t care. Hence we see that using 2 out of 3 don’t care we have got more minimized equation.

We represent don’t cares in an equation as shown below:  F= ∑ m (1, 3, 4, 7) + d (0, 5). The terms represented by d are don’t cares and can be either ignored or taken into consideration to reduce the hardware to implement the function.

Categories
K Maps

K Maps – INTRODUCTION

We want the simplest algebraic expression to represent any function so that we need minimum circuitry to implement it. The simplest algebraic expression is the one with minimum number of literals. We need to find a method to get the simplest expression. This method is called Karnaugh map method.

K-map method:

If we have n variables then there would be 2n min terms and hence 2n number of blocks in the K-map and also min terms are arranged in their gray code order (not in binary order). 2-variable map and 3-variable map are shown below:

Also there are min terms mentioned in the squares of the map

Similarly we can have a K-map for 4 variables, 5 variables, 6 variables etc but we generally use only till 4 variables maps as higher maps are difficult to use.

Now to simplify any expression we first convert the expression into its canonical form and then mark a 1 in the corresponding column of min terms present in the expression and then we’ll combine 1’s and make groups of 2 or 4 or 8 or 16 terms and then write the shortened expression.

Any two adjacent squares in the K map differ only by 1 bit change. So the thing where the term corresponding to one square differs from the term corresponding to the adjacent square is that one literal is in compliment form and same literal in other is non-compliment. So sum of those min terms would lead to elimination of one literal and simplified result would be a single AND term.

Also note that squares on one edge of the k-map are adjacent to the opposite edge of the K-map. Hence m0 is adjacent to m2, m4 is adjacent to m6 but m0 is not adjacent to m6. Similarly we can check the adjacent cells in 4-variable map.