Digital Electronics
Karnaugh Map (part II)

Let me introduce another rule, which helps in reducing the number of gates. The rules says; all vertical and horizontal adjacent 1's can be grouped. Remember, bigger the group; lesser the logic. Let me modify the rule-1 which said "all the individual ones in the circuit should be OR-ed to get final boolean expression" to "all the individual and grouped ones in the circuit should be OR-ed to get final boolean expression"


Lets see the karnaugh map below and analyze the situation

two_input_karnaugh_group

Here we can see there are two adjacent squares where output required is 1. Hence, can group them as shown by green rectangle. And now we will try to put logic for this group. Carefully observe the map again, you can easily see that the input B is very much redundant, which means output required is independent of B's input (0 or 1), output of the circuit is only dependent on A's input. i.e when ever A's input is 1 output should be 1, and when A's input is zero, output should be 0. Hence, we found that B's input is not required, and connecting A directly to the output provides us the design.


So the final boolean expression is ..
A

suppose, we had not grouped them, and had 2 independent ones. In this case, to get final expression we would have OR all the independent ones. In that case the expression would be.. 
   -   -  
 A.B + A.B
Now, think yourself. We have two solutions, both implementing same function. But, one is consuming 5 gates (2 NOT, 2 AND, and 1 OR), and another is consuming 0 gates (simply wire connected from A to output). Which solution is smaller and better ?


Lets take one more map, and try to analyze the situation below..

three_input_karnaugh_group

Here you can see that the two 1's were in the adjacent cell, and hence have grouped them. There is also an isolated 1 which cannot be grouped (remember, diagonal 1's cannot be grouped). Lets reduce the logic for grouped ones. Here you can see that the output of the group is independent of input A, it is one only when C is zero AND B is 1. Hence the reduced logic for group will be.. 
  -
B.C
For the isolated 1's, we don't have much choice. There is nothing to group, so no reduction in logic. Hence logic for isolated 1 it will be 
  -
A.B.C
Now, the final expression will be ORing the grouped and isolated 1's... 
  -     -
B.C + A.B.C


Don't always think that only adjacent cells can be grouped. But understand that any combination that can reduces logic can be grouped. In other words, you can group cells containing 1's that reduces redundancy.

For example analyze the karnaugh map below..

three_input_karnaugh_group2

Here the 1's were not in adjacent cells but still we could group them, it is because they are reducing redundancy (observe that output of group is independent of A). Just remember this thumb rule that where ever the redundancy can be reduced we can group the cells containing 1's.
Karnaugh Map
Don't Cares