Map and Map Simplification

Structure of K-Maps

Two-Variable K-Map

• Let us consider that there are two variables. For a boolean expression with two variables, a K Map is created.
• K Map = 2² = 4 cells are the number of cells in two variables.
• As a result, we construct a 2 x 2 K-Map for a boolean function with two variables.

Two variable Karnaugh Map may be represented as:

The two variables of the above boolean function are A and B.

Three Variable K-Map

• For a three-variable boolean expression, a three-variable K Map is drawn.
• K Map = 2³ = 8 cells are the number of cells present in three variables.
• As a result, we build a 2 x 4 K-Map for a boolean function with three variables.

Three variable Karnaugh Map may be represented as:

 

The three variables of the above boolean function are A, B and C.

Four Variable K-Map

• For a four-variable boolean expression, a four-variable K Map is drawn.
• K Map = 2⁴ = 16 cells are the number of cells present in four variables.
• As a result, we build a 4 x 4 K Map for a boolean function with four variables.

The four-variable K Map can be written as:

The four variables of the following boolean function are A, B, C, and D.

Also Read - Shift Registers in Digital Electronics

K-Map Simplification 

To minimize the given boolean function,

• We create a K Map based on the number of variables in the supplied boolean function to reduce it.
• The K Map is filled with 0s and 1s based on its function.
• The function is then minimized according to the following rules.

Rule 1

We can only group 0s with 0s or 1s with 1s; however, we cannot group 0s and 1s together. The ‘X’ symbol for don't care can be grouped with 0s and 1s.

NOTE: There is no need to separately group X's, i.e. they can be ignored if all 0's and 1's are already grouped. 

Rule 2

Groups may overlap each other.

Rule 3

We can only make a group with a number of cells that is a multiple of two.

In other words, a group can only have 2ⁿ cells, i.e. 1, 2, 4, 8, 16, and so on.

Rule 4

Only horizontal or vertical groups are allowed. We are unable to form diagonal or any other shape groupings.

 

 

Rule 5

Each group should consist of as many ones as possible.

Rule 6

The use of opposite and corner grouping is permitted. In Rule 5, an example of opposite grouping is shown.

The following is an example of corner grouping.

Rule 7

As few groupings as feasible should be formed.

Examples of Karnaugh Map

Example 1 (SOP)

Let us minimize the following boolean function:

F(A,B,C,D) = Σ m(1,0,2,5,7,8,9,10,13,15)

Solution

We draw a 4 x 4 K-Map because the given boolean expression includes four variables: ‘A’, ‘B’, ‘C’ and ‘D’. The specified boolean function is used to fill the cells of the K-Map.

Then, following the above-mentioned rules, we build the groupings.

The Karnaugh map is built like the following:

Now, From each group, we only consider the variables which are common in each cell of the group of the K-Map.

From the green group, we get the terms: B’ D’

Taking and of them: B’D’ 

From the blue group, we get the terms: C’ D

Taking and of them: C’D

From the brown group, we get the terms: B D

Taking and of them: BD

On doing the summation, we get,

F(A, B, C, D)

= B’D’ + C’D + BD

As a result, the minimal boolean expression is:

F(A, B, C, D) = B’D’ + C’D + BD

Example 2 (POS)

Let us minimize the following boolean function:

F(A,B,C,D) = π(1,0,2,5,7,8,9,10,13,15)

Solution

We draw a 4 x 4 K-Map because the given boolean expression includes four variables: ‘A’, ‘B’, ‘C’ and ‘D’. The specified boolean function is used to fill the cells of the K-Map.

Then, following the above-mentioned rules, we build the groupings.

The Karnaugh map is built like the following:

Now, From each group, we only consider the variables which are common in each cell of the group of the K-Map.

From the green group, we get the terms: B’ D’

Taking complement and summing them: (B+D) 

From the blue group, we get the terms: C’ D

Taking the complement and summing them: (C+D’)

From the brown group, we get the terms: B D

Taking the complement and summing them: (B’+D’)

On doing the product, we get,

F(A, B, C, D)

= (B+D)(C+D’)(B’+D’)

As a result, the minimal boolean expression is:

F(A, B, C, D) = (B+D)(C+D’)(B’+D’)

Must Read Shift Registers in Digital Electronics

FAQs

1. What is a K-Map?
   The Karnaugh Map, commonly known as the K Map, is a graphical representation that allows you to reduce boolean expressions in a methodical way.
    
2. What are the ways to minimize a boolean expression?
   There are two approaches for minimizing or decreasing boolean expressions: 
   Using Boolean Algebra laws and using Boolean Algebra laws.
   Using Karnaugh Maps (also known as K-Maps)
    
3. What is POS?
   A set of max terms or sum terms is used to describe a Boolean statement in POS(Product of Sums).
   Eg: (AB+CD)
    
4. What is SOP?
   A set of minterms or product terms is used to describe a Boolean statement in SOP(Sum of Products).
   Eg: (A+B).(C+D)
    
5. What are the advantages of K-Map?
   The benefits of the K-map are listed below.
   Knowledge of Boolean algebraic theorems is not required for K-map simplification.
   When compared to the algebraic minimization technique, it usually needs fewer steps.

Key Takeaways

In this article, we learned about the concept of K-Maps. We also learned about the structure of K-Maps for the different numbers of variables. We also learned about the rules to simplify a boolean expression using K-Maps. At the end of the article, we learned how to solve problems using K-Maps.

Learn more, Instruction Format in Computer Architecture

You can also learn more about boolean algebra here.

To learn more about the subject of Digital Electronics, refer to the evolution of computers and the classification of computers.

Happy Learning!