Karnaugh's Map(K-MAP) | Computer Architecture

Karnaugh's Map

It is used to reduce boolean algebraic equations.It is actually a truth table of another form. Let we understand more details of K-Map by the help of examples of different variables.

Two Variable K-Map

If any algebraic equation have two variable (suppose A and B) than we can say that it is two variable expression. Such as

F = A̅ B̅ + A̅ B

Here A and B are two variables

Now we will see how we plot two variable K-Map

Let we understand how we fill 1 in above figure.We know the above figure have rows and columns.We will write 1 at the intersecting cell of row and column according to expression like here first term of expression is A̅ B̅ so find where is intersecting cell of row A̅ and column B̅ when we find just write 1. In the same way we will do for other term of expression.After finishing all terms then write 0 or blank in the remaining cells.Here we will work with 1's

Our main aim is to reducing the expression. Let we see how reduce expression we can reduce by making pairs such as show in figure

We make pair with 1's not 0's.Here only one pair is possible.After paring new expression will we A̅ B̅ B here B̅ B is discarded so we get A̅.
Now the new expression will be F= A̅.

We can say that expression F = A̅ B̅ + A̅ B is reduced to F= A̅.

Three Variable K-Map

If any algebraic equation have Three variable (suppose A , B and C) than we can say that it is three variable expression. Such as

F = A̅ B̅ C̅ + A B̅ C̅ + A̅ B̅ C + A B̅ C

Here A , B and C are three variables

Now we will see how we plot three variable K-Map

Let we understand how we fill 1 in above figure.We know the above figure have rows and columns.We will write 1 at the intersecting cell of row and column according to expression like here first term of expression is A̅ B̅ C̅ so find where is intersecting cell of row A̅ and column B̅ C̅ when we find just write 1. In the same way we will do for other term of expression.After finishing all terms then write 0 or blank in the remaining cells.Here we will work with 1's

Our main aim is to reducing the expression. Let we see how reduce expression we can reduce by making pairs such as show in figure

We make pair with 1's not 0's.If any pair having four one's than it is known as square or quard. We always try to make biggest pair in map. Here only one pair(square) is possible. For a pair(square) the row and column involved are A̅ , A , B̅ C̅ , B̅ C respectively.For simplification we can write A̅ A B̅ C̅ B̅ C here A̅A-discarded ,C̅C-discarded and B̅ B̅ = B̅. So finally we get B̅.

Now the new expression will be F= B̅.

We can say that expression F = A̅ B̅ C̅ + A B̅ C̅ + A̅ B̅ C + A B̅ C is reduced to F= B̅.

Four Variable K-Map

If any algebraic equation have Four variable (suppose A , B , C and D) than we can say that it is four variable expression. Such as

F = A̅ B̅ C̅ + B̅ C D̅ + A̅ B C D̅ + A B̅ C̅

Here A , B , C and D are four variables

Now we will see how we plot four variable K-Map

Same concept is using as given above. we get

In above diagram we have 3 pairs and 1-Square/Quard (which is made by four corners)

Now the simplified equation will be F = B̅ D̅ + B̅ C̅ + A̅ C D̅

Note: In any K-Map index is given in every cell like 0,1,2,3... with specified sequence. The question is why these sequence is given? where it is used? the answer is some time the question is given in the form of indexes not in the form or expressions so at that time if we know index place then we can directly place 1 or 0 in that cell. Let we understand by the help of example:

Example:

1. Simplify the Boolean function F(A,B,C)= ∑(0,2,4,5,6)

Solution:

K-Map

After Paring we get

Reduced Expression will be F = C̅ + AB̅

2. Simplify the Boolean function F(A,B,C,D)= ∑(0,2,3,4,5,8,10,11,12,13,14,15)

Solution:

K-Map

Reduced Expression will be F = C̅D̅ + AB + BC̅ + A̅B̅C + AC

3. Simplify the Boolean function F(A,B,C,D)= ∑(0,2,4,6,8,10,12,14)

Solution:

K-Map

Reduced Expression will be F = C̅D̅ + CD̅ = D̅

4. Simplify the Boolean function F(A,B,C,D)= ∑(0,13,8,9,11)

Solution:

K-Map

Reduced Expression will be F = B̅C̅ + B̅D̅

5. Simplify the Boolean function F(A,B,C,D)= ∑(0,2,4,6,12,14)

Solution:

K-Map

Reduced Expression will be F = C̅B̅ + DB̅

6. Simplify the Boolean function F(A,B,C,D)= ∑(0,1,2,3,4,5,6,7,8,9,11,12,13,15)

Solution:

K-Map

Reduced Expression will be F = A̅ + C̅ + D

Try your self

7. Simplify the Boolean function F(A,B,C,D)= ∑(1,5,6,7,9,13,14,15)

8. Simplify the Boolean function F(A,B,C,D)= ∑(0,2,4,5,6,7,8,10,13,15)