Test: K-Map - 2 - Electrical Engineering (EE) MCQ

K- map:

• It is a graphical representation and can be used to minimize the logical expression with '0', '1', and don't care.
• In K - map, a group of 8 cells is called an octet, it will eliminates 3 variables in given expression. (2³ = 8)
• A group of 4 cells is called a quad, it will eliminate 2 variables. (2² = 4)
• Similarly, a group of 2^m cells will eliminate 'm' variables. Therefore, the final expression will contain 'n-m' literals. where 'n' is the number of variables in a boolean function.

So, there are only two implicants, 

Concept:
Majority voting means when more than 1 inputs one 1 (i.e. when 2 or more inputs are 1).

Calculation:
Truth Table is as shown:

Solving using K-map we get,

Q = AC + BC + AB

Karnaugh Map is used to simplify Boolean algebra expressions.
It is a graphical technique of simplifying Boolean expressions.
It is also known as K-map.
K-map contains two types of methods:
1. SOP (Sum Of Product): This produces logical expressions that contain OR of multiple AND terms.
Example: b̅.d̅ + d̅.c̅ 
2. POS (Product Of Sum): This produces logical expressions that contain AND of multiple OR terms.
Example: (b̅ + d̅)(d̅ + c̅)

X = B + AC

Concept:
Min Terms: 

• A minterm is a boolean expression written for all those terms whose value is 1 in the K-map.
• It is denoted by: F(x, y, z) = ∑(minterms)

​MaxTerms: 

• A maxterm is a boolean expression written for all those terms whose value is 0 in the K-map.
• It is denoted by: F(x, y, z) = π(max terms)
• Max terms are the compliments of minterms.

Given,  F(x, y, z) = ∑(1, 3, 6, 7)
Binary representation is:
F(x, y, z) = ∑(001, 011, 010, 011)

It is minterm representation.

F(x, y, z) = ∑(000, 010, 100, 101)
F(x, y, z) = ∏ (0, 2, 4, 5)
It is max term representation.

Concept:
K-map:

• K-map (Karnaugh Map) is a pictorial method used to minimize Boolean expression without having to use Boolean Algebra theorems and equation manipulation.
• K-map can be thought of as a special version of a truth table.
• Using K-map, expression with two to four variables are easily minimized.
• K-maps are also referred to as 2D truth tables as each K-map is nothing but a different format of representing the values present in a one-dimensional truth table.
• To simplify a logic expression with two inputs, we require a K-map with 4 cells (= 22)
• Similarly, a logic expression with four inputs we require a K-map with 16 cells (= 24)
• Each cell within K-map has a definite place value which is obtained by using on encoding technique known as Gray code.
• For n-variable K-map, with 2n cells, try to group 2n cells first, then for 2n-1 cells, next for 2n-2 cells, and so on until the group contains only 2° cells ie. Isolated bits (if any)
• Also remember, the number of cells in a group must be equal to an integer power to 2 i.e. 1, 2, 4, 8, ….

Calculation:

→ There are no 16 bits group, no 8-bits group, but there are 2-four bits group
→ Eliminate the variables for which the corresponding hit appears within the group as both 0 and 1.

• Group 1 → B̅1 B2
• Group 2 → B1 B̅2

→ Therefore in SOP form (sum of products) output 

Concept:
The K-map is a graphical method that provides a systematic method for simplifying and manipulating the Boolean expressions or to convert a truth table to its corresponding logic circuit in a simple, orderly process.
In an 'n' variable K map, there are 2ⁿ cells.
For 4 variables there will be 2⁴ = 16 cells as shown:

The Karnaugh map uses the following rules for the simplification of expressions by grouping together adjacent cells containing ones.

• Groups must not include any cell containing a zero.
• Groups may be horizontal or vertical, but not diagonal.
• Groups must contain 1, 2, 4, 8, or in general 2ⁿ cells. That is if n = 1, a group will contain two 1's since 2¹ = 2, if n = 2, a group will contain four 1's since 2² = 4 and so on.
• Groups may overlap.
• Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.

Analysis:
In the given K map groups of one can be formed as shown:

∴ The minimized expression is CD

The correct answer is option 4
K-maps
F(A, B, C, D) = ∑ (0, 1, 2, 3, 6, 12, 13, 14, 15)
Two K-Maps can be constructed from the given boolean function


The expression for K-Map 1 is AB + A'B' + A'CD'
The expression for K-Map 2 is AB +A'B' + BCD'

Forming pair's of 4 in the K-map is as shown:

The simplified expression for G₂ will be:
G₂ = B₃B̅₂ + B̅₃ B₂
G₂  =  B₃ ⊕ B₂

Product of sum (POS) expression:
It is equivalent to logical OR-AND function which gives the AND product of two or more OR sums to produce on output.
Example:

The output function will be:
F = (A + B) (C + D) (E + F)
∴ (b+c)(a+b) is the product of sum expression.

Calculation:
F = A B̅ C̅ + A̅ B̅ C + 1. B C̅ + 0.B C
= A B̅ C̅ + A̅ B̅ C + B C̅ + 0
By forming the k-map, we get

F(A, B, C) = ∑ (1, 2, 4, 6)

Karnaugh map (K-map):

• The Karnaugh map (K-map) is a method of simplifying Boolean algebra expressions.
• The Karnaugh map reduces the need for extensive calculations.
• Karnaugh map can be explained as An array that contains 2k number of cells, where k is the number of variables in the Boolean expression that is to be reduced or optimized. 

Number of cells in 2 variable k-map = 2² = 4
Number of cells in 3 variable k-map = 2³ = 8
Number of cells in 4 variable k-map = 2⁴ = 16

2 variable K-maps:
There are 4 cells in the 2-variable k-map as shown,

3 variable K-maps:

• For a 3-variable Boolean function, there is a possibility of 8 output minterms.
• The general representation of all the minterms using 3-variables is shown below.
  

From the given K-map, the simplified Boolean expression is

F = C A̅ B̅ + C̅ A̅ B + CAB + C̅ A B̅ 
= C̅ (A̅ B + A B̅) + C (A̅ B̅ + AB)
= A ⊕ B ⊕ C

Concept:
The K-map is a graphical method that provides a systematic method for simplifying and manipulating the Boolean expressions or to convert a truth table to its corresponding logic circuit in a simple, orderly process.
In an 'n' variable K map, there are 2n cells.

Application:
For 16 cells, we have 4 variables. 
The K map will give an output of 1, when all the cells have a 1, i.e. if all the input combinations give an output of 1, the maximum number of inputs can be simplified to give an output of 1.
This is explained with the following K map:

Since the K map forms a pair of 16, it can be eliminated giving an output:
Y = 1
Since the output contains no input variables (A, B, C, or D), all the four variables are simplified/eliminated.

The given minterms when represented with K-map for simplification results in:

The simplified Boolean expression is therefore;
⇒ f(w, x, y, z) =y’ +w’z’ + xz’
Option (2) is correct.

f(A, B, C, D) = ∑ m(0, 1, 2, 6, 8, 9, 10, 11) + ∑ d(3, 7, 14, 15)

⇒ f = B̅ + C