Section 5.5 Boolean Function Minimization
- minimal Sum of Products (mSoP)
-
A sum of products expression where all other mathematically equivalent sum of product expressions
have at least as many product terms, and
those with the same number of product terms have at least as many literals.
- minimal Product of Sums (mPoS)
-
A product of sums expression where all other mathematically equivalent product of sums
have at least as many sum terms, and
those with the same number of sum terms have at least as many literals.
Subsection 5.5.1 Minimization Using Algebraic Manipulations
To illustrate the importance of reducing the complexity of a Boolean function, consider the following function:Subsection 5.5.2 Minimization Using Pictorial Tools
The Karnaugh map was invented in 1953 by Maurice Karnaugh while working as a telecommunications engineer at Bell Labs. Also known as a K-map, it provides a pictorial view of all the possible minterms for a given number of variables. The format is a rectangular grid with a cell for each minterm. There arePlace a
in each cell that corresponds to a minterm that evaluates to in the expression.-
Combine cells with
s in them and that share edges into the largest possible groups.Larger groups result in simpler expressions.
The number of cells in a group must be a power of
The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.
Groups may overlap. In fact, this is common. However, no group should be fully enclosed by another group.
The result is the sum of the product terms that represent each group.
place a
in each cell of the Karnaugh map corresponding to a missing minterm in the expression,find groupings of the cells with
s in them,write a sum of products expression represented by the grouping of
s, andcomplement this expression,
Place a
in each cell that corresponds to a maxterm that evaluates to in the expression.-
Combine cells with
s in them and that share edges into the largest possible groups.Larger groups result in simpler expressions.
The number of cells in a group must be a power of
The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.
Groups may overlap. In fact, this is common. However, no group should be fully enclosed by another group.
The result is the product of the sum terms that represent each group.
- XOR
-
A binary operator; the result is
if one, and only one, of the two operands is otherwise the result is We will use β β to designate the XOR operation. The OR gate operation is shown in Figure 5.5.12 with inputs andFigure 5.5.12. The OR gate acting on two variables, and