Author: M Abo Bakar Aslam

Karnaugh Map - 4 Variables

A Karnaugh Map (K-Map) is a visual method used to simplify Boolean expressions in combinational logic circuits. It reduces complex logic functions into minimal forms, helping designers create efficient digital circuits.

Structure of 3-Variable Karnaugh Map

A 4-variable K-Map consists of 16 cells, representing all possible combinations of inputs x, y, z and w. Each cell corresponds to a minterm of the Boolean function. The map is arranged in Gray code order so that only one variable changes between adjacent cells, enabling easy grouping and simplification of logic terms.

  1. Number of Input Variables = n = 4
  2. Total Number of Cells in K-map = 2^n = 2^4 = 16
Cell Arrangement for K-Map having 3 Variables Boolean Expression
Figure 1: Cell Arrangement for K-Map having 3 Variables Boolean Expression

Rules for Construction of K-Map and Grouping

  1. Allowed number of 1's in a group are 1, 2, 4, 8, 16. These number of power of 2 i.e., 2^0(1), 2^1(2), 2^2(4), 2^3(8), 2^4(16) 2. Increase number of 1's in a group
  2. Decrease number of groups
  3. Only adjacent-cells can be in a group. Diagonal cells are not allowed to be in a group.

1. Example - 1

Reduce F = x’y’z’w’ + x’y’z’w + x’y’zw + x’y’zw’ + xy’z’w + xy’zw to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 2: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 3: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: x=0, y=0 → x’, y’
For G2: y=0, w=1 → y’, w

Step 4:

Create minterm for each group
For G1: x’y’
For G2: y’w

Step 5:

Create final function by adding for all minterms
F = x’y’ + y’w

2. Example - 2

Reduce F = x’yz’w’ + xyz’w’ + x’y’zw’ + x’yzw’ + xyzw’ + xy’zw’ to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 3: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 4: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: z=1, w=0 → z, w’
For G2: y=1, w=0 → y, w’

Step 4:

Create minterm for each group
For G1: zw’
For G2: yw’

Step 5:

Create final function by adding for all minterms
F = zw’ + yw’

3. Example - 3

Reduce F = x’yz’w’ + xyz’w’ + x’y’zw’ + x’yzw’ + xyzw’ + xy’zw’ + x’y’z’w’ to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 5: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 6: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: z=1, w=0 → z, w’
For G2: y=1, w=0 → y, w’
For G3: x=0, w=0 → x’, w’

Step 4:

Create minterm for each group
For G1: zw’
For G2: yw’
For G3: x’w’

Step 5:

Create final function by adding for all minterms
F = zw’ + yw’ + x’w’

4. Example - 4

Reduce F = x’y’z’w’ + x’y’zw’ + xy’z’w’ + xy’zw’ to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 7: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 8: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: y=0, w=0 → y’, w’

Step 4:

Create minterm for each group
For G1: y’w’

Step 5:

Create final function by adding for all minterms
F = y’w’

5. Example - 5

Reduce F = x’y’z’w’ + x’y’zw’ + xy’z’w’ + xy’zw’ + x’y’z’w + x’y’zw + xy’z’w + xy’zw to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 9: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 10: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: y=0 → y’

Step 4:

Create minterm for each group
For G1: y’

Step 5:

Create final function by adding for all minterms
F = y’

6. Example - 6

Reduce F = x’y’z’w’ + x’y’zw’ + xy’z’w’ + xy’zw’ + x’y’z’w + x’y’zw + xy’z’w + xy’zw + x’yz’w’ + xyz’w’ + x’yzw’ + xyzw’ to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 11: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 12: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: y=0 → y’
For G2: w=0 → w’

Step 4:

Create minterm for each group
For G1: y’
For G2: w’

Step 5:

Create final function by adding for all minterms
F = y’ + w’

7. Example - 7

Reduce F = x’y’z’w + x’y’zw + x’yz’w + x’yzw + xyz’w + xyzw + xy’z’w + xy’zw to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 13: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 14: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: w=1 → w

Step 4:

Create minterm for each group
For G1: w

Step 5:

Create final function by adding for all minterms
F = w

8. Example - 8

Reduce F = x’y’z’w + x’y’zw + x’yz’w + x’yzw + xyz’w + xyzw + xy’z’w + xy’zw + x’y’zw’ + x’yzw’ + xyzw’ + xy’zw’ to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 15: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 16: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: z=1 → z
For G2: w=1 → w

Step 4:

Create minterm for each group
For G1: z
For G2: w

Step 5:

Create final function by adding for all minterms
F = z + w

9. Example - 9

Reduce F = x’y’z’w + x’y’zw + x’yz’w + x’yzw + xyz’w + xyzw + xy’z’w + x’y’zw’ + x’yzw’ + xyzw’ + xy’z’w’ + x’y’z’w’ + x’yz’w’ + xyz’w’ + xy’zw’ + xy’zw to minimum number of literals

Step 1:

Placing 1 for respective box according to above structure.

Step 1 - Placing 1s according to map
Figure 17: Step 1 - Placing 1s according to map

Step 2:

Make groups of join-boxes containing values

Step 2 - Making Groups
Figure 18: Step 2 - Making Groups

Step 3:

For each group, select variable whose is not changed. And then create respective literal
For G1: no such variable

Step 4:

Create minterm for each group
For G1: 1

Step 5:

Create final function by adding for all minterms
F = 1