K map in digital electronics

K-map is graphical method to obtain minimal expression from any Boolean algebra and it is most effective method to create or reduce the complexity of any logical circuit in digital electronics. It is also known as Karnaugh map. By this method we can easily simplify and minimize Boolean expression of 3 or 4 variables without any Boolean algebra laws and theorems. As we know Boolean expressions are of two types, so, K-maps are also of two types Sum of Product (SOP) and Product of Sum (POS). K-map is advanced form of truth table it is very used in creating or analyzing the digital circuits in electronics. Number of cells in K-map will be 2ⁿ, where n is number of variables.

SOP Form

1.     K-map of 3 variable

In three variables K-map number of cells will be 8. Counting and denotations of cells are shown in the figure below.

The reason behind this discontinuous numbering of cells is that difference between 2 variables (BC here) only should one bit, both bit should not change at once.

For the SOP form put 1 in the cell blocks according to their positions. Say we have this truth table.

Or we can write same thing as, Z(A,B,C)= Σ(0,3,4,7)

 Now, we need to pair 1 with maximum but even number of 1’s. In three variables K-map a pair of 8 1’s is possible when all outputs are high. First we have to check pair of 8 one’s, if there is no such pair available then we have to check pair of four 1’s and then pair of two 1’s. Side by side pairing is also possible.

Here, only two pairs of two 1’s are possible. Now, if pairing is done, we need to check the common variable of all pairs. In the case of red pair, common variable is B’C’ and in the case of blue pair, BC is common variable.

So, Boolean expression is Z = B’C’ + BC.

You can see that variable A is not available in the the Boolean expression that means output is independent from input A. Let’s see the logic circuit of this expression.

Logic circuit

Here we have first ANDed the inverted B and C then we have ANDed B and C directly. Output of both AND gate is the inputs of OR gate which is implementing plus sign in the expression. As said before that output is independent of A so it is not connected to anything.

2.     K-map of four variables

In the four variables K-map numbers of cell blocks are 16.

F(A,B,C,D) =Σ(0,2,3,5,6,7,8,9,10,12,14,15)

K-map for this table –

There are six pairs in this K-map. Yellow, blue, lime (light green) and light blue are pairs of four 1’s. The lime and light blue pairs are side by side pairs.

So, Boolean expression is F= AB’C’ + A’BD + AD’ + A’C + BC + B’D’

Logic circuit

POS Form

1.     K-map with 3 variables

As we know that in POS form 1 is treat as complement, so, in K-map denotations are interchanged.

For the SOP form put 0 in the cell blocks according to their positions.

Or, Z(A,B,C)= π(1,2,5,6)

For the red group BC’ is common, so we will write it as B+C’ and for the blue pair B’C is common, so we will write it as B’+C. Our final expression will be the multiplication of both terms.

So, the final expression, Z=(B+C’).(B’+C)

You can here also variable A is not available in the the Boolean expression that means output is independent from input A. Let’s see the logic circuit of this expression.

Logic circuit

Here we have first ORed the inverted C and B then we have ORed inverted B and C. Output of both OR gate is the inputs of AND gate which is implementing product sign(.) in the expression. As said before that output is independent of A so it is not connected to anything.

2.     K-MAP with four variable

F(A,B,C,D) =π(1,3,4,7,9,10,11,13)

K-map for this table –

In this K-map numbers of possible pairs are five. For green pair D’ and B is common variable, for orange pair AC’D’ is common term, for red pair A’CD’ is common term, for blue pair A’BC’ is common term. There is no pairing of purple 0, so we will write all variable which are AB’CD.

So, final expression, F= (A+B’+C+D).(A+C’+D’).(A’+C+D’).( A’+B+C’).(B+D’)

Logic circuit

Conclusion

• We have learnt in this article about the K map.
• There are how many types of the Boolean expression.
• How to obtain Boolean expression of logic according to truth table using K map
• How to create logic circuit using Boolean expression.