17.10 Karnaugh Maps – Pulse and Digital Circuits

17.10 KARNAUGH MAPS

We have seen that Boolean expressions can be simplified to arrive at the simplified gate circuit using the rules of Boolean algebra and associated laws. However, there is no assurance that the resultant gate circuit is the simplest. On the contrary, the Karnaugh map method provides a simple and straightforward method for minimizing Boolean functions. This method is a pictorial representation of the truth table. The map method was first proposed by Veitch and then modified by Karnaugh. Hence, these maps are known as Veitch diagrams or Karnaugh maps (K-maps).

K-maps are made up of a number of squares, each square representing a minterm. Since any Boolean function can be represented by the sum of minterms, it can be represented in the map from the area enclosed by the squares whose minterms are included in the function.

Two-variable K-maps. A two-variable K-map has 22(4 cells), a three-variable K-map has 23(8 cells) and a four-variable K-map has 24(16 cells) and so on. The procedure for simplification using a K-map, gives the truth table of the gate circuit as follows.

Given: Truth table, as in Table 17.28(a)

Step 1: A two-variable K-map has four cells, given in Table 17.28(b).

Let us transfer the contents from the truth table to the K-map. When P = 0, Q = 0, f = 0. This corresponds to the cell 0. As the output f = 0, no entry is made in this cell. P = 0, Q = 1 represents cell 1 in which case the output f = 1. So we enter 1 in this cell. When P = 1, Q = 0, f = 0, and hence, there is no entry in cell 2. Finally when P = 1, Q = 1, enter 1 in cell 3. Thus, we have transferred the contents from the truth table to the K-map as given in Table 17.28(c). We see that cells 0 and 1 are adjacent cells. Similarly 0 and 2, 2 and 3, and 1 and 3 are adjacent cells.

Step 2: Adjacent cells may have one or more Boolean variables in common.

Group the two ones in the column. When the 1s in adjacent cells, either in a row or column, are grouped or circled, the resultant group is called a sub-cube. We can now find the variables which remain unaltered in the group, as shown in Fig. 17.28(d).

P varies from (= 0) to P(= 1) whereas Q is the variable which is unaltered. Hence,

f = Q.

If on the other hand the entries in the K-map are as given in Table 17.28(e).

Now the solution is f = , since Q varies from 0 to 1 but P remains as . As another variation let the K-map have the following entries, given in Table 17.28(f). The output is

f = P + Q.

TABLE 17.28(a) The given truth table

P Q f
0 0 0
0 1 1
1 0 0
1 1 1

TABLE 17.28(b) The two variable K-map cell representation

TABLE 17.28(c) The truth table to represent the pair

TABLE 17.28(d) The adjacent cell with the same variables

TABLE 17.28(e) The adjacent cell with the same variables

TABLE 17.28(f) The adjacent cell with the same variables

EXAMPLE

Example 17.10: Simplify the Boolean function: f = Q + P + PQ, using the K-map.

Solution:

f is in the sum of products (SOP) form.

= 0,    P = 1,     = 0,    Q = 1

Therefore, the entries into the K-map are made as given in Table 17.29(a).

TABLE 17.29(a) The truth table for Q + P + PQ

And the simplified function is space f = P + Q.

Consider a special case where,

f = Q + P

Here, while making the entries in the K-map, shown in Table 17.29(b), it is not possible to form groups as the adjacent cells do not have 1s. So, the function cannot be simplified further.

Three-variable K-maps. If the Boolean expression has three variables, instead of two variables, then to understand how to represent it on the K-map, look at the K-map given in Table 17.30(a).

This K-map has 23(8) cells and the variables on the top of the map are represented in Gray code and not in binary to ensure that adjacent cells will vary by only one Boolean variable. The characteristic of this sequence is that there is only one bit change either from 1 to 0 or 0 to 1. Now let a Boolean function be represented in sum of products (SOP) form.

In the cells 000 () and 001 (R), we represent 1s, as shown in Fig. 17.30(b).

P remains as and the variable Q remains unaltered as

As the adjacent cells have 1s, circle these 1s and we remove the non-common variable and retain the common variable. The simplified Boolean function is:

TABLE 17.29(b) The simplified truth table for Q + P

TABLE 17.30(a) The three variable K-map

TABLE 17.30(b) The K-map for

EXAMPLE

Example 17.11: Simplify the Boolean function using the K-map.

Solution: Mapping the function f on the K-map, shown in Table 17.31, all the four product terms are covered by P. Hence, the simplified function is,

f = .

TABLE 17.31 The K-map for

EXAMPLE

Example 17.12: Simplify the Boolean function using the K-map:

Solution: Mapping the variables, given in Table.17.32, all the four product terms are covered by R. Hence, f = R. P varies, Q varies; R is unchanged

TABLE 17.32 The K-map for

Four-variable K-maps. If the Boolean expression has four variables, then the representation in the K-map is as follows:

This K-map has 24 (16) cells and the variables on the map are represented in Gray code. As a result, there is only one bit change either from 1 to 0 or 0 to 1. The binary numbers along the top of the map represent the conditions of R and S along any column and binary numbers along the left side represent the conditions of P and Q along any row, as given in Table 17.33.

TABLE 17.33 A four Variable K-map

Rules for finding the minimal solution using the maps are:

1. Always form sub-cubes of adjacent cells. The sub-cubes are formed by concatenating 2n cells.
2. If n = 0 then the cell has no adjacent cells and cannot be minimized further.
3. Find all cells that are adjacent to only one other cell i.e., for n = 1. These form sub-cubes of two each.
4. Find the sub-cubes that lead to maximal sub-cubes of four cells for n = 2 and then eight cells for n = 3, etc.
5. The minimal solution is formed by the sub-cubes which are as large as possible.

In the case of a four-variable map:

1. If n = 0, it represents one square, giving a term of four literals.
2. If n = 1, it represents two adjacent squares which represent a term of three literals.
3. If n = 2, it represents four adjacent squares resulting in a term of two literals.
4. If n = 3, it represents eight adjacent squares resulting in a term of single literal.
5. If n = 4, it represents sixteen adjacent squares and the function is equal to 1.
EXAMPLE

Example 17.13: Simplify :

1. Using Boolean simplification
2. Using K-map

Solution:

1. Taking the terms 1 and 2, we get

Taking the terms 3 and 4, we get

Taking the terms 2 and 5, we get

Now considering Eqs. (1) and (2), we get

From Eqs. (3) and (4), we get

2. Using K-Maps:

Let us first map the product terms in the K-map, given in Table 17.34. We get the sub-cube covered by minterms 0, 1, 2, 3; and are unchanged, for the sub-cube covered by the minterms 1, 5; , and S are unchanged. Hence, the minimal solution is

TABLE 17.34 The K-map of example 15

Don’t Care Conditions. An unused input combination in any digital circuit under normal operating conditions is known as a don’t care condition. These conditions are not represented as 1 or 0 in the K-map but are represented as ‘X’ or ‘d’. When choosing adjacent squares these can be assumed as 1 or 0 whichever gives the minimal solution. A don’t care condition need not be considered at all, if it does not contribute to a maximum sub-cube.

EXAMPLE

Example 17.14: Simplify the expression f (P, Q, R, S) = (0, 1, 2, 3, 8, 9) and d(P, Q, R, S) = (12, 13, 14)

Solution:

TABLE 17.35 The K-map of example 16

Let us first represent the values on the K-map as given in Table 17.35. For the sub-cube covered by minterms 0, 1, 2, 3; is unchanged and for the sub-cube covered by minterms 8, 9, 12, 13; we assume the two don’t care conditions in 12, 13 as 1s to get a minimal solution. By sub-cubing 8, 9, 12, 13; we get P. Hence, the minimal solution is f = + P

Design Procedure. The design of a combinational circuit starts with the statement of the problem and ends with the logic diagram. The procedure involves the following steps:

1. The statement of the problem is given.
2. Identify the number of inputs and outputs required and assign variable names.
3. The truth table to define the relation between the input and output is defined.
4. The simplified Boolean function is obtained.
5. The logic diagram is drawn.
SOLVED PROBLEMS

Example 17.16: Reduce the Boolean expressions,

1. f = AB + + + C(AB + C)
2. f = AB + A(B + C) + B(B + C)
3. f = AB + + AC(AB + C)

Solution:

(a)

(b)

f = AB + + + C(AB + C)

AB + + + C(AB + C) = AB + + + CAB + C

= 1 + + C(AB + 1) = 1 + + + C = 1

(c)

f = AB + A(B + C) + B(B + C) = AB + AB + AC + BB + BC

= AB + AC + B + BC = AB + AC + B(1 + C)

= AB + AC + B = B(1 + A) + AC

= B + AC

(d)

f = AB + + AC(AB + C)

AB + + AC(AB + C) = AB + + AABC + ACC

= AB + + ACC = AB + + + AC

= + B + + AC    since A + B = A + B (Commutative law)

= + C + B + = + C + B +

= + B + 1 = 1

Example 17.17: Draw the logic circuit for Boolean equation f = PQ +

Solution:

The Boolean function is implemented as shown in Fig. 17.32.

FIGURE 17.32 The logic circuit for the given Boolean functions

Example 17.18: Write the Boolean equation for the logic circuit shown in Fig. 17.33 and reduce the equation.

FIGURE 17.33 The logic circuit

Solution:

Example 17.19: Simplify the following three variable function using the Boolean algebra, f = m(1, 3, 5, 7).

Solution:

From minterms, we can write the expression in Sum of Products form:

f = R + QR + PR + PQR

If we apply the Boolean rules

= R( + Q) + PR( + Q) = R + PR = R( + P) = R

Example 17.20: Reduce the following Boolean function using the K-map.

f(P, Q, R, S) = (0, 1, 4, 5, 8, 9)

Solution:

Let us first map the terms on the K-map as shown in Table 17.36. From the K-map f (P, Q, R, S) = +

TABLE 17.36 The K-map for the Boolean function in Example 17.20.

SUMMARY
1. Boolean algebra forms the basis for the design and simplification of digital systems.
2. Combinational circuits are digital circuits in which the output at any given instant of time depends only on the inputs at that instant. The previous history of the inputs is inconsequential to the output.
3. Boolean identities and laws help in simplifying Boolean functions.
4. Combinational circuits can be designed using only NAND gates in the SOP form and only NOR gates in the POS form.
5. Boolean expressions can be converted from one canonical form to the other by interchanging the symbols and and listing those numbers that are missing in the original.
6. In Karnaugh-maps, the variables on the map are represented in the Gray code. The characteristic of this sequence is that there is only one bit change either from 1 to 0 or 0 to 1 in the adjacent cells.
7. The unused input combinations under normal operating conditions are known as don’t care conditions. These conditions are represented as X or d in the K-map. When choosing the adjacent squares these can be assumed as 1 or 0, whichever gives the minimal solution.
MULTIPLE CHOICE QUESTIONS
1. The relationship that represents the dual of the Boolean property A + 1 = 1 is:
1. A.0 = 0
2. A + 0 = 0
3. A.A = A
4. A.1 = 1
2. The best definition of a literal is:
1. A Boolean variable in true or the complement of a Boolean variable
2. A Boolean variable interpreted literally
3. The actual understanding of a Boolean variable
4. None of the above
3. Simplify the Boolean expression (A + B + C)() + (A + B + C)(D) and choose the best answer:
1. A + B + C
2. D
3. A
4. None of the above
4. Which of the following relationships represents the dual of the Boolean property x + y = x + y?
1. (x + y) = xy
2. x(y) = xy
3. x + y = xy
4. x( + y) = xy
5. Simplification of the Boolean expression ( + )( + + ) + ( + ) yields which of the following results:
1. A + B
2. C + D + E
6. An equivalent representation for the Boolean expression + 1 is:
1. A
2. 1
3. 0
7. Which of these gates are called universal gates?
1. NAND and NOR
2. OR and AND
3. AND and NOT
4. OR and NOT
8. Determine the values of A, B, C, and D that make the sum term A + + + D equal to zero:
1. A = 1, B = 0, C = 0, D = 1
2. A = 1, B = 0, C = 1, D = 0
3. A = 0, B = 1, C = 1, D = 0
4. A = 1, B = 0, C = 1, D = 1
9. Applying the distributive law to the expression A(B+ + D), we get:
1. AB + AC + AD
2. ABCD
3. A + B + C + D
4. AB + A + AD
10. Applying De Morgan’s theorem to the expression , we get:
1. + +
2. + B +
3. A + +
4. ( + )
11. How many gates would be required to implement the following Boolean expression before simplification: XY + X (X + Z) + Y (X + Z)?
1. 1
2. 2
3. 4
4. 5
1. Prepare a truth table for the given Boolean expression:

ABC + A + AC

2. Prove the following rules using the truth table:
1. X + XY = X
2. X + Y = X + Y
3. Convert the following expression to SOP:
1. ( + )( + )
2. ( + C)(AB + AB + AC)
4. Convert the following from one form to another:
1. f (A, B, C) = (1, 3, 5, 7)
2. f (A, B, C, D) = Π(0, 2, 5, 7, 12, 13)
5. Express the following functions in sum of minterms or product of maxterms:

f (A, B, C, D) = ABC + AD + CD

1. Obtain the simplified expression in the sum of products for the following Boolean functions:
1. xy + + x
2. A + + BC
2. Obtain the simplified expression in the sum of products for the following Boolean functions:
1. a + bc + a
2. xz + xy + yz + xyz
3. Obtain the simplified expression in the sum of products and product of sum for the Boolean function and implement using the AND–OR gates:

f (A, B, C, D) = ∑(0, 1, 4, 5, 10, 11, 15)

4. Obtain the simplified expression in the sum of products and product of sum for the Boolean function and implement using the AND–OR gates:
5. Obtain the simplified expression in the sum of products and product of sum for the Boolean function and implement using the AND–OR gates:
6. Obtain the simplified expressions in product of sums:
1. f (x, y, z) = Π(0, 1, 4, 5)
2. f (A, B, C, D) = Π(0, 1, 2, 3, 4, 10, 11)
3. f (w, x, y, z) = Π(1, 3, 5, 7, 13, 15)
7. Implement the following functions with NAND gates. Assume that both the normal and complement inputs are available.
1. BD + BCD + AC +
2. (AB + )(C + D)
8. Simplify the Boolean function F using don’t care conditions d, in (1) sum of products and (2) product of sums:
9. Simplify the Boolean function F using don’t care conditions d, in (1) sum of products and (2) product of sums:
10. Implement the following function with either NAND or NOR gates. Only normal inputs are available.
UNSOLVED PROBLEMS
1. Simplify using Boolean algebra techniques:
1. (A + B) + (B + AA)(A + )
2. ( + B)( + B)
2. Simplify the following Boolean functions using K-maps and realize the gate circuits using only the NAND gates.
1. f (A, B, C) = + B + AB + AC
2. f (A, B, C) = B + B + BC + A
3. f (A, B, C, D) = (0, 1, 2, 3, 8, 9, 10, 11)
3. Simplify and implement using (i) only NAND gates and (ii) only NOR gates.
f(A, B, C, D) = (0, 1, 2, 3, 8, 9, 10, 11)
d(A, B, C, D) = (9, 12, 13)
4. What is the output Q of the circuit shown in Fig. 17p.4. Implement the circuit using only the NAND gates.
5. Draw and use a K-map to produce a minimized SOP and POS expression for:
f (w, x, y, z) = (0, 2, 6, 7, 8, 10, 11, 15)

FIGURE 17p.4 The given gate circuit

6. Simplify the following Boolean function using the K-map, .
7. Simplify using the K-map.
8. Simplify the Boolean function,
9. Simplify : (a) Using Boolean simplification (b) Using K-map
10. A combinational circuit has four inputs and one output. The output is 1 when (a) all the inputs are equal to 1; (b) none of the inputs is equal to 1; and (c) when the odd number of inputs is equal to 1. Design a logic circuit to implement the above.