Hey friends, welcome to the YouTube channel ALL ABOUT ELECTRONICS. So, in this video, we will learn about the Karnaugh Map, which is also known as K-map. So the Karnaugh Map is a technique to simplify the Boolean expression. And by simplifying this Boolean expression we can reduce the number of logic gates, which is required to implement that function. For example, let's say we have this Boolean expression, and we have to implement this using logic gates. Now this expression is intercanonical SOP form. So to implement this expression we require 3 AND gates, and 1 OR gate. And here we are assuming that the inputs in the true form and complementary form are readily available. But if we just minimize this expression, then we can reduce the number of logic gates which is require to implement this function. so in this way, by simplifying the Boolean expression, we can reduce the number of logic gates, and by doing so, we can reduce the total cost and the required space for that implementation. So of course, as we have seen so far, using the Boolean laws we can easily minimize the Boolean expression. But to minimize the expression algebraically, we need the familiarity with the Boolean laws. And the as the number of variables increases, then it becomes difficult to minimize the expression algebraically. And after the minimization, we are not sure weather the reduced expression is actually minimal or not. So in such case this Karnaugh map is relatively simple method for simplifying the Boolean expression. So first of all let us see, how to construct the K-map for 2 and 3 variables, then after we will see that, how to map this Boolean expression in this K- map, and after that we will see that, how to minimize this Boolean expression using K-map. So for the 2 variables, there are total 4 different combinations. Or in other words, 2 variables, there are total 4 minterms. So this is how 2 variable K-map will be look like. So here digit beside each row is the possible values of A, while digit above each column is the possible values of B. And the combination of this A and B is represented by each cell of the Karnaugh map. Or in other words, we can say that, the each cell of the map represents the particular minterm. So whenever this A and B are 0, then it represents A bar . B bar. And it is represented by this cell. Similarly while this A is 0 and B is 1, then it represent A bar. B. And the second cell represents the minterm m1. Likewise when A is 1, and B is 0, then it represents minterm m2, and this last cell represent the minterm m3. That means each cell of the map represents the particular minterm. And for the simplicity, we can also denote each cell with the number. Where this number denotes the particular minterm, which is represented by that cell. So this is how, the 2 variable K-map will look like. Similarly now let us see the 3 variable K-map. So for the 3 variables, there are total 8 different combinations. And this is how the 3 variable K-map will look like. So here the numbers on the top of each column represents the possible combinations of B and C , while the numbers besides each row represents possible values of A. And each cell represent the particular combination of A B and C. Or in other words, each cell represents the particular minterm. Now here in K-map, numbering is done in grey code form. That means if we move from 1 column to other column, then only 1 bit changing at the time. And that is why, after 01 we have 11 instead of 10. That means between each pair of adjacent cell, only 1 bit is changing at the time. For example as we move from 1st cell to the 2nd cell, then only 3rd bit is changing. Likewise as we move from 001 to 011, then only this 2nd bit is changing. Similarly as we move from 001 to 101, then only MSB is changing. Moreover as we move from 000 to 010, then also only 1 bit is changing. That means these 2 corner cells are also adjacent. Because if we just read this map, then these 2 cells will be adjacent to each other. Similarly these 2 cells are also adjacent to each other. So in short in the K-map, the cells are arranged such that between each pair of adjacent cells, only 1 bit is changing at the time. alright, so let us see how to map the Boolean expression in this K-map. And in this video we will assume that, the Boolean expression is in the sum of the product form. So first let us take the case of 2 variables. So here, this F1 is the function of 2 variables. So to represent this function in the K-map, what we will do, whatever minterms are present in this function, for those minterms, we will put 1 in the map. For example in this case, the minterms 0 1 and 3 are present. So we will put 1 in those cells. Now in many times, we might given a function in algebraic form. So from that also we can map the function in K-map. For example the same function is also given as A bar . B bar + A bar . B + A . B. So here, for A bar . B bar both A and B are 0. That means this term represent the 1st cell. So here, we will put 1 in the 1st cell. Similarly in case of A bar . B, A is 0 and B is 1. So for this we will put 1 in this cell. Similarly in A . B both variables A and B are 1. That means we will put 1 in last cell. So in this way we can map the Boolean expression in the K-map. So now, let us see how to minimize the Boolean expression, once it is mapped in K-map. So for the minimization make the group of 1s, which are adjacent to each other. But this group should be in the power of 2, that means in case of the 2 variable map, we can make group of two 1s or four 1s which are adjacent to each other. But we can not make of group of 1s, which is not in the power of 2. For example we can not make group of three 1s. And during the grouping, just ensure that all the 1s in the map gets covered. And during the grouping procedure, even if the 2 groups overlap with each other, then also it is alright. So, in this case, we can make the group of these two 1s, and likewise, we can also make the group of these two 1s. And in this way, all the 1s in the map gets covered. So, in this way, by doing this grouping, we can minimize the Boolean expression. And to understand that, first let's consider this first group. So, this group consist of two minterms. That is A bar . B bar and A bar. B. Now in this case, since A bar is common, so we will have B bar + B. And we know that , this B bar + B = 1. That means this A bar . B bar + A bar . B = A bar. So by grouping these two 1s, equivalently we will get A bar. So now let us see, how to get the same result from the K-map. So if you see this group, then this variable A remains same throughout the group. On the other hand this variable B is changing over the group. So we will discard the variable which is changing throughout the group, and we will keep the variable which is not changing. So in this case as you can see, this variable A is not changing. And here the value of this variable = 0. That means this group represents A bar. Similarly, let us see the second group. So this group consist of 2 minterms, A bar . B and A B. So if we simplify this expression using the Boolean laws, then we will get the B. And the same reason we can also get directly from the K-map. So if you see this group, then in this group, the variable A is changing, while B is constant. So in this group, we will keep this variable B and we will ignore this variable A. And here, since the value of variable B = 1, so this group represents B. That means this group represents A bar, while this group represents B. And the overall function is the summation of A bar and B. So in this way, using the K-map, we can simplify the Boolean expression without using any Boolean laws. So let us take one more example. So once again here the function is the 2 variable function. And it consist of 2 minterms. That is m0 and m3. So in the K-map first of all let us mark those cells with 1, which corresponds these 2 minterms. So in this case, we can not make a group of 2. Because these 2 cells are not adjacent to each other. So in this case just consider these two 1s alone. So the first cell, represents A bar . B bar, while the last cell represent A . B. That means in this case, further we can not minimize the function. And the output = A bar . B bar + A B. Similarly in this case also, these two 1s are not adjacent to each other. And therefore we can not group them together. And therefore we need to consider these 2 terms individually. So in this case, this 1 represents A bar. B, while this 1 represents A . B bar. And output is the summation of these 2 terms. On the other hand, all the sums are 1 in the map, and the output = 1. Because irrespective of the change in the value of A and B, the output remains 1. So that is how, we can minimize any 2 variable Boolean function using the K-map. Similarly now let us see, how to minimize the 3 variable Boolean expression using the K-map. So let us say, this F1 is function of 3 variables. So first of all let us map this function in the K-map. So here we will place 1s in those cells, which represents minterms m0 m1and m5. And now let us try to minimize this function. So as I have discussed earlier, to minimize this function, we need to make the group of 1s, which are adjacent to each other. And the group should be in the power of 2. So in this case, this is the 1st group, and by combining these two 1s, we will get the second group. And in these 2 groups, all the 1s in the map gets covered. So first of all, let us consider these groups. So in this group if you see, the variable C is changing, while the variable A and B are fixed. Therefore for this particular group, we will consider this variable A and B, and we will ignore the variable C. Moreover, since the variable A and B are 0, that means, these groups represents A bar .B bar. Similarly, let us see the second group. So in this group if you see, then the variable A is changing, while the variable B and C are same. So here B is 0, while C is 1. Therefore this group represents B bar. C. And if you see the overall function, then overall function represents A bar . B bar + B bar . C. So in this way, while making the groups in the Karnaugh's map, we can minimize the Boolean function. So let us take another example. So let us say this F1 is the function of 3 variables. And it consists of following minterms. So 1st of all let us represent this function in the -map. That means we will place 1s in those cells, which represents these minterms. And now let us try to minimize it. So here in the top raw, we can make the group of these two 1s, and similarly in the bottom raw, we can make the group of these two 1s. So 1st, let us consider this 1st group. So in this group, the variables A and B are not changing, while variable C is changing. And here value of variable A and B are 0. That means this group represents A bar . B bar. Similarly in the second group, the variable A and C is not changing, while the variable B is changing. So in this group, the value A and C = 1. Therefore, this group represents, A . C. So if you see, the overall minimized function , then that is = A bar . B bar + AC. Now some of you might have question that, can we combine these 2 groups and can we make a group of 4. Well the answer is no, because we can do so, when both the groups are adjacent to each other. Now when we move from 1 group to the other group, and only 1 variable is changing, then we can say that, those 2 groups are adjacent to each other. And in that case, we can combine those 2 groups, and make the bigger group. So in this case if you see, when we go from 1 group to the other group, and more then 1 variable is changing. Because in this case, this variable A is changing and at the same time this variable B is also changing. That means these 2 groups are not adjacent to each other. Therefore we can not combine these 2 groups. So in short we can make the group of 1s, which is in the power of 2, and the shape of that group should be the square or rectangular. Now some of you might ask, while grouping can we cover these two 1s 1st, then these two 1s, and then these two 1s, well you can do so, just by making these two groups only we are able to cover all the 1s in the map. So there is no need to make this 3rd group. That means during the minimization, try to cover all the 1s in the map, by making the minimum number of groups. So let us take few more examples, so it will get clear to you. So in this case, the Boolean function contains 4 minterms. So 1st of all let us represent all the 4 terms in the K-map. So for that you will place 1s in each cell which represents these minterms. That is 0 1 3 and 5. And now let us try to minimize it. So here this is the 1st group of 1s, similarly we can also make the group of these two 1s. And now only this 1 remains. So by making the group of these two 1s, we can also cover that 1. So in this way, we have covered all the 1s in that map. So 1st now let us consider this group. So as you have seen earlier in this group the variable A and B is not changing, while the variable C is changing. And here the value of A and B = 0. Therefore this group represents A bar . B bar. Similarly in this second group the variable A is changing, while the variable B and C remains same. And here the value of B = 0, while the value of C = 1. Therefore this group represents B bar . C. Similarly in the third group the variable A and C is not changing, while variable B is changing. So here the value of A = 0 , while the value of C = 1. Therefore, this group represents A bar . C. So now the overall function is the summation of all these groups. That is A bar . B bar + B bar . c + A bar . C. So in this way using the K- map we can minimize the Boolean function. So let us take few more examples and let us understand the other possible groupings in this 3 variable K-map. So let us consider this function. So first of all, let us map this function in the K-map. So earlier we have seen that the cells at the edge of the map, are also adjacent to each other. So if the function contains those minterms, then we can also group them like this. So in this case as you have see, the variable A and C is not changing. And here the value of both variable A and C = 0. Therefore this group represent A bar . C bar. Similarly in this case, we can combine this two 1s, and this group represents A . C bar. Because in this group the value of variable A = 1, while the value of variable C = 0 . Now so far in our discussion of f3 variable K -map we have seen that how to make the group of 2. But now let us see 2 more examples where we can make the group of 4. And let us see how to minimize those functions. So let us consider this function. So first let us map this function in the K-map. So as you can see, it contains minterms 1 3 5 and 7. So in this case instead of making group of two 1s, we can make group of four 1s. So in this group if you see, then both variables A and B are changing. But this variable C remains same. Therefore this group represents C. And the minimize expression of this function is also = C. So in this way by making the group of 4, we can further minimize the Boolean expression. So let us take couple of more examples. So in this case, first let us map this function in the K-map. So this function contains four minterms, 0 2 4 and 6. So here instead of making the group of 2, we can make the group of 4. Because these two groups are also adjacent to each other. Now if you see the entire group, then only variable C is not changing. And the value of variable C = 0, therefore this group represents C bar. And the minimize expression of this group is also = C bar. So let us take few more examples. So first let us map this function in the K-map. So after mapping if you see, then these four 1s are in the same raw. So we can make the group of 4. Now in this case, the variable B and C both are changing, while variable A remains same. And here the value of variable A = 0. Therefore this group represents A bar. That means after the simplification, this function is equivalent to A bar. Similarly in this case, if you map this function in the K- map, then we have four 1s in the bottom group. So here we can make the group of 4. And in this case, only 1 variable A is not changing. And since the value of variable A = 1, so this group represents the A. So let us take couple of more examples. So in this case, the function contains 6 minterms. So first let us map this function on the K-map. Now here, we can't take the group of 6, because as you have seen earlier, we can make a group which is in the power of 2. That means here we can make the group of two , four or eight. So here, to minimize this expression, we can make a group of these four 1s, and likewise, we can also make the group of these four 1s. So of course, here the two groups are overlapping, but that is alright. So if we just consider the first group, then only 1 variable B is not changing. And the value of variable B = 0. Therefore this group represents B bar. Similarly if we see this second group, then only 1 variable C is not changing. And the value of variable C = 1. Therefore this group represents C. And if we see overall minimized function, then that = B bar+ C. So now let us move to our last example. So this function also contains 6 minterms. So first of all let us map them on the K-map. So after mapping if you see, then we can cover all these 6 minterms using 2 groups. So the 1 group is the group of these four 1s, while the second group is the the group of these four 1s. So if we consider this first group, then it corresponds to B bar. Because in this case only variable B is not changing. And the value of B = 0. Therefore this group represents B bar. Now if you see the second group, then in this group only variable C is not changing. And the value of variable C = 0. Therefore this group represents C bar. That means if you see the overall minimized function, then that = B bar + C bar. So in this way, through the different examples we have seen that, using the K-map how you can easily minimize the Boolean function of 2 and 3 variables. Similarly in the next video, we will see the 4 variable K-map , and through the different examples we will see that, how to minimize the Boolean function of 4 variables using the K- map. So if you have any question or suggestions, then do let me know here in the comment section below. If you like this video , hit the like button, and subscribe to the channel for more such videos. Thank you.