Lecture Notes

Digital Logic And Design (DLD)

Dr. Tahira Shujah

(Lecture 6)
Boolean Minimization using Karnaugh Map up to 4 Variable for SOP
and POS. Don’t Care Conditions Verification by using Binary
Testing Techniques for standard and Minimized form
Karnaugh Map:-
The K-map is a graphical representation that provides a systematic method for simplifying the
Boolean Expression.
 The Karnaugh map is an array of cells in which each cell represents a binary value of the
input variables.
 The cells are arranged in a way so that simplification of a given expression is simply a
matter of properly grouping the cells.
 Karnaugh maps can be used for expressions with two, three, four, and five variables
Two Variable K-map:
For n variable k-map 2n cells are required. Therefore, for 2 variable k-map, 22 =4 cells will be
required.

Three Variable K-map:

For n variable k-map 2n cells are required. Therefore, for 3 variable k-map, 23=8 cells will be
required.

Four Variable K-map:

For n variable k-map 2n cells are required. Therefore, for 4 variable k-map, 24=16 cells will be
required.
Q: Plot the Boolean Expression:

Mapping a Standard SOP Expression:

 For an SOP expression in standard form, a 1 is placed on the Karnaugh map for each
product term in the expression.
 Each 1 is placed in a cell corresponding to the value of a product term.
Step 1: Determine the binary value of each product term in the standard SOP expression.
Step 2: As each product term is evaluated, place a 1 on the Karnaugh map in the cell having the
same value as the product term.
 For Practice: Example 4-23, 4-24
Mapping a Nonstandard SOP Expression:
 A Boolean expression must first be in standard form before you use a Karnaugh map.
 If an expression is not in standard form, then it must be converted to standard form.
 Since an expression should be evaluated before mapping anyway, numerical expansion is
probably the most efficient approach.
Numerical Expansion of a Nonstandard Product Term:
Recall that a nonstandard product term has one or more missing variables.
 For example, assume that one of the product terms in a certain 3-variable SOP expression
is AB.
 This term can be expanded numerically to standard form as follows.
o First, write the binary value of the two variables and attach a 0 for the missing
variable C: 100.
o Next, write the binary value of the two variables and attach a 1 for the missing
variable C: 101.
 The two resulting binary numbers are the values of the standard SOP terms ABC and ABC.
 As another example, assume that one of the product terms in a 3-variable expression is B
(remember that a single variable counts as a product term in an SOP expression).
 This term can be expanded numerically to standard form as follows.
o Write the binary value of the variable; then attach all possible values for the missing
variables A and C as follows:

 The four resulting binary numbers are the values of the standard SOP terms ABC, ABC,
ABC, and ABC.

For Practice: Example 4-25, 4-26

 Karnaugh Map Simplification of SOP Expressions:
The process that results in an expression containing the fewest possible terms with the
fewest possible variables is called minimization.
 After an SOP expression has been mapped, a minimum SOP expression is obtained by
grouping the 1s and determining the minimum SOP expression from the map.

Grouping of cells for simplification:

 Grouping 1s:
1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In
the case of a 3-variable map, 23 = 8 cells is the maximum group.
2. Each cell in a group must be adjacent to one or more cells in that same group, but
all cells in the group do not have to be adjacent to each other.
3. Always include the largest possible number of 1s in a group in accordance with rule
1.
4. Each 1 on the map must be included in at least one group. The 1s already in a group
can be included in another group as long as the overlapping groups include
noncommon 1s.

 Please refer to lecture video for further explanation of this Figure.

Determining the Minimum SOP Expression from the Map:
 When all the 1s representing the standard product terms in an expression are properly
mapped and grouped, the process of determining the resulting minimum SOP expression
begins.
Rules followed for K-Map simplification:
The following rules are applied to find the minimum product terms and the minimum SOP
expression:
 Group the cells that have 1s.
 Each group of cells containing 1s creates one product term composed of all variables that
occur in only one form (either uncomplemented or complemented) within the group.
 Variables that occur both uncomplemented and complemented within the group are
eliminated.
 Determine the minimum product term for each group.
 For a 3-variable map:
o A 1-cell group yields a 3-variable product term
o A 2-cell group yields a 2-variable product term
o A 4-cell group yields a 1-variable term
o An 8-cell group yields a value of 1 for the expression
 For a 4-variable map:
o A 1-cell group yields a 4-variable product term
o A 2-cell group yields a 3-variable product term
o A 4-cell group yields a 2-variable product term
o An 8-cell group yields a 1-variable term
o A 16-cell group yields a value of 1 for the expression 3.
 When all the minimum product terms are derived from the Karnaugh map, they are
summed to form the minimum SOP expression.
 Groups do not include any cell containing zero “0”
  Groups may be horizontal or vertical but not diagonal:

 Group must contain 2n cells (1,2,4,8,….)

 Each group should be as large as possible.

Example:

 For Further Practice: Example 4-28 to 4-31

Mapping Directly from a Truth Table:
In the figure below you can see that the Boolean expression, the truth table, and the Karnaugh
map are simply different ways to represent a logic function.

“Don’t Care” Conditions:

Sometimes a situation arises in which some input variable combinations are not allowed.
For example, recall that in the BCD code covered in Chapter 2,
 there are six invalid combinations: 1010, 1011, 1100, 1101, 1110, and 1111.
 Since these unallowed states will never occur in an application involving the BCD
code, they can be treated as “don’t care” terms with respect to their effect on the output.
 That is, for these “don’t care” terms either a 1 or a 0 may be assigned to the output; it
really does not matter since they will never occur.
Advantage of “don’t care” terms In K-map:
The “don’t care” terms can be used to advantage on the Karnaugh map.
 Figure shows that for each “don’t care” term, an X is placed in the cell.
 When grouping the 1s, the Xs can be treated as 1s to make a larger grouping or as 0s if
they cannot be used to advantage.
 The larger a group, the simpler the resulting term will be.
  For Practice: Example 4-32
 Note: Karnaugh Map POS Minimization follows same rules as
explained for SOP.
 For Practice POS K-mapping and simplification of POS expression:
Example 4-33, 4-34, 4-35

Converting Between POS and SOP Using the Karnaugh Map:

When a POS expression is mapped, it can easily be converted to the equivalent SOP form
directly from the Karnaugh map.Also, given a mapped SOP expression, an equivalent POS
expression can be derived directly from the map. This provides a good way to compare both
minimum forms of an expression to determine if one of them can be implemented with fewer gates
than the other.
 For a POS expression, all the cells that do not contain 0s contain 1s, from which the SOP
expression is derived.
 Likewise, for an SOP expression, all the cells that do not contain 1s contain 0s, from which
the POS expression is derived.

Example 4–36 illustrates this conversion.