Digital Logic Design

Gate-Level Minimization
 3-1 Introduction
■ Gate-level minimization refers to the design task of finding an optimal gate-
level implementation of Boolean functions describing a digital circuit.
3-2 The Map Method
■ The complexity of the digital logic gates
❑ The complexity of the algebraic expression

■ Logic minimization
❑ Algebraic approaches: lack specific rules
❑ The Karnaugh map
❑ A simple straight forward procedure
❑ A pictorial form of a truth table

■ A diagram made up of squares

❑ Each square represents one minterm
Review of Boolean Function
■ Boolean function
❑ Sum of minterms
❑ Sum of products (or product of sum) in the simplest form
❑ A minimum number of terms
❑ A minimum number of literals
Two-Variable Map
■ A two-variable map
❑ Four minterms
❑ x' = row 0; x = row 1
❑ y' = column 0; y =
column 1
❑ A truth table in square
diagram
❑ Fig. 3.2(a): xy = m3 Figure 3.1 Two-variable
❑ Fig. 3.2(b): x+y = Map
x'y+xy' +xy =
m1+m2+m3

Figure 3.2 Representation of functions in

the map
 A Three-variable Map
■ A three-variable map
❑ Eight minterms
❑ The Gray code sequence
❑ Any two adjacent squares in the map differ by only one variable
❑ Primed in one square and unprimed in the other
❑ e.g., m5 and m7 can be simplified
❑ m5+ m7 = xy'z + xyz = xz (y'+y) = xz

Figure 3.3 Three-variable Map

A Three-variable Map
❑ m0 and m2 (m4 and m6) are adjacent
❑ m0+ m2 = x'y'z' + x'yz' = x'z' (y'+y) = x'z'
❑ m4+ m6 = xy'z' + xyz' = xz' (y'+y) = xz'
 Example 3.1
■ Example 3.1: simplify the Boolean function F(x, y, z) = Σ(2, 3, 4, 5)
❑ F(x, y, z) = Σ(2, 3, 4, 5) = x'y + xy'

Figure 3.4 Map for Example 3.1, F(x, y, z) = Σ(2, 3, 4, 5) = x'y

+ xy'
 Example 3.2
■ Example 3.2: simplify F(x, y, z) = Σ(3, 4, 6, 7)
❑ F(x, y, z) = Σ(3, 4, 6, 7) = yz+ xz'

Figure 3.5 Map for Example 3-2; F(x, y, z) = Σ(3, 4, 6, 7) = yz

+ xz'
 Four adjacent Squares
■ Consider four adjacent squares
❑ 2, 4, and 8 squares
❑ m0+m2+m4+m6 = x'y'z'+x'yz'+xy'z'+xyz' = x'z'(y'+y) +xz'(y'+y) = x'z' + xz‘ = z'
❑ m1+m3+m5+m7 = x'y'z+x'yz+xy'z+xyz =x'z(y'+y) + xz(y'+y) =x'z + xz = z

Figure 3.3 Three-variable Map

Example 3.3
Example 3.3: simplify F(x, y, z) = Σ(0, 2, 4, 5, 6)
❑ F(x, y, z) = Σ(0, 2, 4, 5, 6) = z'+ xy'

Figure 3.6 Map for Example 3-3, F(x, y, z) = Σ(0, 2, 4, 5, 6) =

z' +xy'
 Example 3.4
■ Example 3.4: let F = A'C + A'B + AB'C + BC
a) Express it in sum of minterms.
b) Find the minimal sum of products expression.
Ans:
F(A, B, C) = Σ(1, 2, 3, 5, 7) = C + A'B

Figure 3.7 Map for Example 3.4, A'C + A'B + AB'C + BC = C +

A'B
 3.3 Four-Variable Map
■ The map
❑ 16 minterms
❑ Combinations of 2, 4, 8, and 16 adjacent squares

Figure 3.8 Four-variable

 Example 3.5
■ Example 3.5: simplify F(w, x, y, z) = Σ(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

F = y'+w'z'+xz'

Figure 3.9 Map for Example 3-5; F(w, x, y, z) = Σ(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) = y' + w' z'
+xz'
 Example 3.6
■ Example 3-6: simplify F = A′B′C′ + B′CD′ + A′B′C′D′ + AB′C′

Figure 3.9 Map for Example 3-6; A′B′C′ + B′CD′ +

A′B′C′D′ + AB′C′= B′D′ + B′C′ +A′CD′
 Prime Implicants
■ Prime Implicants
❑ All the minterms are covered.
❑ Minimize the number of terms.
❑ A prime implicant: a product term obtained by combining the maximum possible
number of adjacent squares (combining all possible maximum numbers of squares).
❑ Essential P.I.: a minterm is covered by only one prime implicant.
❑ The essential P.I. must be included.
 Prime Implicants
■ Consider F(A, B, C, D) = Σ(0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)
❑ The simplified expression may not be unique
❑ F = BD+B'D'+CD+AD = BD+B'D'+CD+AB'
= BD+B'D'+B'C+AD = BD+B'D'+B'C+AB'

Figure 3.11 Simplification Using Prime

 3.4 Five-Variable Map
■ Map for more than four variables becomes complicated
❑ Five-variable map: two four-variable map (one on the top of the other).

Figure 3.12 Five-variable Map

 Example 3.7
■ Example 3.7: simplify F = Σ(0, 2, 4, 6, 9, 13, 21, 23, 25, 29, 31)

F = A'B'E'+BD'E+ACE
3-5 Product of Sums Simplification
■ Approach #1
❑ Simplified F' in the form of sum of products
❑ Apply DeMorgan's theorem F = (F')'
❑ F': sum of products → F: product of sums
■ Approach #2: duality
❑ Combinations of maxterms (it was minterms)
❑ M0M1 = (A+B+C+D)(A+B+C+D') = (A+B+C)+(DD') = A+B+C

CD
AB 0 0 1 1
0
M 1
M 1
M 0
M
0 0 1 3 2
0
0 M4 M5 M7 M6
1 M12 M13 M15 M14
1
1
1 M8 M9 M11 M10
0
Example 3.8
Example 3.8: simplify F = Σ(0, 1, 2, 5, 8, 9, 10) into (a) sum-of-products
form, and (b) product-of-sums form:

a) F(A, B, C, D)= Σ(0, 1, 2, 5,

8, 9, 10) =
B'D'+B'C'+A'C'D
b) F' = AB+CD+BD'
» Apply DeMorgan's
theorem;
F=(A'+B')(C'+D')(B'+D)
» Or think in terms of
maxterms

Figure 3.14 Map for Example 3.8, F(A, B, C, D)=

Σ(0, 1, 2, 5, 8, 9, 10) = B'D'+B'C'+A'C'D
 Example 3.8 (cont.)
■ Gate implementation of the function of Example 3.8

Sum-of products form Product-of sums form

Figure 3.15 Gate Implementation of the Function of

Example 3.8
 Sum-of-Minterm Procedure
■ Consider the function defined in Table 3.2.
❑ In sum-of-minterm:

❑ In sum-of-maxterm:

❑ Taking the complement of F′

 3-6 Don't-Care Conditions
■ The value of a function is not specified for certain combinations of variables
❑ BCD; 1010-1111: don't care
■ The don't-care conditions can be utilized in logic minimization
❑ Can be implemented as 0 or 1
■ Example 3.9: simplify F(w, x, y, z) = Σ(1, 3, 7, 11, 15) which has the don't-
care conditions d(w, x, y, z) = Σ(0, 2, 5).
Example 3.9 (cont.)
❑ F = yz + w'x'; F = yz + w'z
❑ F = Σ(0, 1, 2, 3, 7, 11, 15) ; F = Σ(1, 3, 5, 7, 11, 15)
❑ Either expression is acceptable

Figure 3.17 Example with don't-care

Conditions
 3-7 NAND and NOR Implementation
■ NAND gate is a universal gate
❑ Can implement any digital system

Figure 3.18 Logic Operations with NAND

Gates
 NAND Gate
■ Two graphic symbols for a NAND gate

Figure 3.19 Two Graphic Symbols for

NAND Gate
 Two-level Implementation
■ Two-level logic
❑ NAND-NAND = sum of products
❑ Example: F = AB+CD
❑ F = ((AB)' (CD)' )' =AB+CD

Figure 3.20 Three ways to implement F =

 Example 3.10
■ Example 3-10: implement F(x, y, z) =

Figure 3.21 Solution to Example

 NOR Implementation
■ NOR function is the dual of NAND function.
■ The NOR gate is also universal.

Figure 3.24 Logic Operation with NOR

Two Graphic Symbols for a NOR Gate

Figure 3.25 Two Graphic Symbols for

NOR Gate
Example: F = (A + B)(C +
D)E

Figure 3.26 Implementing F = (A + B)(C +

 3-9 Exclusive-OR Function
■ Exclusive-OR (XOR)
❑ x⊕y = xy'+x'y
■ Exclusive-NOR (XNOR)
❑ (x⊕y)' = xy + x'y'
■ Some identities
❑ x⊕0 = x
❑ x⊕1 = x'
❑ x⊕x = 0
❑ x⊕x' = 1
❑ x⊕y' = (x⊕y)'
❑ x'⊕y = (x⊕y)'
■ Commutative and associative
❑ A⊕B = B⊕A
❑ (A⊕B) ⊕C = A⊕ (B⊕C) = A⊕B⊕C
 Exclusive-OR Implementations
■ Implementations
❑ (x'+y')x + (x'+y')y = xy'+x'y = x⊕y

Figure 3.32 Exclusive-OR Implementations