Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Karnaugh Map
2.1.
Two-variable K-Map
2.2.
Three-variable K-Map
3.
3.1.
Four-variable K-Map
4.
Simplification of Logical Functions Using K-Map
5.
Frequently Asked Questions
6.
Conclusion
Last Updated: Mar 27, 2024

Karnaugh Maps

Author Urwashi Priya
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this blog, we will discuss about Karnaugh Maps. It was developed in 1953 with a vision to simplify complex boolean algebraic expression. it is just a modified and updated version of the truth table. It saves us from learning complex laws and algebraic theorems.

Karnaugh Map

Karnaugh map is a graphical method that provides a systematic method for simplifying and manipulating the Boolean functions. In this technique, the information contained in a truth table or available in the SOP(sum of product) or POS(product of sum) form is represented in the karnaugh maps(also known as k-map). Although this technique may be used for any number of variables, it is generally used for up to 6 variables, beyond which it becomes very cumbersome. In n-variable k-map, there are 2ⁿ cells. 

Two-variable K-Map

  • Four cells.
  • Four minterms(maxterms)

Three-variable K-Map

  • Eight cells
  • Eight minterms(max terms)
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Four-variable K-Map

  • Sixteen cells
  • Sixteen minterms(maxterm)

Simplification of Logical Functions Using K-Map

Simplification of logical functions with K-map is based on the principle of combining terms in adjacent cells. The expression for output ‘Y’ can be simplified by properly combining those cells in the K-map, which contains 1’s for SOP term or 0’s for POS form. The process for combining these 1’s and 0’s is called grouping. Groups are made up of 2, 8, 16 and so on. By folding K-map over its edges, the number of 1’s and 0’s overlapping forms the group. 

A pair of adjacent 1’s in a K-map eliminates the variable that appears in the complemented and uncomplemented form. 

Similarly, we can make group of quads and octets.

Algorithm:

  • Draw the k-map and place 1’s in those cells corresponding to the 1’s in the truth table. Place 0’s in the other cells.
  • Examine the map for adjacent 1’s and group those 1’s which are not adjacent to any other 1’s. These are called isolated 1’s. 
  • Next, look for those two adjacent 1’s. Any pair containing such a 1. 
  • Any octet even it contains some 1’s that have already been grouped. 
  • Any quad containing one or more 1’s which have not already been grouped. 
  • group any pairs necessary to include any 1’s that have not yet been grouped making sure to use the minimum number of groups. 
  • Find the OR sum of all the terms generated by each group.
     

Example: Simplify a four variable logic function using K map.

f(A, B, C,D)=Σm(0,1,2,4,5,6,8,9,12,13,14).

Solution:

Given, f(A, B, C,D)=Σm(0,1,2,4,5,6,8,9,12,13,14).

Step 1: draw a 16 cell map and put 1’s in such cell as given in f(A,B,C,D).

Step 2: one group of 8, 2 group of 4’s are formed.

Step 3: finally we write minimised SOP.

      F=C’+A’D’+BD’

 

Frequently Asked Questions

  1. How many maximum possible minterm and maxterm can be made with n number of variables?
    With n number of variables the maximum possible minterm or maxterm is equal to 2ⁿ.
     
  2. What is meant by equality of K-maps?
    The two K-maps are said to be equal if 1’s are placed in the same position on both the maps. Thus, the logical expression is also the same
     
  3. What is meant by complementation of K-maps?
    The two K maps are said to be complemented if K-map has 1’s and another K map has 0’s on the same location.

Conclusion

This article taught us about Karnaugh Maps. We individually discussed about their structure and the steps to simplify an expression.

We hope you could easily take away all critical and conceptual techniques by walking over the given examples. 

Recommended Reading - Canonical Cover In DBMS.

Now, we strongly recommend you to understand the other related concepts in boolean algebra and enhance your learning. You can get a wide range of topics similar to this on booleanalgebra

It's not the end. Learn and explore more.

Previous article
Logic Gates & Circuits
Next article
Introduction to Trees
Live masterclass