Transcript EE208 Chapter 3 - Gate Level Minimization

1
EE 208 – Logic Design
Chapter 3
Gate Level Minimization
Sohaib Majzoub
Circuit Optimization
2
• Goal: To obtain the simplest implementation for a
given function
• Optimization requires a cost criterion to measure the
simplicity of a circuit
• Distinct cost criteria we will use:
– Minimum number of gates
– Minimum number of inputs per gate
• Optimization is a more formal approach to
simplification that is performed using a specific
procedure or algorithm
• Because: less gates => cheaper, less power, lower
delay
Gate Delay
3
• In actual physical gates, if one or more input
changes causes the output to change, the output
change does not occur instantaneously.
• The delay between an input change(s) and the
resulting output change is the gate delay denoted by
tG:
1
Input
0
1
Output
0
0
tG
tG
0.5
1
tG = 0.3 ns
1.5
Time (ns)
Terminology
• Fan-In: refers to the number of inputs a gate has.
• The higher number of inputs the more transistors
needed to design the gate.
• As Fan-In increase => bigger gates => more area,
higher power consumption, longer delay.
• Fan-Out: refers to the number of gate that can be
driven by a gate (number of gates connect to an
output), same cost criteria as Fan-In
• A gate can drive limited number of inputs, due to
limited driving power (supply current) by gate.
• Increase Fan-Out => Larger/more transistors are
needed => larger area, power, and lower speed.
4
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
5
Two Variable Maps
• A 2-variable Karnaugh Map:
y=0 y=1
– Note that minterm m0 and
m0 = m1 =
minterm m1 are “adjacent”
x=0
x’ y’
x’ y
and differ in the value of the
x = 1 m 2 = m3 =
variable y
x y
x y’
– Similarly, minterm m0 and
minterm m2 differ in the x variable.
– Also, m1 and m3 differ in the x variable as well.
– Finally, m2 and m3 differ in the value of the
variable y
6
K-Map and Truth Tables
7
• 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).
K-Map
Input
Values
(x,y)
Function
Value
F(x,y)
00
01
10
11
a
b
c
d
x=0
x=1
y=0
y=1
a
c
b
d
K-Map Function Representation
• Example: F(x,y) = x
•
F=x
8
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
Duplicate and Combine
• Example: G(x,y) = x + y
9
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:
G(x,y) = (x.y’+x.y)+(x.y+x’.y) = x + y
Duplicate x y
10
Three Variable Maps
• A three-variable K-map:
yz=00 yz=01 yz=11 yz=10
x=0
m0
m1
m3
m2
x=1
m4
m5
m7
m6
• Where each minterm corresponds to the product
terms:
yz=00 yz=01 yz=11 yz=10
x=0
x’y’z’
x’ y’ z
x’ y z
x’ y z’
x=1
x y’ z’
x y’ z
x y z
x y z’
• Note that if the binary value for an index differs in
one bit position, the minterms are adjacent on the
K-Map
11
Alternative Map Labeling
• Map use largely involves:
– Entering values into the map, and
– Reading off product terms from the
map.
• Alternate labeling are useful:
y
x
x
0
4
y
1
3
7
5
z
z
x
2
6
z
y
yz
00 01 11 10
0 0
x 1
4
1
3
2
5
7
6
z
Example Functions
• By convention, we represent the minterms of F
by a "1" in the map and leave the minterms of
F’ blank
y
• Example:
0
3
2
1
1 1
F(x, y, z)  m(2,3,4,5)
x 4 1 51 7 6
• Example:
z
G(a, b, c)  m(3,4,6,7)
y
• Learn the locations of the 8
0
3
2
1
1
indices based on the variable
4
7
6
5
x
1
1
1
order shown (x, most significant
z
and z, least significant) on the
map boundaries
12
Four Variable Maps
• Example:
F(A,B,C,D)  m(4,8,15)

1
1
1
13
Four Variable Maps
• Example:
F(A,B,C,D)  m(3,4,7,8)

1
1
1
1
14

Four Variable Maps
• Example:
F(A,B,C,D)  m(0,3,7,8)
1
1
1
1
15
Four Variable Maps
• Example:
F(A,B,C,D)  m(0,3,4,7,8,9,13)
1
1
1
1
1
1
1
16
Four Variable Maps
• Example:
F(A,B,C,D)  m(0,3,4,5,6,7,8,9,13)
1
1
1
1
1
1
1
1
1
17
Four Variable Maps
• Example:
F(A,B,C,D)  m(0,3,4,5,7,8,9,13,15)
1
1
1
1
1
1
1
1
1
18
Four Variable Maps
• Example:
F(A,B,C,D)  m(3,4,5,6,7,9,12,13,14,15)
1
1
1
1
1
1
1
1
1
1
19

Four Variable Maps
• Example:
F(A,B,C,D)  m(0,1,2,3,5,7,8,9,10,11,13,15)
1
1
1
1
1
1
1
1
1
1
1
1
20
Four Variable Maps
• Example:
F(A,B,C,D)  m(0,2,5,7,8,10,13,15)
1
1
1
1
1
1
1
1
21
Summary
• 2i 1-cells should be grouped => product term
• Case: 3 variable K-Map
20 = 1 : 1-cell
3 variable product term
21 = 2 : 1-cells 2 variable product term
22 = 4 : 1-cells 1 variable product term
23 = 8 : 1-cells φ variable product term (F=1)
• Case: 4 variable K-Map
20 = 1 : 1-cell
4 variable product term
21 = 2 : 1-cells 3 variable product term
22 = 4 : 1-cells 2 variable product term
23 = 8 : 1-cells 1 variable product term
24 =16: 1-cells φ variable product term (F=1)
22
Prime Implicant Theorem
• 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
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.
23
Prime Implicant Example
• Example:
F(A,B,C,D)  m(0,3,4,5,6,7,8,9,13)
1
1
1
1
1
1
1
1
1
24
Prime Implicant Example
• Example:
F(A, B, C, D)  m(4,5,6,7,13,15)
1
1
1
1
1
1
25
Examples
F(A,B,C,D)  m(0,2,3,6,7,8,9,12)
26
Examples
27
F(A,B,C,D)  m(0,1,4,5,8,11,12,13,15)
Examples
F(A,B,C,D)  m(6,7,8,9,13,15)
28
Examples
F(A,B,C,D)  m(4,5,6,13,14,15)
29
Examples
30
F(A,B,C,D)  m(1,5,7,8,9,12,13,14,15)
Examples
31
F(A,B,C,D)  m(1,3,4,5,6,7,11,12,14,15)
Don’t Cares in K-Maps
32
• 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.
Don’t Cares, Example
33
• A logic function having the binary codes for
the BCD digits as its inputs.
• This function produces 1 for even BCD digit
and 0 for odd BCD digit.
• 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.”
Don’t Cares, Example
ABCD
F
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
1
1
1
1
1
F = A’D’+B’C’D’
34
Don’t Cares, Example
ABCD
F
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1
0
1
0
1
0
1
0
1
0
x
x
x
x
x
x
1
1
1
1
x
1
F = D’
x
x
x
x
x
35
Example
• Example: design a NAND-NAND logic
F(A,B,C,D)  m(0,3,4,5,7,8,9,13,15) +d(1,6,12,14)
1
x
1
1
1
1
x
x
1
1
x
1
1
36
Examples
F(A,B,C,D)  m(0,1,3,5,14) +d(8,15)
F(A,B,C,D)
F(A,B,C,D)
F(A,B,C,D)
F(A,B,C,D)




m(0,1,2,8,11) +d(3,9,15)
m(4,6,7,9,13) +d(5,12)
m(4,5,9,13,15) +d(0,1,7,11,12)
m(1,5,12,13,14,15) +d(7,9)
37
Example
• Example: design a NOR-NOR logic
F(A,B,C,D)   M(0,4,6,7,13,15).D(1,5,8,10,12)
0
x
0
x
0
x
0
0
x
0
x
38
Minimization Using Tabular Method
• Tabular Method is useful when functions have large
number of variables, e.g. 6 or 5 variables.
• Can be programmed easily (write a C program to
implement TM?)
• The method reduces a SOP to a set of prime
implicants from which variables are eliminated as
much as possible.
• Redundant PI are removed.
• Like K-Maps uses A+A’=1
• A variable is denoted as (1), A’ variable is denoted
(0), eliminated variable is denoted (-).
39
Tabular Method Example
• Example:
F(A,B,C,D)  m(0,2)
• Then the variables can be written as:
A’B’C’D’+A’B’CD’ = A’B’(C+C’)D’ = A’B’D’
which
 is equivalent to:
0000
0010
00–0 which is A’B’D’
40
Tabular Method Example
• Example: F(A,B,C,D)  m(0,2,4,6,8)
• Then the variables can be written as:
0000, 0010,0100,0110,1000
Sort those
with one flip:

0000 and 0010,0100,1000 => 00–0, 0–00, –000
0010 and 0110 => 0–10
0100 and 0110 => 01–0
0110 and 0100,0010 => 01–0, 0–10
1000 and 0000 => –000
41
Tabular Method Example
• Sort the result again
00–0, 0–00, –000, 0–10, 01–0,
then:
–000
00–0, and 01–0, => 0––0
0–00, and 0–10, => 0––0
The result is: –000, and 0––0 or B’C’D’ and A’D’
42
Examples
• Solve using Tabular Method:
F(A, B, C, D)  m(0,1,4,5,7,8,9,12,14,15)
F(A, B, C, D)  m(1,5,6,7,11,12,13,15)
F(A, B, C, D)  m(0,2,3,4,5,7,8,10,11,12,13,15)
F(A, B, C, D, E)  m(5,7,13,15,16,20,25,27,29,31)
43