Simplification of Logic Expressions:Derivation of Minimal Sums by Karnaugh Map.

Derivation of Minimal Sums by Karnaugh Map

Because of its pictorial nature, a Karnaugh map is a very powerful tool for deriving manually all prime implicants, irredundant disjunctive forms, minimal sums, and also absolute minimal sums. Algebraic concepts such as prime implicants and consensuses can be better understood on a map.

One can derive all prime implicants, irredundant disjunctive forms, and minimal sums by the following procedures on Karnaugh maps, when the number of variables is small enough for the map to be manageable.

Procedure 28.1: Derivation of Minimal Sums on a Karnaugh Map

This procedure consists of three steps:

1. On a Karnaugh map, encircle all the 1-cells with rectangles (also squares as a special case), each of which consists of 2i 1-cells, choosing i as large as possible, where i is a non-negative integer. Let us call these loops prime implicant loops, since they correspond to prime implicants in the case of the Karnaugh map for four or fewer variables. (In the case of a fiveor six-variable map, the correspondence is more complex, as will be explained later.) Examples are shown in Figure 28.2(a).

2. Cover all the 1-cells with prime-implicant loops so that removal of any loops leaves some 1-cells uncovered. These sets of loops represent irredundant disjunctive forms. Figures 28.2(b) through 28.2(e) represent four irredundant disjunctive forms, obtained by choosing the loops in Figure 28.2(a) in four different ways. For example, if the prime-implicant loop x1x3x4 is omitted in Figure 28.2(b), the 1-cells for (x1,x2,x3,x4) = (1 1 0 1) and (1 0 0 1) are not covered by any loops.

3. From the sets of prime implicant loops formed in Step 2 for irredundant disjunctive forms, choose the sets with a minimum number of loops. Among these sets, the sets that contain as many of the largest loops as possible (a larger loop represents a product of fewer literals) represent minimal sums. Figure 28.2(c) expresses the unique minimal sum for this function, since it contains one less loop than Figure 28.2(b), (d), or (e).

It is easy to see, from the definitions of prime implicants, irredundant disjunctive forms, and minimal sums, why Procedure 28.1 works.

When we derive irredundant disjunctive forms or minimal sums by Procedure 28.1, the following property is useful. When we find all prime-implicant loops by Step 1, some 1-cells may be contained in only one loop. Such 1-cells are called distinguished 1-cells and are labeled with asterisks. (The 1-cells shown with asterisks in Figure 28.2(a) are distinguished 1-cells.) A prime implicant loop that contains distinguished 1-cells is called an essential prime implicant loop. The correspond- ing prime implicant is an essential prime implicant, as already defined. In every irredundant disjunctive form and every minimal sum to be found in Step 2 and 3, respectively, essential prime implicants must be included, since each 1-cell on the map must be contained in at least one prime implicant loop and distinguished 1-cells can be contained only in essential prime implicant loops. Hence, if essential prime implicant loops are first identified and chosen, Procedure 28.1 is quickly processed.

Even if the don’t-care condition d is contained in some cells, prime implicants can be formed in the same manner, by simply regarding d as being 1 or 0 whenever necessary to draw a greater prime implicant loop. For example, in Figure 28.3, we can draw a greater rectangular loop by regarding two d ’s as being 1. One d is left outside and is regarded as being 0. We need not consider loops consisting of d ’s only.

Maps for Five and Six Variables

The Karnaugh map is most useful for functions of four or fewer variables, but it is often useful also for functions of five or six variables. A map for five variables consists of two four-variable maps, as shown in Figure 28.4, one for each value of the first variable. A map for six variables consists of four four-variable maps, as shown in Figure 28.5, one for each combination of values of the first two variables. Note that the four maps in Figure 28.5 are arranged so that binary numbers represented by x1 and x2 differ in only one bit horizontally and vertically (the map for x1 = x2 = 1 goes to the bottom right-hand side).

In a five-variable map, 1-cells are combined in the same way as in the four-variable case, with the additional feature that rectangular loops of 2i 1-cells that are on different four-variable maps can be combined to form a greater loop replacing the two original loops only if they occupy the same relative position on their respective four-variable maps. Notice that these loops may be inside other loops in each four-variable map. For example, if f15 and f31 are 1, they can be combined; but even if f15 = f29 = 1, f15 and f29 cannot. In a six-variable map, only 1-cells in two maps that are horizontally or vertically adjacent can be combined if they are in the same relative positions. In Figure 28.5, for example, if f5 and f37 are 1, they can be combined; but even if f5 and f53 are 1, f5 and f53 cannot. Also, four 1-cells that occupy the same relative positions in all four-variable maps can be combined as representing a single product. For example, f5, f21, f37, and f53 can be combined if they are 1.

In the case of a five-variable map, we can find prime implicant loops as follows.

Procedure 28.2: Derivation of Minimal Sums on a Five-Variable Map

1. Unlike Step 1 of Procedure 28.1 for a function of four variables, this step requires the following two substeps to form prime implicant loops:

a. On each four-variable map, encircle all the 1-cells with rectangles, each of which consists of 2i 1-cells, choosing the number of 1-cells contained in each rectangle as large as possible. Unlike the case of Procedure 28.1, these loops are not necessarily prime implicant loops because they may not represent prime implicant, depending on the outcome of substep b.

In Figures 28.6 and 28.7, for example, loops formed in this manner are shown with solid lines.

b. On each four-variable map, encircle all the 1-cells with rectangles, each of which consists of 2i 1-cells in exactly the same relative position on the two maps, choosing i as great as possible. Then connect each pair of the corresponding loops with an arc. On each four-variable map, some of these loops may be inside some loops formed in substep a.

In Figure 28.6, one pair of loops that is in the same relative position is newly formed. One member of the pair, shown in a dotted line, is contained inside a loop formed in substep a. The pair is connected with an arc. The other loop coincides with a loop formed in substep a. In Figure 28.7, two pairs of loops are formed: one pair is newly formed, as shown in dotted lines, and the second pair is the connection of loops formed in substep a.

The loops formed in substep b and also those formed in substep a but not contained in any loop formed in substep b are prime implicant loops, since they correspond to prime implicants.

In Figure 28.6, the loop formed in substep a, which represents x1x2 x3x5 , is contained in the prime implicant loop formed in substep b, which represents x2x3x5. Thus, the former loop is not a prime implicant loop, and consequently x1x2 x3x5 is not a prime implicant.

2. Processes for deriving irredundant disjunctive forms and minimal sums are the same as Steps 2 and 3 of Procedure 28.1. D In the case of six-variable map, the derivation of prime implicant loops requires more comparisons of four-variable maps, as follows.

Procedure 28.3: Derivation of Minimal Sums on a Six-Variable Map

1. Derivation of all prime-implicant loops requires the following three substeps:

a. On each four-variable map, encircle all the 1-cells with rectangles, each of which consists of 2i 1-cells, choosing i as great as possible.

b. Find the rectangles (each of which consists of 2i 1-cells) occupying the same relative position on every two adjacent four-variable maps, choosing i as great as possible. (Two maps in diagonal positions are not adjacent.) Thus, we need four comparisons of two maps (i.e., upper two maps, lower two maps, left two maps, and right two maps).

c. Then find the rectangles (each of which consists of 2i 1-cells) occupying the same relative position on all four-variable maps, choosing i as great as possible. Prime implicant loops are loops formed at substeps c, loops formed at b but not contained inside those at c, and loops formed at a but not contained inside those formed at b or c.

2. Processes for deriving irredundant disjunctive forms and minimal sums are the same as Steps 2 and 3 of Procedure 28.1. D An example is shown in Figure 28.8.

Irredundant disjunctive forms and minimal sums are derived in the same manner as in the case of four variables.

Procedures 28.1, 28.2, and 28.3 can be extended to the cases of seven or more variables with increasing complexity. It is usually hard to find a minimal sum, however, because each prime implicant loop consists of 1-cells scattered in many maps.