# Karnaugh Maps (K-Maps)

**Karnaugh Maps (K-Maps)**: In this tutorial, we are going to learn different types of **Karnaugh Maps: 2 variables K-Map, 3 variables K-Map and 4 variables K-Maps**.

Submitted by Saurabh Gupta, on November 27, 2019

In the previous articles, we have already discussed how we can use theorems of Boolean Algebra to simplify Boolean functions so that these simplified expressions help us in getting simple, less expensive and smaller circuits. Although, that method was helpful but also was difficult and non-systematic. We don't have any guarantee that we have reached a minimal expression. Thus, **Karnaugh Maps (K-Maps)** are used to simplify Boolean functions. **K-Map** is a systematic method to simplify Boolean expressions.

## Karnaugh Map (K-Map)

A **K-Map** is a chart or graph composed of an arrangement of adjacent cells. Each of the cells represents one of the **2 ^{2} possible products that can be formed from n-variables**. Two different types of

**K-Map**can be drawn for both CSOP and CPOS in terms of respective minterms and maxterms.

### 1) 2-variable K-Map

A **2-variable** expression can have **2 ^{2} = 4** possible ways of input representation. Thus, a

**2-variable K-Map**will have

**4**adjacent cells representing each of the 4 possible combinations of inputs. Binary numbers at the top of the K-Map represent the condition of variable B along any column and binary number to the left of the K-Map represents the condition of variable

**A**along any row.

**Representation using minterms (SOP form):**

**Representation using maxterms (POS form):**

### 2) 3-variable K-Map

A **3-variable** expression can have **2 ^{3} = 8** possible ways of input representation. Thus, a

**3-variable K-Map**will have

**8**adjacent cells representing each of the 8 possible combinations of inputs.

The thing to be noticed in the representation is that the binary numbers along the top of the **K-Map** are not in normal binary order. They are, in fact, in the Gray Code. This is to ensure that two physically adjacent squares are adjacent i.e., their minterms and maxterms differ by only one variable.

**Representation using minterms (SOP form):**

**Representation using maxterms (POS form):**

### 3) 4-variable K-Map

A **4-variable** expression can have **2 ^{4} = 16** possible ways of input representation. Thus, a

**4-variable K-Map**will have

**16**adjacent cells representing each of the 16 possible combinations of inputs.

The binary number designations of the rows and columns are in **Gray Code**. Binary numbers at the top of the **K-Map** represents the condition of variables **C** and **D** along any column and binary numbers to the left of the K-Map represents the condition of variables **A** and **B** along any row.

**Representation using minterms (SOP form):**

**Representation using maxterms (POS form):**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions