Karnaugh Map

Boolean Algebra

In this tutorial we will learning about Karnaugh Map.

We know that truth table is used to represent values of a
boolean function. Similarly, Karnaugh map is another way of representing the values of a
boolean function. So, K-map is a table consisting of cells which represents a Minterm or Maxterm. Karnaugh map or K-map is named after Maurice Karnaugh.

Karnaugh Map for Sum of Products

For SOP or Sum of Products, each cells in a K-map represents a Minterm. If there are n variables for a given boolean function then, the K-map will have 2n cells. And we fill the cells with 1s whose Minterms output is 1. Lets check the K-map for 2, 3 and 4 variables.

2 variables K-map for Sum of Products

Say we have two variables X and Y then, there will be 22 = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 2 then it represent minterm m2.

3 variables K-map for Sum of Products

Say we have three variables X, Y and Z then there will be 23 = 8 cells in the K-map.

Each cell has a subscripted number at the bottom right corner it is the value of the minterm. So, if a cell has number 7 then it represent minterm m7.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have X’Y’Z’, X’Y’Z, X’YZ and X’YZ’ so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise
X’Y’Z’ —> X’Y’Z [Z’ changed to Z]
X’Y’Z —> X’YZ [Y’ changed to Y]
X’YZ —> X’YZ’ [Z changed to Z’]

4 variables K-map for Sum of Products

Say we have four variables W, X, Y and Z then there will be 24 = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 12 then, it represent minterm m12.

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

How to fill values in the K-map for Sum of Products?

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So, we can draw the following truth table with all possible input and output values.

To express F using Minterm shorthand notation we have to consider only those minterms for which F = 1.

F = m1 + m2

This can also be written as
F = ∑(1, 2)

Now, we have F = m1 + m2 = ∑(1, 2)
Draw an empty K-map having 4 cells (since there are 2 variables so 22 = 4 cells).

F = m1 + m2
So, fill the cells marked with subscript 1 and 2 with value 1. And fill rest of the cells of the K-map with value 0.

In a similarly way we can fill 3 and 4 variables K-map.

Karnaugh Map for Product of Sums

For POS each cells in a K-map represents a Maxterm. If there are n variables for a given boolean function then the K-map will have 2n cells. And we fill the cells with 0s whose Maxterm output is 0. Lets check the K-map for 2, 3 and 4 variables.

2 variables K-map for Product of Sums

Say we have two variables X and Y then there will be 22 = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 2 then, it represent maxterm M2.

3 variables K-map for Product of Sums

Say we have three variables X, Y and Z then there will be 23 = 8 cells in the K-map. So, if a cell has number 0 then it represent maxterm M0.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have X+Y+Z, X+Y+Z’, X+Y’+Z’ and X+Y’+Z so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise
X+Y+Z —> X+Y+Z’ [Z changed to Z’]
X+Y+Z’ —> X+Y’+Z’ [Y changed to Y’]
X+Y’+Z’ —> X+Y’+Z [Z’ changed to Z]

4 variables K-map for Product of Sums

Say we have four variables W, X, Y and Z then there will be 24 = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 15 then it represent maxterm M15.

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

How to fill values in the K-map for Product of Sums?

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So we can draw the following truth table with all possible input and output values.

To express F using Maxterm shorthand notation we have to consider only those maxterms for which F = 0.

F = M0 . M3

This can also be written as
F = ∏(0, 3)

Now that we have F = M0 . M3 = ∏(0, 3).

Draw an empty K-map having 4 cells (since there are 2 variables so 22 = 4 cells)

F = M0 . M3
So, fill the cells marked with subscript 0 and 3 with value 0. And fill rest of the cells of the K-map with value 1.

In a similarly way we can fill 3 and 4 variables K-map.