Transcript EECS 265: Digital Systems - UIC

EECS 465: Digital Systems
Lecture Notes # 2
Two-Level Minimization Using Karnaugh Maps
SHANTANU DUTT
Department of Electrical & Computer Engineering
University of Illinois, Chicago
Phone: (312) 355-1314: e-mail: [email protected]
URL: http://www.ece.uic.edu/~dutt
Concepts in 2-Level Minimization
2
• Defn: An implicant g of a function is a product term (e.g., g=xyz) s.t.
when g=1  f=1
• Defn: A minterm is an implicant whose product term representation
consists of all n variables of an n-var. function (each in either compl.or
uncompl. form)
• Defn: Let g, and h be 2 implicants of a function f. g is said to cover h
if h=1  g=1 (e.g., g = xz, h = xyz)
• Defn: Let G = {g1, .., gk} be a set of implicants of func f, and let h be
another implicant of f. Then G is covers h if h=1  g1+ .. + gk =1
(generalized covering).
3
• Defn: An SOP or POS expression is also called a 2-level
expression
• Defn: A 2-level AND-OR (OR-AND) gate realization of an SOP
(POS) expression is one in which all product terms (OR terms in
POS) in the SOP (POS) expression are implementedby multiple
input AND (OR) gates & the ORing (ANDing) of the product
(OR) terms is realized by a multiple input OR (AND) gate.
AB + BC + ACD
A
B
B
C
A
C
D
f1
Level 2
Level 1
4
An OR-AND 2-level circuit implementing a POS expression
(B + C)(A + D)(C + D)
B
C
A
D
C
D
Level 1
Level 2
f2
A multi-level circuit implementing a multi-level expression
E.g.
A
B
f1 = AB + BC + ACD
--- 2-level. (SOP)
f2 = ( B+C )( A+D )( C+D )
--- 2-level (POS)
f3 =AB + AC( B+D )
--- not SOP or POS
level 1 I/Ps
--- not 2-level
--- 3 level ( can be realized
directly by 3 levels of gates)
A
f3
C
B
D
level 0
I/Ps
level 2
I/Ps
level 1
gates
level 2
gates
level 3
gate
3
6
• Defn. A gate in a logic circuit is a level-1 gate if all its inputs are
primary inputs (i.e., literals, A, A, B, B, etc.)
A gate is a level-i gate g, i > 1, if the highest-level gate whose
output feeds g is a level-(i-1) gate.
• NOTE: If a given expr. is not 2-level, we can convert it to a
2-level one using the distributive law.
• The goal of 2-level minimization is to minimize the number of
literals (a literal is a var. in complemented or uncompl. form)in a
2-level logic expr.
• This approx. reduces the total # of inputs over all level-1 gates
(AND gates in an SOP expr. , OR gates in a POS expr.) in the
circuit in a 2-level gate realization.
• Cost of a circuit = total # of gate inputs across all its gates (=
approx. (number of MOS transistors)/2)
• Cost of a 2-level expr. f = cost of a 2-level circuit implementing f
7
E.g. f = ABC + ABC + ABC (non-minimized 9 literals)
A
B
(12 gate I/Ps)
C
= Circuit complexity
A
f
B
C
A
B
C
f = AB + AC (minimized 4 literals)
A
f
B
(6 gate I/Ps)
= Circuit complexity
A
C
Note: Minimizing # of literals + # of product terms  minimizing total # of gate inputs
in a 2-level impl.  approx. min. total # of gate i/ps of a multi-level impl. (reqd. when
gates of certain sizes reqd. by the minimized expression is not available)
8
Multilevel Minimization Example
f = x1x2x3 + x2x3x4 + x1x5 + x4x5
(2-level minimized)
Cost = 14 (# of gate i/ps in a 2-level impl.)
Applying the distributive law (factoring)
f = x2x3(x1 + x4) + x5(x1 + x4)
= (x2x3 + x5)(x1 + x4) -- Multilevel expr. See gate impl. below
•
•
•
Cost = 8 (# of gate i/ps).
Can increase delay though due to more levels of gates & more
interconnects that the critical path has to go through
• Critical path goes through 3 2-i/p
Simple gate delay model: delay prop. to # of inputs
gates (6 units of delay) and 2
x2
x3
x5
x1
x4
f
Multilevel
circuit
•
•
interconn. delays (not counting i/p
and o/p interconnects). The
critical path in a 2-level impl. of
the above SOP expr. will go
through a total of 7 gate units of
delay but only 1 interconnect
delay.
An interconnect’s delay is
generally much more than a single
gate i/p delay
So sometimes cost decrease via
multi-level min. can cause delay
increase (but not always).
9
Defn. Two implicants (or product terms) of a function f are said to
be logically adjacent if they have the same literals
except in one variable xi which occurs in uncomplemented form
(xi) in one implicant and in complemented form (xi) in the
other. The 2 implicants are said to differ in xi.
E.g.
ABC, ABC
ABD, ABC
(adjacent implicants, differ in B)
(not adjacent)
Adjacent implicants can be combined into one implicant
by the combining theorem (ABC + ABC = AC)
AB
C
00
01
11
10
1
1
AC’
A’B’C’
0
1
AB’C
ABC
1 A’B’C 1
1
A’B’
1
AC
A
10
Karnaugh Maps
2-variable TT outputs
Binary
place-value
ordering
(Binary
ordering)
A
0
0
1
1
B
0
1
0
1
Z1
0
1
0
1
Z2
0
1
1
0
Physically adjacent
but not logically
adjacent.
logically adjacent but not physically adjacent
AB + AB
B
Another ordering of inputs ( Gray-code ordering)
A B
Z1
0
0
0
0
1
1
Z1 = B
Physically as well as
1
1
1
logically adjacent.
1
0
0
11
n-variable Gray-code ordering
Defn. Gi = i-bit Gray-code ordering
rev(Gi) = reverse order of Gi
G1 = 0
Base.
1
G2 = 0 G1
=
1 rev(G1)
0
0
1
1
G 3 = 0 G2
1 rev(G2)
Convert to a 2-dimensional
Gray-code ordered TT
C
y
AB
00
x
01
11
10
1
•
0
1
1
0
=
A
0
0
0
0
1
1
1
1
B
0
0
1
1
1
1
0
0
C
0
1
1
0
0
1
1
0
•
0
1
110
Gn = 0 Gn-1
1 rev(Gn-1)
1
001
Throw away variable (A)
changing across the 2 squares.
We thus obtain BC.
Example ( 3-var. K-Map)
Function f:
C
AB
00
01
B’C’
11
0
1
1
1
1
1
A’B’
12
Gray code ordering
AC’
10
1
Consensus = BC
f = AB + AB + AC + BC
AB
Note: 1) that the consensus theorem is an example of generalized covering discussed earlier.
2) AC’ is also a consensus, this time of AB and B’C’. Can’t discard both simultaneously!
Need to apply gen. covering (incl. consensus) one at a time.
Defn. A Prime Implicant (PI) of a function f is an implicant of f that
is not covered by any other implicant of f.
Defn. An Essential PI is a PI that covers/includes at least one minterm
that is not covered by any other PI.
In the above K-map,
four PIs AB, BC, AC, AB formed. Not all these PIs are needed in the
expression. Only a minimum set that covers all minterms is needed.
In the above example, AB & AB are essential PIs. These will need to be
present in any SOP expr. of the function. To form a minimal set, the PI
BC can be used. Thus f = AB + AB + BC is a minimized expression.
13
Larger than 2-minterm PIs can also exist:
AB
E.g., C
00
01
11
10
AB
C
0
1
1
0
1
1
1
1
AB
B
AB
00
1
01
11
1
1
10
1
C
B
• 2-minterm implicants (AB, AB in the 1st example above) can
be merged if they are logically adjacent to form a 4-minterm
implicant and so on.
14
• When an implicant can not be “grown” any further, then it is a PI.
Defn. In a K-map, 2 implicants can be logically adjacent if they
are symmetric,
i.e., if : (1) They are disjoint (no common minterms).
(2) They cover the same # of minterms.
(3) Each minterm in one implicant is adjacent to a
unique minterm in the other implicant.
AB
More Examples:
Both PIs
C
00
01
11
10
(A, BC)
AB
0
01
11
10
1
1
Redrawn
C 00
are
1
1
1
0
essential.
1
1
1
•
1
1
1
1
Not symmetric
Symmetric ( logically adjacent)
2-minterm implicants : Can be “merged” to form
a 4-minterm implicant, which will be a PI.
Thus, f = A + BC
is minimized.
15
4-variable K-Map:
Gray code ordering
AB
Gray code ordering
C
D
00
01
11
10
10
•
00
01
11
•
16
Example:
f = AC + D
AB
CD
00
01
11
10
00
1
1
1
1
1
1
1
1
01
Instead of starting with 2-minterm
implicants & growing them, you
can form larger implicants directly
by grouping power of 2 (2, 4, 8,
AC etc.) # of minterms so as to form
a rectangle or square ( a convex
region).
Convex
11
10
1
1
D
Concave
AB
CD
00
01
00
1
1
01
1
1
Valid
11
groupings
1
1
10
1
11
10
Invalid grouping
(region formed is concave)
1
f = AB + AC + BCD
17
Another Example:
TT:
A
0
0
0
0
0
0
0
Binary
0
order
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Z
1
0
1
1
0
1
1
1
1
0
1
1
0
0
1
1
AB
CD
00
00
10
11
1
10
BD
1
ABD
01
11
01
1
1
1
1
1
1
1
1
1
f = C + BD + ABD
C
18
Don’t Cares in K-Maps
• Many times certain input combinations are invalid for a function
(E.g. BCD to 7-segment display functions; see pp. 212-214 in
Katz text )
• For such combinations, we do not care what the output is, and
we put an ‘x’ in the o/p column for the TT
AB
00
01
11
10
CD
A B C f
0 0 0 1
0
x
x
1
0
0 0 1 0 f = BC + AB
0 1 0 1 by considering all
1
0
1
1
0
0 1 1 x x’s as 0s
1 0 0 0
f=B
The x’s can, however, be profitably
1 0 1 1
used to make larger PIs & thus
1 1 0 x by selectively
further simplify the function.
considering the 010
1 1 1 x cell’s x as 1
19
• In a K-map, the ‘x’s can be profitably used to form larger
implicants (which have fewer literals)
• However, when we need to form a minimal PI cover, we need to
worry only about covering the minterms ( the 1s), and not the Xs.
• Thus as far as x’s are concerned, we can have the cake and eat it too!
Example:
CD
00
00
0
LSBs 01
1
11
10
 m(1,3,5,7,9) +  d(2,6,12,13)
MSBs
AB
AD
f(A,B,C,D) =
1
3 1
2
x
01
11
10
4
12 x
8
5 1
13 x
9
7 1
15
11
6 x
14
1
CD
10
AC
If inputs 2,6 occur o/p = 1.
f = CD + AD
or CD + AC
A
0
0
0
0
B
0
0
0
0
C
0
0
1
1
D
0
1
0
1
•
•
• 2,6 occur
If input comb.
o/p is 0.
Which to use for lower dynamic power (consumed on a 0  1 transition at the o/p)?
20
STEPS IN K-MAP MINIMIZATION (sop EXPR.)
STEP1: Form all PIs by including the Xs with the 1s to form larger
PIs. (Do not form PIs covering only Xs !)
STEP2: Identify all essential PIs by visiting each minterm (1s) &
checking if it is covered by only one PI. If so, then that
PI is an essential PI.
STEP3: Identify all 1s not covered by essential PIs. Select a minimalcost set S of PIs to cover them. This requires some trial-and error (in
fact, this is a hard computational problem).
STEP4: Minimal SOP Expr. for function f:
f =  essential PIs +
 Pi
Pi  S
PI Pi is in set S
21
Minimal POS Expr. from a K-Map :
METHOD 1: Obtain minimal SOP expression for the complement
function f, and complement this SOP expression to get a minimal
POS expr. for f (using De-Morgan’s Law)
Big M notation
Example:
F (A,B,C,D) =
F
0
0
01
Xs of F
0s of F
AB
CD
00
 M(0,2,4,8,10,11,14,15) •  D(6,12,13)
0
4
1
F
AB
CD
x
0
12
8
13 x
9
1
1
5
11
3
1
7
1
15
0
10
2
0
6
x
14
0
Complement
00
1
01
11
0
11
10
0
10
00
01
11
10
1
1
x
1
0
0
0
0
x
1
0
1
1
x
1
1
F =D + AC F = D + AC = D(A +C)
D
AC
Example: (Method2: Direct Method)
AB
CD
00
D
01
11
10
00
0
0
x
0
01
1
1
x
1
11
1
1
0
0
10
0
x
0
0
(OR terms)
Prime Implicate
( Groups of 0s that cannot
be grown any further)
Both D and A + C are
Essential Prime Implicates.
(A + C)
F = D( A + C )
( Product of Prime Implicates )
22
23
METHOD2 : Direct Method :
(1) Obtain all prime implicates (PTs) (largest groups of 0s & Xs
iˆ
of size 2 , i  0, forming a convex region, that can not be “grown”
any further).
(2) Identify all essential PTs (those that cover at least one 0 not
covered by any other PT).
(3) Choose a minimal set T of PTs to cover the 0s not covered by
the set of essential PTs.
(4) The expression for a PT is an OR term obtained by discarding
all changing variables, & keeping variables complemented if they
are constant at 1 or uncomplemented if they are constant at 0 &
taking the OR (sum) of these literals.
(5) Minimal POS Expr.:
f=
 (essential PTs) • q 
q
 T i
i
5-variable K-map: f(A,B,C,D,E): Juxtapose two 4-var. K-submaps 24
one for the MSB A=0 and the other for A=1:
BC
DE
BC
00
01
11
10
DE
00
01
11
10
00
0
4
12
8
00
16
20
28
24
01
1
5
13
9
01
17
21
29
25
11
3
7
15
11
11
19
23
31
27
10
2
6
14
10
10
18
22
30
26
A=0
Example:
BC
DE
00
01
11
A=1
4-var. K-submap
4-var. K-submap
Adjacencies of a square: Adjacent squares of the 4-var. K-submap
plus the “corresponding” or “mirror” square in the other 4-var.
K-submap.
BC
00
01
11
10
0 1 4
12 1
1
13 1 9
8
DE
00
01
5
11
3 1 7 1 15 x 11
00
2
6
14 x 10
A=0
11
10
16
20
28 x 24
17
21
29 1
25
19 x 23 1 31 x 27
10
10
01
18
22 1 30 1 26
A=1
25
6-variable K-map: f(A,B,C,D,E,F)--Juxtapose two 5-var. K-submaps
one for the MSB A=0 and other for A=1
CD
EF
CD
00
01
11
10
EF
00
01
11
10
00
0
4
12
8
00
16
20
28
24
01
5-var.
A=0
K-submap
1
5
13
9
01
17
21
29
25
11
3
7
15
11
11
19
23
31
27
10
2
6
14
10
10
18
22
30
26
B=0
CD
EF
00
01
B=1
11
10
00
32
36
44
40
5-var.
01
K-submap A=1
33
37
45
41
11
35
39
47
43
10
34
38
46
B=0
42
CD
EF 00
01
11
10
00
48
52
60
56
01
49
53
61
57
11
51
55
63
59
50
54
62
58
10
B=1
Adjacencies of a square: Adjacent squares of the 5-var.
K-submap plus the “corresponding” or “mirror” square
in the other 5-var. K-submap.
26
6-variable K-map: f(A,B,C,D,E,F,)---Example:
CD
EF
CD
00
01
11
10
EF
00
01
11
10
00
0
4
12
8
00
16
20
28
24
01
1
5
13
9
01
17
21
29
25
11
3
7
15
11
11
19
23
31
27
10
2
6
14
10
10
18
22
30
26
A=0
B=0
CD
EF
00
01
B=1
11
10
00
32
36
44
40
01
33
37
45
41
35
39
47
43
A=1
11
10
34
38
46
B=0
42
CD
EF 00
01
11
10
00
48
52
60
56
01
49
53
61
57
11
51
55
63
59
50
54
62
58
10
B=1
f = A’BC’ + BC’D + B’CD’
AB
CD
00
01
00
1
01
1
11
10
1
11
10
1
f = (C’+D’)(B’+C’)(C+B)(A’+C+D)
1
f = A’BC’ + BC’D + A’CD’
AB
CD
00
01
00
1
01
1
11
10
1
11
10
1
1
f = (C’+D’)(A’+B)(A’+C’)(C+B)(A’+D)
f = BC’ + A’CD’ + BCD’
AB
01
11
00
1
1
01
1
1
CD
00
11
10
1
1
1
f = (C’+D’)(A’+B)(C+B)
10