Table of Contents
Chapter 3 Simplification of Switching Functions
Simplification Goals
Example 3.1
Minimization Methods
Minimum SOP and POS Representations
Karnaugh Maps
Figure 3.1 Venn diagram and equivalent K-map for two variables
Figure 3.2 Venn diagram and equivalent K-map for three variables
Figure 3.3 (a) -- (d) K-maps for four and five variables
Figure 3.3 (e) -- (f) K-maps for six variables
Plotting (Mapping) Functions in Canonical Form on a K-map
Figure 3.4 Plotting functions on K-maps
Figure 3.5 K-maps for f(a,b,Q,G) in Example 3.4 (a) Minterm form. (b) Maxterm form.
Figure 3.6 K-map of Figure 3.5(a) with variables reordered: f(Q,G,b,a).
Plotting Functions in Algebraic Form
Figure 3.7 -- Example 3.6. (a) Venn diagram form. (b) Sum of minterms. (c) Maxterms.
Figure 3.8 -- Example 3.7. (a) Maxterms, (b) Minterms, (c) Minterms of f ?.
Figure 3.9 -- Example 3.8. (a) K-map of f?, (b) K-map of f.
Simplification of Switching Functions Using K-maps
Figure 3.10 K-map for Example 3.9
Simplification Guidelines for K-maps
Prime Implicants and Covers
Figure 3.11 K-map illustrating implicants
Algorithm 3.1 -- Generating and Selecting Prime Implicants
Figure 3.12 -- Example 3.10 (Illustrating Algorithm 3.1)
Algorithm 3.2 -- Generating and Selecting Prime Implicants (Revisited)
Figure 3.13 -- Example 3.11 (Illustrates Algorithm 3.2)
Figure 3.14 -- Example 3.12 f(A,B,C,D) = ?m(0,5,7,8,10,12,14,15)
Figure 3.15 -- Example 3.13 f(A,B,C,D) = ?m(1,2,3,6) = A?C + BC?
Figure 3.16 -- Example 3.14 f(A,B,C,D) = B?D? + B?C? + BCD
Figure 3.17 -- Example 3.15 Function with no essential prime implicants.
Figure 3.18 -- Example 3.16 Minimizing a five-variable function. f(A,B,C,D,E) = ?m(0,2,4,7,10,12,13,18,23,26,28,29)
Prime Implicates and Covers
Algorithm 3.3 -- Generating and Selecting Prime Implicates
Algorithm 3.4 -- Generating and Selecting Prime Implicates (Revisited)
Example 3.17 -- Find the minimum POS form of the function f(A,B,C,D) = ?M(0,1,2,3,6,9,14)
Algorithm 3.5 -- Finding MPOS of f from f?
Example 3.18 -- Find the MPOS of the following function using Algorithm 3.5 f(A,B,C,D) = ?M(0,1,2,3,6,9,14)
Example 3.19 -- Minimum covers of f(A,B,C,D) = ? M (3,4,6,8,9,11,12,14) and its complement.
Figure 3.22 Finding a minimal POS expression for a 5-variable function.
Figure 3.23 Deriving POS and SOP forms of a function.
Example 3.22 -- Minimizing a Function with Don’t Cares. f(A,B,C,D) = ?m(1,3,4,7,11) + d(5,12,13,14,15) = ?M(0,2,6,8,9,10) ? D(5,12,13,14,15)
Example 3.23 -- Design a circuit to distinguish BCD digits ? 5 from those ? 5.
Example 3.23 (concluded)
Timing Hazards in Combinational Logic Circuits
Figure 3.27 (a)--(b) Illustration of a static hazard.
Figure 3.27 (c) Illustration of a static hazard (con’t)
Figure 3.27 (d) Illustration of a static hazard (con’t).
Figure 3.28 Identifying hazards on a K-map.
Figure 3.29 Hazard-free network.
Figure 3.30 (a)--(b) Example of a static-0 hazard.
Figure 3.30 (c)--(d) Example of a static-0 hazard (con’t).
Figure 3.31 Dynamic hazards.
Quine-McCluskey Minimization Method
Example 3.24 -- Use the Q-M method to find the MSOP of the function f(A,B,C,D) = ?m(2,4,6,8,9,10,12,13,15)
Step 1 -- List Prime Implicants in Groups (Example 3.24)
Step 2 -- Generate Prime Implicants (Example 3.24)
Step 3 -- Prime Implicant Chart (Example 3.24)
Step 4 -- Reduced Prime Implicant Chart (Example 3.24)
The Resulting Minimal Realization of f
How the Q-M Results Look on a K-map
Covering Procedure
Coverage Example f(A,B,C,D) = ?m(0,1,5,6,7,8,9,10,11,13,14,15)
Reduced PI Charts
Cyclic PI Charts
Using the Q-M Procedure with Incompletely Specified Functions
Minimizing Table for Example 3.25
PI Chart for Example 3.25
Results of Minimization for Example 3.25
Minimizing Circuits with Multiple Outputs
Minimizing Table for Example 3.26
Prime Implicant Chart for Example 3.26
Reduced Prime Implicant Chart for Example 3.26
Minimum Realizations for Example 3.26
Figure 3.34 Reduced multiple-output circuit.
Petrick’s Algorithm for Selecting a Minimal Cover (Algorithm 3.6)
Example 3.27 -- Example of Petrick’s Algorithm
The Cover Function for Example 3.27
Figure 3.35
Figure 3.36
Figure 3.37
Figure 3.38
Figure P3.1
|
Author: Dr Bill Carroll
|