Digital Circuits

Design
Dr. Omar A. M. Aly
Dr. Diaaeldin Abdelrahman
[email protected]
 Chapter 3:
Gate-Level
Minimization
Dr. Omar A. M. Aly
Dr. Diaaeldin Abdelrahman
[email protected]

M. M. Mano, “Digital Design With an Introduction to the Verilog HDL,” 5th Edition, Pearson
Education, 2013.
Outline
Introduction
The Map Method
Four-Variables K-Map
Product-of-Sum Simplification
Don’t Care Conditions
NAND and NOR Implementations

Digital Circuits Design Slide 3

Circuit Optimization
Goal: To obtain the simplest implementation for a given function

Optimization requires a cost criterion to measure the simplicity of a circuit

Two distinct cost criteria we will use:
Literal cost (L)
Gate input cost (G)
Gate input cost with NOTs (GN)

Digital Circuits Design Slide 4

Cost Criteria
Literal – a variable or its complement
Literal cost – the number of literal appearances in a Boolean expression
corresponding to the logic circuit diagram

Gate input costs: the number of inputs to the gates in the implementation
corresponding exactly to the given equation or equations. (G - inverters not
counted, GN - inverters counted)

Digital Circuits Design Slide 5

 Example for Cost Criteria
 Example 1: GN = G + 2 = 9
L=5
 F=A+ BC + BC
G=L+2= 7
B
C
A F

 L (literal count) counts the AND inputs and the single

literal OR input.
 G (gate input count) adds the remaining OR gate inputs
 GN(gate input count with NOTs) adds the inverter inputs

Digital Circuits Design Slide 6

 Cost Criteria (continued)
 Example 2: A
B
 F = A B C + AB C C
L = 6 G = 8 GN = 11 F
 F = (A + C)( B + C)( A + B)
L = 6 G = 9 GN = 12
 Same function and same A
literal cost B
 But first circuit has better C
gate input count and better F
gate input count with NOTs
 Select it!

Digital Circuits Design Slide 7

Boolean Function Optimization
Minimizing the gate input (or literal) cost of a (a set of) Boolean equation(s)
reduces circuit cost.
We choose gate input cost.
Boolean Algebra and graphical techniques are tools to minimize cost criteria
values.
Some important questions:
When do we stop trying to reduce the cost?
Do we know when we have a minimum cost?
Treat optimum or near-optimum cost functions for two-level (SOP and POS)
circuits first.
Introduce a graphical technique using Karnaugh maps (K-maps, for short)
Digital Circuits Design Slide 8
Expression Simplification

Digital Circuits Design Slide 9

Karnaugh Maps (K-map)
A K-map is a collection of squares
Each square represents a minterm
The collection of squares is a graphical representation of a Boolean function
Adjacent squares differ in the value of one variable
Alternative algebraic expressions for the same function are derived by recognizing
patterns of squares
The K-map can be viewed as
A reorganized version of the truth table
A topologically-warped Venn diagram as used to visualize sets in algebra of sets

Digital Circuits Design Slide 10

Some Uses of K-Maps
Provide a means for:
Finding optimum or near optimum
• SOP and POS standard forms, and
• two-level AND/OR and OR/AND circuit implementations
for functions with small numbers of variables
Visualizing concepts related to manipulating Boolean expressions, and
Demonstrating concepts used by computer-aided design programs to simplify large
circuits

Digital Circuits Design Slide 11

Two Variable Maps
A 2-variable Karnaugh Map:
Note that minterm m0 and y=0 y=1
minterm m1 are “adjacent” and differ in the value of the m0 = m1 =
variable y x=0
x y x y
Similarly, minterm m0 and minterm m2 differ in the
x variable. x = 1 m 2 = m3 =
x y x y
Also, m1 and m3 differ in the x variable as well.
Finally, m2 and m3 differ in the value of the variable y

Digital Circuits Design Slide 12

K-Map and Truth Tables
The K-Map is just a different form of the truth table.
Example – Two variable function:
We choose a,b,c and d from the set {0,1} to implement a particular function, F(x,y).

Function Table K-Map

Input Function
Values Value y=0 y=1
(x,y) F(x,y)
00 a
x=0 a b
01 b x=1 c d
10 c
11 d
Digital Circuits Design Slide 13
K-Map Function Representation
Example: F(x,y) = x F=x y=0 y=1
x=0 0 0
x=1 1 1

For function F(x,y), the two adjacent cells containing 1’s can be combined
using the Minimization Theorem:

F (x, y ) = x y + x y = x

Digital Circuits Design Slide 14

K-Map Function Representation
Example: G(x,y) = x + y G = x+y y = 0 y = 1
x=0 0 1

x=1 1 1

For G(x,y), two pairs of adjacent cells containing 1’s can be combined using
the Minimization Theorem:

Digital Circuits Design Slide 15

Three-Variable K-Map
The minterms are arranged in a sequence similar to the Gray code
The characteristic of the Gray code is that only one-bit changes in value
from one adjacent column to the next

Digital Circuits Design Slide 16

Combining Squares
By combining squares, we reduce number of literals in a product term, reducing
the literal cost, thereby reducing the other two cost criteria
 On a 3-variable K-Map:
One square represents a minterm with three variables
Two adjacent squares represent a product term with two variables
Four “adjacent” terms represent a product term with one variable
Eight “adjacent” terms is the function of all ones (no variables) = 1.

Digital Circuits Design Slide 17

Three-Variable Maps
Reduced literal product terms for SOP standard forms correspond to
rectangles on K-maps containing cell counts that are powers of 2.

Rectangles of 2 cells represent 2 adjacent minterms; of 4 cells represent 4

minterms that form a “pairwise adjacent” ring.

Rectangles can contain non-adjacent cells as illustrated by the “pairwise

adjacent” ring above.

Digital Circuits Design Slide 18

Three-Variable Maps
Topological warps of 3-variable K-maps that show all adjacencies:

yz=00 yz=01 yz=11 yz=10

x=0 m0 m1 m3 m2
x=1 m4 m5 m7 m6

Digital Circuits Design Slide 19

Combining Squares
Example Shapes of 2-cell Rectangles:

Read off the product terms for the rectangles shown

Digital Circuits Design Slide 20

Combining Squares
Example Shapes of 4-cell Rectangles:

Read off the product terms for the rectangles shown

Digital Circuits Design Slide 21

Three-Variable K-Map
Simplification Process
Two adjacent term
om0+m1=x’y’, m1+m3=x’z, m3+m2=x’y, m0 + m2 = x’z’
om4+m5=xy’ , m5+m7=xz, m7+m6=xy , m4 + m6 = xz’
om0+m4=y’z’, m1+m5=y’z, m3+m7=yz , m2 + m6 = yz’
Four adjacent Term
om0 + m1 + m3 + m2 = x’ , m 4 + m5 + m7 + m6 = x
om0 + m1 + m4 + m5 = y’ , m 3 + m2 + m7 + m6 = y
om0 + m4 + m2 + m6 = z’ , m 1 + m3 + m5 + m7 = z
Digital Circuits Design Slide 22
Three-Variable K-Map
Example: Simplify the Boolean function: F(x,y,z) = ∑(2,3,4,5)
Solution:
om3+m2=x’y
om4+m5=xy’
oTherefore, F = x’y + xy’

Example: Simplify the Boolean function: F(x,y,z) = ∑(3, 4, 6, 7)

Solution:
om3+m7=yz
om4+m6=xz’
oTherefore, F = yz + xz’
Digital Circuits Design Slide 23
Three-Variable K-Map
Example: Simplify the Boolean function F = A’C + A’B + AB’C + BC

Solution:
1) Express this function as a sum of minterms.
2) Find the minimal sum-of-products expression

Digital Circuits Design Slide 24

Three-Variable Map Simplification
Use a K-map to find an optimum SOP equation for
F(X, Y, Z) = m(0,1,2,4,6,7)

Digital Circuits Design Slide 25

Four Variable Maps
Map and location of minterms:

Digital Circuits Design

Four Variable Terms
Four variable maps can have rectangles corresponding to:
A single 1 = 4 variables, (i.e., Minterm)
Two 1s = 3 variables,
Four 1s = 2 variables
Eight 1s = 1 variable,
Sixteen 1s = zero variables (i.e. Constant "1")

Digital Circuits Design Slide 27

Four-Variable Maps
Example Shapes of Rectangles:

Digital Circuits Design Slide 28

Four-Variable Maps
Example Shapes of Rectangles:

Digital Circuits Design Slide 29

FOUR-VARIABLE K-MAP
Example: Simplify the Boolean function
F (w, x, y, z) = ∑(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)
Solution:

Digital Circuits Design Slide 30

FOUR-VARIABLE K-MAP
Example: Simplify the Boolean function F = A’B’C’ + B’CD’+ A’BCD’ + AB’C’

Solution:

Digital Circuits Design Slide 31

Four-Variable Map Simplification
 Simplify
1)

2)

Digital Circuits Design Slide 32

Systematic Simplification
A Prime Implicant is a product term obtained by combining the maximum
possible number of adjacent squares in the map into a rectangle with the
number of squares a power of 2.
A prime implicant is called an Essential Prime Implicant if it is the only
prime implicant that covers (includes) one or more minterms.
Prime Implicants and Essential Prime Implicants can be determined by
inspection of a K-Map.
A set of prime implicants "covers all minterms" if, for each minterm of the
function, at least one prime implicant in the set of prime implicants includes
the minterm.

Digital Circuits Design Slide 33

Example of Prime Implicants
 Find All prim implicants
CD ESSENTIAL Prime Implicants
C C
BD BD
1 1 1 1 1 1

BD 1 1 BD 1 1
B B
1 1 1 1
A A
1 1 1 1 1 1 1 1
AB
D D
AD Minterms covered by single prime implicant
BC
Digital Circuits Design Slide 34
Prime Implicant Practice
Find all prime implicants for:

1)

2) G(A, B, C, D) = m(0,2,3,4,7,12,13,14,15)
Hint: There are seven prime implicants!

Digital Circuits Design Slide 35

Don't Cares in K-Maps
Sometimes a function table or map contains entries for which it is known:
the input values for the minterm will never occur, or
The output value for the minterm is not used

In these cases, the output value need not be defined

Instead, the output value is defined as a “don't care”
By placing “don't cares” ( an “x” entry) in the function table or map, the
cost of the logic circuit may be lowered.

Digital Circuits Design Slide 36

Don't Cares in K-Maps
Ultimately, each “x” entry may take on either a 0 or 1 value in resulting
solutions
For example, an “x” may take on value “0” in an SOP solution and value “1”
in a POS solution, or vice-versa.
Any minterm with value “x” need not be covered by a prime implicant.

Example 1: A logic function having the binary codes for the BCD digits as
its inputs. Only the codes for 0 through 9 are used. The six codes, 1010
through 1111 never occur, so the output values for these codes are “x” to
represent “don’t cares.”

Digital Circuits Design Slide 37

DON’T-CARE CONDITIONS
Example: Simplify the Boolean function 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)

Solution:

Digital Circuits Design Slide 38

Example: BCD “5 or More”
The map below gives a function F1(w,x,y,z) which is defined as "5 or more"
over BCD inputs. With the don't cares used for the 6 non-BCD
combinations:

Digital Circuits Design Slide 39

PRODUCT-OF-SUMS SIMPLIFICATION
The complement of a function is represented in the map by the squares not
marked by 1’s

If we mark the empty squares by 0’s and combine them into valid adjacent
squares, we obtain a simplified sum-of-products expression of the
complement of the function (i.e., of F’ )

The complement of F’ gives us back the function F in product-of-sums form

(a consequence of DeMorgan’s theorem)

Because of the generalized DeMorgan’s theorem, the function so obtained

is automatically in product-of-sums form

Digital Circuits Design Slide 40

PRODUCT-OF-SUMS SIMPLIFICATION
Example: Simplify the following Boolean function into (a) sum-of-products
form and (b) product-of-sums form:
F (A, B, C, D) = ∑(0, 1, 2, 5, 8, 9, 10)

Solution:

Digital Circuits Design Slide 41

Product of Sums Example
Find the optimum POS solution:
F(A, B, C, D) = m(3,9,11,12,13,14,15) +
d (1,4,6)
Hint: Use and complement it to get the result.

Digital Circuits Design Slide 42

Optimization Algorithm
Find all prime implicants.
Include all essential prime implicants in the solution
Select a minimum cost set of non-essential prime implicants to cover all
minterms not yet covered:
Obtaining an optimum solution: See Reading Supplement - More on Optimization
Obtaining a good simplified solution: Use the Selection Rule

Digital Circuits Design Slide 43

Prime Implicant Selection Rule
Minimize the overlap among prime implicants as much as possible. In
particular, in the final solution, make sure that each prime implicant
selected includes at least one minterm not included in any other prime
implicant selected.

Digital Circuits Design Slide 44

Selection Rule Example

Selected Essential

1 1 1 1

1 1 1 1 1 1 1 1
1 1
1 1 1 1

D
Minterms covered by essential prime implicants

Digital Circuits Design Slide 45

Selection Rule Example with Don't Cares
Simplify F(A, B, C, D) given on the K-map.
Selected Essential
C C

1 x 1 x

1 x x 1 1 x x 1
B B
x x
A A
1 1 x 1 1 x

D D
Minterms covered by essential prime implicants

Digital Circuits Design Slide 46

Prime Implicants
Example: Consider the following four-variable Boolean function
F(A, B, C, D) = ∑(0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)

Digital Circuits Design Slide 47

NAND AND NOR IMPLEMENTATION
Digital circuits are frequently constructed with NAND or NOR gates rather
than with AND and OR gates

NAND and NOR gates are easier to fabricate with electronic components
and are the basic gates used in all IC digital logic families

Because of the prominence of NAND and NOR gates in the design of digital
circuits, rules and procedures have been developed for the conversion from
Boolean functions given in terms of AND, OR, and NOT into equivalent
NAND and NOR logic diagrams

Digital Circuits Design Slide 48

Universal NAND Circuits
Logic operations with NAND gates:

Two graphic symbols for a three-input NAND gate

Digital Circuits Design Slide 49

Two-Level Implementation
Three ways to implement F = AB + CD

Digital Circuits Design Slide 50

NAND AND NOR IMPLEMENTATION
Example: Implement the following Boolean function with NAND gates
F (x, y, z) = ∑(1, 2, 3, 4, 5, 7)

Digital Circuits Design Slide 51

Multilevel NAND Circuits
The general procedure for converting a multilevel AND–OR diagram into an
all-NAND diagram using mixed notation is as follows:

1) Convert all AND gates to NAND gates with AND-invert graphic symbols
2) Convert all OR gates to NAND gates with invert-OR graphic symbols
3) Check all the bubbles in the diagram. For every bubble that is not
compensated by another small circle along the same line, insert an
inverter (a one-input NAND gate or complement the input literal)

Digital Circuits Design Slide 52

Multilevel NAND Circuits
 Example: Implement the following Boolean function with NAND gates

Digital Circuits Design Slide 53

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

Digital Circuits Design Slide 54

NOR Implementation
Two Graphic Symbols for a NOR Gate

Digital Circuits Design Slide 55

NOR Implementation
Example: Implement the following Boolean function with NOR gates
F = (A + B)(C + D)E

Digital Circuits Design Slide 56

NOR Implementation
Example: Implement the following Boolean function with NOR gates
F = (AB +AB)(C + D)

Digital Circuits Design Slide 57

 Thanks and Feedback

Electronic Devices and Circuits Slide 58