Simplification of SOP Expression

Simplification of SOP Expression

AU: May-05,09,10,11,13,14, Dec.-03,08,11,14

• A pair of 1s eliminates one variable, a quad of 1s eliminates two variables and an octet of 1s eliminates three variables.

• In general, when a variable appears in both complemented and uncomplemented form within a group, that variable is eliminated from the resultant expression.

• Variables that are same in all with the group must appear in the final expression.

• Each group gives us a product term and summation of all product term gives us a Boolean expression.

• Each product term implies the function and, hence is an implicant of the function.

• All the implicants of a function determined using a Karnaugh map are the prime implicants.

• From the above discussion we can outline generalized procedure to simplify Boolean expressions as follows:

1. Plot the K-map and place 1s in those cells corresponding to the 1s in the truth table or sum of product expression. Place 0s in other cells.

2. Check the K-map for adjacent 1s and encircle those 1s which are not adjacent to any other 1s. These are called isolated 1s.

3. Check for those 1s which are adjacent to only one other 1 and encircle such pairs.

4. Check for quads and octets of adjacent 1s even if it contains some 1s that have already been encircled. While doing this make sure that there are minimum number of groups.

5. Combine any pairs necessary to include any 1s that have not yet been grouped.

6. Form the simplified expression by summing product terms of all the groups.

Examples for Understanding

Solution:

Step 1: Fig. 1.3.1 (a) shows the K-map for four variables and it is plotted according to the given expression.

Step 2: There are no isolated 1s.

Step 3: There are no such 1s which are adjacent to only one other 1.

Step 4: There are three quads formed by cells 0, 2, 8, 10, cells 8, 10, 12, 14 and cells 2, 3, 10, 11. These quads are combined and referred to as group 1, group 2 and group 3 respectively.

Step 5: All 1s have already been grouped.

Step 6: Each group generates a term in the expression for Y. In group 1 variables A and C are eliminated, in group 2 variables B and C are eliminated and in group 3 variables A and D are eliminated and we get,

Solution :

Step 1: Fig. 1.3.2 (a) shows the K-map for four variables and it is plotted according to the given expression.

Step 2: There are no isolated 1s.

Step 3: The 1 in the cell 1 is adjacent only to 1 in the cell 5, the 1 in the cell 6 is adjacent only to the 1 in the cell 7, the 1 in the cell 12 is adjacent only to the 1 in the cell 13 and the 1 in the cell 11 is adjacent only to the 1 in the cell 15. These pairs are combined and referred to as group 1-4 respectively.

Step 4: There is no octet, but there is a quad. However, all 1s in the quad have already been grouped. Therefore this quad is ignored.

Step 5: All 1s have already been grouped.

Step 6: Each group generates a term in the expression for Y. In group 1 variable B is eliminated. Similarly, in AB 111 group 2-4 variables D, D and B are eliminated one in each group. We finally get minimum sum of products form as,

Example 1.3.3 Simplify the logic function specified by the truth Table 1.3.1 using the Karnaugh map method. Y is the output variable, and A, B and C are the input variables.

Solution :

Step 1: Fig. 1.3.3 (a) shows the K-map for three variables and it is plotted according to given truth table.

Step 2: There are no isolated 1s.

Step 3: The 1 in the cell 0 is adjacent only to 1 in the cell 4 and the 1 in the cell 3 is adjacent only to 1 in the cell 7. These two pairs are grouped and referred to as group 1 and group 2.

Step 4:There is no octet and quad.

Step 5:All 1s have already been grouped.

Step 6:In group 1 and group 2 variable A is eliminated and we get,

Examples for practice

Essential Prime Implicants

• After grouping the cells, the sum terms which appear in the K-map are called prime implicants groups.

• It is observed that some cells may appear in only one prime implicants group; while other cells may appear in more than one prime implicants group.

• In Fig. 1.3.2 (b), cells 1, 6, 11 and 12 appear in only one prime implicants group. These cells are called essential cells and corresponding prime implicants are called essential prime implicants.

Incompletely Specified Functions (Don't Care Terms)

• In some logic circuits, certain input conditions never Occur, therefore thecorresponding output never appears. In such cases the output level is not defined, it can be either HIGH or LOW. These output levels are indicated by 'X' or `d' in the truth tables and are called don't care outputs or don't care conditions or incompletely specified functions.

• As shown in truth table given by Table 1.3.2, outputs are defined for input conditions from 00 0 to 1 0 1. For remaining two conditions of input, output is not defined, hence these are called don't care conditions for this truth table.

• A circuit designer is free to make the output for any "don't care" condition either a '0' or a '1' in order to produce the simplest output expression.

Describing Incomplete Boolean Function

• We can describe the Boolean function using either a minterm canonical formula or a maxterm canonical formula.

• In order to obtain similar-type expressions for incomplete Boolean functions we use additional term to specify don't care conditions in the original expression. This is illustrated in the following examples.

In expression,

f (A, B, C) =m (0, 2, 4) + d (1, 5)

minterms are 0, 2 and 4. The additional term d(1, 5) is introduced to specify the don't care conditions.

• This terms specifies that outputs for minterms 1 and 5 are not specified and hence these are don't care conditions.

• Letter d is used to indicate don't care conditions in the expression.

The above expression indicates how to represent don't care conditions in the minterm canonical formula. In the similar manner, we can specify the don't care conditions in the maxterm canonical formula. For example,

f(A, B, C)=II M (2, 5, 7) + d(1, 3)

Don't Care Conditions in Logic Design

• Consider the logic circuit for an even parity generator for 4-bit BCD number. The Table 1.3.3 shows the truth table for even-parity generator. (See Fig. 1.3.6 on next page)

• The truth table shows that the output for last six input conditions cannot be specified, because such input conditions does not occur when input is in the BCD form.

• The Boolean function for even parity generator with 4-bit BCD input can expressed in minterm canonical formula as,

f(A, B, C, D) =Σ m (1, 2, 4, 7, 8) + d(10, 11, 12, 13, 14, 15)

Minimization of Incompletely Specified Functions

• A circuit designer is free to make the output for any don't care condition either a 0' or '1' in order to produce the simplest output expression.

• Consider a truth table shown in Table 1.3.4.The K-map for this truth table is shown in Table 1.3.3 Truth table for even parity

Fig. 1.3.5 with x placed in the and ABC cells.

• It is not always advisable to put don't cares as 1s. This is illustrated in Fig. 1.3.5 (b). Here, the don't care output for cell ABC is taken as 1 to form a quad and don't care output for cell  is taken as 0, since it is not helping any way to reduce an expression. Using don't care conditions in this way we get the simplified Boolean expression as Y = C

• It is important to decide which don't cares to change to 0 and which to 1 to produce the best K-map grouping (i.e. the simplest expression).

Examples for understanding

• To form a quad of cells 0, 1, 2 and 3 the don't care conditions 0 and 2 are replaced

by 1s.

• The remaining don't care condition is replaced by 0 since it is not required to form any group. With these replacements we get the simplified equation as

Example 1.3.11 Find the prime implicants for the following function and determine which are essential.

F(w, x, y, z) = (0,2,4,5,6,7,8,10,13,15)AU: Dec.-08, Marks 10, Dec.-11, Marks 4

Solution: The minterms of the given function are marked with 1's in the map of Fig. 1.3.7. The Fig. 1.3.7 (a) shows two essential prime implicants. The term xz is essential because there is only one way to include minterms m₁₃ and m₁₅ within four adjacent squares. Similarly, there is only one way that minterms m₈ and m₁₀ can be combined with four adjacent squares and this gives second term . The two essential prime implicants cover eight minterms. The remaining two minterms, m₄ and m₆ must be considered next.

Examples with Solutions

Example 1.3.12 Simplify the following Boolean function F together with don't care condition using Karnaugh map method.

i) F(A,B,C,D) = Σ m(0, 6, 8, 13, 14), d (A, B,C,D) = Σ m(2,4,10)

ii) F(A,B,C,D) = ∑ m(0,2,4,5,8,14,15), d (A, B, C, D) =∑m(7,10,13)

iii) F(A,B,C,D) =Σm(4,6,7,8,12,15), d (A, B, C, D) =∑m(2, 3,5,10,11,14)

Solution:

Example 1.3.13 Express the following function as the minimal sum of products using a K-map. f(a,b,c,d) = (0,2,4,5,6,8,10,15) +20 (7,13,14)

AU May-05, Marks 12

Solution :

As shown in Fig. 1.3.11 the given example has three solutions and all are correct. Students are expected to give any one solution.

Examples for Practice

Review Questions

1. Give the steps for simplification of SOP expression.

2.What do you mean by essential prime implicants ?

3. What is don't care condition?