Chapter 2
Algebraic Methods for the Analysis and
Synthesis of Logic Circuits
Chapter 2
1
Fundamentals of Boolean Algebra (1)
•
•
•
•
•
•
•
•
Basic Postulates
Postulate 1 (Definition): A Boolean algebra is a closed algebraic system
containing a set K of two or more elements and the two operators  and +.
Postulate 2 (Existence of 1 and 0 element):
(a) a + 0 = a (identity for +),
(b) a 1 = a (identity for )
Postulate 3 (Commutativity):
(a) a + b = b + a,
(b) a b = b a
Postulate 4 (Associativity):
(a) a + (b + c) = (a + b) + c
(b) a (bc) = (ab) c
Postulate 5 (Distributivity):
(a) a + (bc) = (a + b) (a + c)
(b) a (b + c) = ab + ac
Postulate 6 (Existence of complement):
(a) a  a  1
(b) a  a  0
Normally is omitted.
Chapter 2
2
Fundamentals of Boolean Algebra (2)
•
Fundamental Theorems of Boolean Algebra
•
Theorem 1 (Idempotency):
(a) a + a = a
Theorem 2 (Null element):
(a) a + 1 = 1
Theorem 3 (Involution)
•
•
(b) aa = a
(b) a0 = 0
a  a
•
Properties of 0 and 1 elements (Table 2.1):
OR
a+0=0
a+1=1
Chapter 2
AND
a0 = 0
a1 = a
Complement
0' = 1
1' = 0
3
Fundamentals of Boolean Algebra (3)
•
•
•
•
Theorem 4 (Absorption)
(a) a + ab = a
(b) a(a + b) = a
Examples:
– (X + Y) + (X + Y)Z = X + Y
– AB'(AB' + B'C) = AB'
[T4(a)]
[T4(b)]
Theorem 5
(a) a + a'b = a + b
(b) a(a' + b) = ab
Examples:
– B + AB'C'D = B + AC'D
– (X + Y)((X + Y)' + Z) = (X + Y)Z
Chapter 2
[T5(a)]
[T5(b)]
4
Fundamentals of Boolean Algebra (4)
•
•
Theorem 6
(a) ab + ab' = a
(b) (a + b)(a + b') = a
Examples:
– ABC + AB'C = AC
[T6(a)]
– (W' + X' + Y' + Z')(W' + X' + Y' + Z)(W' + X' + Y + Z')(W' + X' + Y + Z)
= (W' + X' + Y')(W' + X' + Y + Z')(W' + X' + Y + Z)
[T6(b)]
= (W' + X' + Y')(W' + X' + Y)
[T6(b)]
= (W' + X')
[T6(b)]
Chapter 2
5
Fundamentals of Boolean Algebra (5)
•
•
Theorem 7
(a) ab + ab'c = ab + ac
Examples:
– wy' + wx'y + wxyz + wxz'
(b) (a + b)(a + b' + c) = (a + b)(a + c)
= wy' + wx'y + wxy + wxz'
= wy' + wy + wxz'
= w + wxz'
=w
– (x'y' + z)(w + x'y' + z') = (x'y' + z)(w + x'y')
Chapter 2
[T7(a)]
[T7(a)]
[T7(a)]
[T7(a)]
[T7(b)]
6
Fundamentals of Boolean Algebra (6)
•
Theorem 8 (DeMorgan's Theorem)
(a) (a + b)' = a'b'
(b) (ab)' = a' + b'
•
Generalized DeMorgan's Theorem
(a) (a + b + … z)' = a'b' … z'
(b) (ab … z)' = a' + b' + … z'
•
Examples:
– (a + bc)'
= (a + (bc))'
= a'(bc)'
= a'(b' + c')
= a'b' + a'c'
– Note: (a + bc)' a'b' + c'
Chapter 2
[T8(a)]
[T8(b)]
[P5(b)]
7
Fundamentals of Boolean Algebra (7)
•
More Examples for DeMorgan's Theorem
– (a(b + z(x + a')))'
= a' + (b + z(x + a'))'
= a' + b' (z(x + a'))'
= a' + b' (z' + (x + a')')
= a' + b' (z' + x'(a')')
= a' + b' (z' + x'a)
= a' + b' (z' + x')
– (a(b + c) + a'b)'
Chapter 2
= (ab + ac + a'b)'
= (b + ac)'
= b'(ac)'
= b'(a' + c')
[T8(b)]
[T8(a)]
[T8(b)]
[T8(a)]
[T3]
[T5(a)]
[P5(b)]
[T6(a)]
[T8(a)]
[T8(b)]
8
Fundamentals of Boolean Algebra (8)
•
•
Theorem 9 (Consensus)
(a) ab + a'c + bc = ab + a'c
(b) (a + b)(a' + c)(b + c) = (a + b)(a' + c)
Examples:
– AB + A'CD + BCD = AB + A'CD
– (a + b')(a' + c)(b' + c) = (a + b')(a' + c)
– ABC + A'D + B'D + CD
= ABC + (A' + B')D + CD
= ABC + (AB)'D + CD
= ABC + (AB)'D
= ABC + (A' + B')D
= ABC + A'D + B'D
Chapter 2
[T9(a)]
[T9(b)]
[P5(b)]
[T8(b)]
[T9(a)]
[T8(b)]
[P5(b)]
9
Switching Functions
•
•
•
•
•
•
Switching algebra: Boolean algebra with the set of elements K = {0, 1}
If there are n variables, we can define 2
switching functions.
Sixteen functions of two variables (Table 2.3):
2
n
AB
f0
f1
f2
f3
f4
f5
f6
f7
f8
f 9 f 10 f 11 f 12 f 13 f 14 f 15
00
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
01
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
10
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
11
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
A switching function can be represented by a table as above, or by a switching
expression as follows:
f0(A,B)= 0, f6(A,B) = AB' + A'B, f11(A,B) = AB + A'B + A'B' = A' + B, ...
Value of a function can be obtained by plugging in the values of all variables:
The value of f6 when A = 1 and B = 0 is: 1  0 '  1' 0 = 0 + 1 = 1.
Chapter 2
10
Truth Tables (1)
•
•
Shows the value of a function for all possible input combinations.
Truth tables for OR, AND, and NOT (Table 2.4):
Chapter 2
ab
f(a,b)= a+ b
ab
f(a,b)= ab
a
f(a)= a'
00
0
00
0
0
1
01
1
01
0
1
0
10
1
10
0
11
1
11
1
11
Truth Tables (2)
•
Truth tables for f(A,B,C) = AB + A'C + AC' (Table 2.5)
Chapter 2
ABC
f(A ,B ,C )
ABC
f(A ,B ,C )
000
0
FFF
F
001
1
FFT
T
010
0
FTF
F
011
1
FTT
T
100
1
TFF
T
101
0
TFT
F
110
1
TTF
T
111
1
TTT
T
12
Algebraic Forms of Switching Functions (1)
•
•
•
Literal: A variable, complemented or uncomplemented.
Product term: A literal or literals ANDed together.
Sum term: A literal or literals ORed together.
•
•
•
SOP (Sum of Products):
ORing product terms
f(A, B, C) = ABC + A'C + B'C
•
•
•
POS (Product of Sums)
ANDing sum terms
f (A, B, C) = (A' + B' + C')(A + C')(B + C')
Chapter 2
13
Algebraic Forms of Switching Functions (2)
•
•
•
A minterm is a product term in which all the variables appear exactly
once either complemented or uncomplemented.
Canonical Sum of Products (canonical SOP):
– Represented as a sum of minterms only.
– Example: f1(A,B,C) = A'BC' + ABC' + A'BC + ABC
(2.1)
Minterms of three variables:
Chapter 2
M interm
M interm C ode
M interm N um ber
A 'B 'C '
A 'B 'C
000
001
m0
m1
A 'B C '
A 'B C
010
011
m2
m3
A B 'C '
A B 'C
100
101
m4
m5
ABC'
ABC
110
111
m6
m7
14
Algebraic Forms of Switching Functions (3)
•
•
•
•
Compact form of canonical SOP form:
f1(A,B,C) = m2 + m3 + m6 + m7
A further simplified form:
f1(A,B,C) = S m (2,3,6,7) (minterm list form)
The order of variables in the functional notation is important.
Deriving truth table of f1(A,B,C) from minterm list:
R ow N o.
(i)
In p u ts
ABC
0
000
1
001
0
2
010
1
 m 2
0
3
011
 m 3
0
4
100
1
0
5
101
0
6
110
1
7
111
1
Chapter 2
O u tp u ts
f 1 (A ,B ,C )=  S m (2 ,3 ,6 ,7 )
0
(2.2)
(2.3)
C o m p le m e n t
f 1 '(A ,B ,C )=  S m (0 ,1 ,4 ,5 )
1
 m 0
1
 m 1
1
 m 4
 m 5
 m 6
1
0
 m 7
0
15
Algebraic Forms of Switching Functions (4)
•
Example: Given f(A,B,Q,Z) = A'B'Q'Z' + A'B'Q'Z + A'BQZ' + A'BQZ, express
f(A,B,Q,Z) and f '(A,B,Q,Z) in minterm list form.
f(A,B,Q,Z)
= A'B'Q'Z' + A'B'Q'Z + A'BQZ' + A'BQZ
= m0 + m1 + m6 + m7
= S m(0, 1, 6, 7)
f '(A,B,Q,Z)
= m2 + m3 + m4 + m5 + m8 + m9 + m10 + m11 + m12
+ m13 + m14 + m15
= S m(2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14, 15)
n
•
•
2 1
m 1
AB + (AB)' = 1 and AB + A' + B' = 1, but AB + A'B'  1.
Chapter 2
i
(2.6)
i0
16
Algebraic Forms of Switching Functions (5)
•
•
•
A maxterm is a sum term in which all the variables appear exactly once
either complemented or uncomplemented.
Canonical Product of Sums (canonical POS):
– Represented as a product of maxterms only.
– Example: f2(A,B,C) = (A+B+C)(A+B+C')(A'+B+C)(A'+B+C')
(2.7)
Maxterms of three variables:
Chapter 2
M axterm
M axterm C ode
M axterm N um ber
A+B+C
A+B+C'
000
001
M0
M1
A + B '+ C
A + B '+ C '
010
011
M2
M3
A '+ B + C
A '+ B + C '
100
101
M4
M5
A '+ B '+ C
A '+ B '+ C '
110
111
M6
M7
17
Algebraic Forms of Switching Functions (6)
•
f2(A,B,C) = M0M1M4M5
= PM(0,1,4,5) (maxterm list form)
•
The truth table for f2(A,B,C):
R w o N o. In p u ts
M0
(i)
ABC
A+B+C
0
000
0
Chapter 2
(2.8)
(2.9)
M1
A+B+C'
1
M4
A '+ B + C
1
M5
A '+ B + C '
1
O u tp u ts
f 2 (A ,B ,C )
0
1
001
1
0
1
1
0
2
010
1
1
1
1
1
3
011
1
1
1
1
1
4
100
1
1
0
1
0
5
101
1
1
1
0
0
6
110
1
1
1
1
1
7
111
1
1
1
1
1
18
Algebraic Forms of Switching Functions (7)
•
•
•
Truth tables of f1(A,B,C) of Eq. (2.3) and f2(A,B,C) of Eq. (2.7) are identical.
Hence, f1(A,B,C) = S m (2,3,6,7)
= f2(A,B,C)
= PM(0,1,4,5)
(2.10)
Example: Given f(A,B,C) = ( A+B+C')(A+B'+C')(A'+B+C')(A'+B'+C'),
construct the truth table and express in both maxterm and minterm form.
– f(A,B,C) = M1M3M5M7 = PM(1,3,5,7) = S m (0,2,4,6)
Chapter 2
R ow N o.
(i)
In p u ts
ABC
0
1
000
001
2
010
1
3
011
 M 3
4
5
100
101
0
1
0
 M 5
6
110
1
7
111
0
O u tp u ts
f(A ,B ,C )= P M (1 ,3 ,5 ,7 ) = S m (0 ,2 ,4 ,6 )
1
m0
0
 M 1
m 2
m4
m 6
 M 7
19
Algebraic Forms of Switching Functions (8)
•
Relationship between minterm mi and maxterm Mi:
– For f(A,B,C), (m1)' = (A'B'C)' = A + B + C' = M1
– In general, (mi)' = Mi
(Mi)' = ((mi)')' = mi
Chapter 2
(2.11)
(2.12)
20
Algebraic Forms of Switching Functions (9)
•
Example: Relationship between the maxterms for a function and its
complement.
– For f(A,B,C) = ( A+B+C')(A+B'+C')(A'+B+C')(A'+B'+C')
– The truth table is:
R ow N o.
(i)
In p u ts
ABC
O u tp u ts
f (A ,B ,C )
0
000
1
0
1
001
0
1
2
010
1
 M 2 
3
011
0
0
1
4
100
1
 M 4
5
101
0
0
1
6
110
1
 M 6 
7
111
0
0
1
Chapter 2
O u tp u ts
f '(A ,B ,C )= P M (0,2,4,6)
 M 0
21
Algebraic Forms of Switching Functions (10)
– From the truth table
f '(A,B,C) = PM(0,2,4,6) and f(A,B,C) = PM(1,3,5,7)
– Since f(A,B,C)  f '(A,B,C) = 0,
(M0M2M4M6)(M1M3M5M7) = 0 or  M  0
– In general,  M  0
– Another observation from the truth table:
f(A,B,C) = S m (0,2,4,6) = PM(1,3,5,7)
f '(A,B,C) = S m (1,3,5,7) = PM(0,2,4,6)
3
2 1
i
i0
n
2 1
(2.13)
i
i0
Chapter 2
22
Derivation of Canonical Forms (1)
•
•
Derive canonical POS or SOP using switching algebra.
Theorem 10. Shannon's expansion theorem
(a). f(x1, x2, …, xn) = x1 f(1, x2, …, xn) + (x1)' f(0, x2, …, xn)
(b). f(x1, x2, …, xn) = [x1 + f(0, x2, …, xn)] [(x1)' + f(1, x2, …, xn)]
•
Example: f(A,B,C) = AB + AC' + A'C
– f(A,B,C) = AB + AC' + A'C = A f(1,B,C) + A' f(0,B,C)
= A(1B + 1C' + 1'C) + A'(0B + 0C' + 0'C) = A(B + C') + A'C
– f(A,B,C) = A(B + C') + A'C = B[A(1+C') + A'C] + B'[A(0 + C') + A'C]
= B[A + A'C] + B'[AC' + A'C] = AB + A'BC + AB'C' + A'B'C
– f(A,B,C) = AB + A'BC + AB'C' + A'B'C
= C[AB + A'B1 + AB'1' + A'B'1] + C'[AB + A'B0 + AB'0' + A'B'0]
= ABC + A'BC + A'B'C + ABC' + AB'C'
Chapter 2
23
Derivation of Canonical Forms (2)
•
•
Alternative: Use Theorem 6 to add missing literals.
Example: f(A,B,C) = AB + AC' + A'C to canonical SOP form.
– AB = ABC' + ABC = m6 + m7
– AC' = AB'C' + ABC' = m4 + m6
– A'C = A'B'C + A'BC = m1 + m3
– Therefore,
f(A,B,C) = (m6 + m7) + (m4 + m6) + (m1 + m3) = Sm(1, 3, 4, 6, 7)
•
Example: f(A,B,C) = A(A + C') to canonical POS form.
– A = (A+B')(A+B) = (A+B'+C')(A+B'+C)(A+B+C')(A+B+C)
= M3M2M1M0
– (A+C')= (A+B'+C')(A+B+C') = M3M1
– Therefore,
f(A,B,C) = (M3M2M1M0)(M3M1) = PM(0, 1, 2, 3)
Chapter 2
24
Incompletely Specified Functions
•
•
•
•
•
A switching function may be incompletely specified.
Some minterms are omitted, which are called don't-care minterms.
Don't cares arise in two ways:
– Certain input combinations never occur.
– Output is required to be 1 or 0 only for certain combinations.
Don't care minterms: di
Don't care maxterms: Di
Example: f(A,B,C) has minterms m0, m3, and m7 and don't-cares d4 and d5.
– Minterm list is: f(A,B,C) = Sm(0,3,7) + d(4,5)
– Maxterm list is: f(A,B,C) = PM(1,2,6)·D(4,5)
– f '(A,B,C) = Sm(1,2,6) + d(4,5) = PM(0,3,7)·D(4,5)
– f (A,B,C)= A'B'C' + A'BC + ABC + d(AB'C' + AB'C)
= B'C' + BC (use d4 and omit d5)
Chapter 2
25
Electronic Logic Gates (1)
•
Electrical Signals and Logic Values
E lectric S ignal
H igh V oltage (H )
L ow V oltage (L )
L ogic V alue
P ositive L ogic
N egative L ogic
1
0
0
1
– A signal that is set to logic 1 is said to be asserted, active, or true.
– An active-high signal is asserted when it is high (positive logic).
– An active-low signal is asserted when it is low (negative logic).
Chapter 2
26
Electronic Logic Gates (2)
AND
OR
a
b
a
b
NOT a
NAND
NOR
a
f(a, b) = a b
f(a, b) = a + b
OR
f(a) = a
NOT
f(a, b) = a b
NAND
b
a
b
E X C L U S I VaE
OR
b
f(a, b) = a + b
f(a, b) = a
S ym bol set 1
Chapter 2
AND

NOR
b
a
b
a
&
f(a, b) = a b
³
1
f(a, b) = a + b
1
f(a) = a
&
f(a, b) = a b
³
1
f(a, b) = a + b
b
a
b
a
b
a
b
E X C L U S I VaE
OR
b
= 1
f(a, b) = a

b
S ym bol set 2
(A N S I/IE E E S ta n d a rd 9 1 -1 9 8 4 )
27
Electronic Logic Gates (3)
Vc c
4B
4A
4Y
3B
3A
3Y
Vc c
4Y
4B
4A
3Y
3B
3A
14
13
12
11
10
9
8
14
13
12
11
10
9
8
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1A
1B
1Y
2A
2B
2Y
GND
1Y
1A
1B
2Y
2A
2B
GND
7400Y
: =AB
Q u a d ru p le tw o -in p u t N A N D g a te s
Vc c
6A
6Y
5A
5Y
4A
4Y
Vc c
4B
4A
4Y
3B
3A
3Y
14
13
12
11
10
9
8
14
13
12
11
10
9
8
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1A
1Y
2A
2Y
3A
3Y
GND
1A
1B
1Y
2A
2B
2Y
GND
7404Y
: =A
H e x in v e rte rs
Chapter 2
7402Y
: =A + B
Q u a d ru p le tw o -in p u t N O R g a te s
7408Y
: =AB
Q u a d ru p le tw o -in p u t A N D g a te s
28
Electronic Logic Gates (4)
Vc c
1C
1Y
3C
3B
3A
3Y
Vc c
2D
2C
NC
2B
2A
2Y
14
13
12
11
10
9
8
14
13
12
11
10
9
8
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1A
1B
2A
2B
2C
2Y
GND
1A
1B
NC
1C
1D
1Y
GND
7410Y
: =ABC
T rip le th re e -in p u t N A N D g a te s
Chapter 2
7420Y
: =ABCD
D u a l fo u r-in p u t N A N D g a te s
29
Electronic Logic Gates (5)
Vc c
NC
H
G
NC
NC
Y
Vc c
4B
4A
4Y
3B
3A
3Y
14
13
12
11
10
9
8
14
13
12
11
10
9
8
1
2
3
4
5
6
7
1
2
3
4
5
6
7
A
B
C
D
E
F
GND
1A
1B
1Y
2A
2B
2Y
GND
7430Y
: =A BCD EFG H
8 - in p u t N A N D g a te
7432Y
: =A + B
Q u a d ru p le tw o -in p u t O R g a te s
Vc c
4B
4A
4Y
3B
3A
3Y
14
13
12
11
10
9
8
1
2
3
4
5
6
7
1A
1B
1Y
2A
2B
2Y
GND
7486Y
: =A Å B
Q u a d ru p le tw o -in p u t e x c lu s iv e - O R g a te s
Chapter 2
30
Basic Functional Components (1)
•
AND
a b
0
0
1
1
0
1
0
1
fA N D(a, b) = a b
0
0
0
1
(a)
A
A B
Y
L
L
H
H
L
L
L
H
L
H
L
H
(b )
Y
B
(c)
A
&
B
Y
(d )
(a) AND logic function.
(b) Electronic AND gate.
(c) Standard symbol.
(d) IEEE block symbol.
Chapter 2
31
Basic Functional Components (2)
•
OR
A
a b fO R(a, b) = a + b
A B
Y
0
0
1
1
L
L
H
H
L
H
H
H
0
1
0
1
0
1
1
1
(a)
L
H
L
H
(b)
Y
B
(c)
A

B
Y
(d)
(a) OR logic function.
(b) Electronic OR gate.
(c) Standard symbol.
(d) IEEE block symbol.
Chapter 2
32
Basic Functional Components (3)
•
Meaning of the designation  1 in IEEE symbol:
Chapter 2
f O R (a , b) = a + b
0
sum (a , b)  1
F alse
01
1
T rue
1
10
11
1
2
T rue
T rue
1
1
ab
sum (a , b )
00
0
33
Basic Functional Components (4)
•
NOT
A
a
0
1
fN O T(a) = a
1
0
(a )
A
Y
L
H
H
L
(b )
Y
(c )
A
1
Y
(d )
(a) NOT logic function.
(b) Electronic NOT gate.
(c) Standard symbol.
(d) IEEE block symbol.
Chapter 2
34
Basic Functional Components (5)
•
Positive Versus Negative Logic
P ositive L ogic
N egative L ogic
1 is represented by
H igh V oltage
L ow V oltage
0 is represented by
L ow V oltage
H igh V oltage
Chapter 2
35
Basic Functional Components (6)
•
AND Gate Usage in Negative Logic
A B
Y
a
1
1
0
0
1
1
1
0
b
1
0
1
0
(a )
A
Y
B
(b )
y=a+b
(c )
a
y = ab
b
(d )
–
–
–
–
–
–
Chapter 2
(a) AND gate truth table (L = 1, H = 0)
(b) Alternate AND gate symbol (in negative logic)
(c) Preferred usage
(d) Improper usage
y = a·b =
a  b  a  b  f OR ( a , b )
y  ( a )  ( b )  a  b  f OR ( a , b )
(2.14)
(2.15)
36
Basic Functional Components (7)
•
OR Gate Usage in Negative Logic
A B
Y
a
1
1
0
0
1
0
0
0
b
1
0
1
0
(a )
A
Y
B
(b )
y = ab
(c )
a
y=a+b
b
(d )
–
–
–
–
–
–
Chapter 2
(a) OR gate truth table(L = 1, H = 0)
(b) Alternate OR gate symbol (in negative logic)
(c) Preferred usage
(d) Improper usage
y  a  b  a  b  a  b  f AND ( a , b )
y  ( a )  ( b )  a  b  f AND ( a , b )
(2.16)
(2.17)
37
Basic Functional Components (8)
•
Example 2.32: Building smoke alarm system
– Components: two smoke detectors, a sprinkler, and an automatic
telephone dialer
– Behavior:
• Sprinkler is activated if either smoke detector detects smoke.
• When both smoke detector detect smoke, fire department is called.
– Signals:
• D 1, D 2 : Active-low outputs from two smoke detectors.
•
: Active-low input to the sprinkler
SPK
• DIAL : Active-low input to the telephone dialer.
– Logic equations
• SPK  D 1  D 2
(2.18)
•
(2.19)
DIAL  D 1  D 2
Chapter 2
38
Basic Functional Components (9)
•
Logic diagram of the smoke alarm system
Sm oke
d e te c to rs
D1
D2
G1
D1 + D2
S p rin k le r
SP K
G2
D1 D2
T e le p h o n e
d ia le r
D IA L
Chapter 2
39
Basic Functional Components (10)
•
NAND
a b
0
0
1
1
fN A N D(a, b) = a b
0
1
0
1
1
1
1
0
A B
Y
L
L
H
H
H
H
H
L
(a )
A
Y
B
(c )
–
–
–
–
Chapter 2
A
Y
B
(d )
A
L
H
L
H
(b )
&
B
Y
(e )
(a) NAND logic function
(b) Electronic NAND gate
(c) Standard symbol
(d) IEEE block symbol
40
Basic Functional Components (10)
•
Matching signal polarity to NAND gate inputs/outputs
–
(a) Preferred usage
(b) Improper usage
a
y
b
a
y
b
a
a
y
b
(a )
•
y
b
(b )
f NAND ( a , a )  a  a  a  f NOT ( a )
f NAND ( a , b )  a  b  a  b  f AND ( a , b )
f NAND ( a , b )  a  b  a  b  f OR ( a , b )
•
Hence, NAND gate may be used to implement all three elementary operators.
Chapter 2
41
Basic Functional Components (11)
•
AND, OR, and NOT gates constructed exclusively from NAND gates
a
ab
b
f(a, b) = a b= a b
A N D g a te
a
a
f(a, a) = aa = a
N O T g a te
a
f(a, b) = a + b = a + b
b
b
O R g a te
Chapter 2
42
Basic Functional Components (12)
•
NOR
a b
0
0
1
1
fN O R(a, b) = a + b
0
1
0
1
1
0
0
0
(a )
A
Y
B
(c )
–
–
–
–
Chapter 2
A B
Y
L
L
H
H
H
L
L
L
L
H
L
H
(b )
A
Y
B
(d )
A
³1
B
Y
(e )
(a) NAND logic function
(b) Electronic NAND gate
(c) Standard symbol
(d) IEEE block symbol
43
Basic Functional Components (13)
•
Matching signal polarity to NOR gate inputs/outputs
–
(a) Preferred usage
(b) Improper usage
a
y
b
a
y
b
(a )
•
a
y
b
a
y
b
(b )
f NOR ( a , a )  a  a  a  f NOT ( a )
f NOR ( a , b )  a  b  a  b  f OR ( a , b )
f NOR ( a , b )  a  b  a  b  f AND ( a , b )
•
Hence, NAND gate may be used to implement all three elementary operators.
Chapter 2
44
Basic Functional Components (14)
•
AND, OR, and NOT gates constructed exclusively from NOR gates.
a
a+b
b
f(a, b) = a + b a
O R g a te
a
f(a, a) = a + a = a
N O T g a te
a
f(a, b) = a b= a b
b
b
A N D g a te
Chapter 2
45
Basic Functional Components (15)
•
Exclusive-OR (XOR)
– fXOR(a, b) = a  b = a b  a b
ab
0
0
1
1
0
1
0
1
f X O R (a, b) = a  b
0
1
1
0
(2.24)
A B
Y
L
L
H
H
L
H
H
L
L
H
L
H
(a) XOR logic function (b) Electronic XOR gate
A
B
Y
(c) Standard symbol
Chapter 2
A
B
=1
Y
(d) IEEE block symbol
46
Basic Functional Components (16)
•
POS of XOR
a  b  a b  ab
 a a  a b  ab  bb
 a (a  b)  b (a  b)
 ( a  b )( a  b )
•
Some other useful relationships
– aa=0
– a a =1
– a0=a
– a1= a
– ab ab
– ab=ba
– a  (b  c) = (a  b)  c
Chapter 2
[P2(a), P6(b)]
[P5(b)]
[P5(b)]
(2.25)
(2.26)
(2.27)
(2.28)
(2.29)
(2.30)
(2.31)
47
Basic Functional Components (17)
•
•
Output of XOR gate is asserted when the mathematical sum of inputs is one:
ab
sum (a, b)
sum (a, b) = 1?
00
01
0
1
F alse
T rue
f(a, b) = a  b
0
1
10
11
1
2
T rue
F alse
1
0
The output of XOR is the modulo-2 sum of its inputs.
Chapter 2
48
Basic Functional Components (18)
•
Exclusive-NOR (XNOR)
– fXNOR(a, b) = a  b  a
Chapter 2
(2.32)
a b fX N O R(a, b) = a b
A B
Y
0
0
1
1
L
L
H
H
H
L
L
H
0
1
0
1
1
0
0
1
(a)
–
–
–
–
b
L
H
L
H
(b)
A
Y
B
(c)
A
=1
B
Y
(d)
(a) XNOR logic function
(b) Electronic XNOR gate
(c) Standard symbol
(d) IEEE block symbol
49
Basic Functional Components (19)
•
SOP and POS of XNOR
a b ab
 a b  ab
 a b  ab
 ( a  b )( a  b )
 a a  ab  a b  b b
 ab  a b
•
ab
Chapter 2
= a
[P2]
[T8(a)]
[T8(b)]
[P5(b)]
[P6(b), P2(a)]
b
50
Analysis of Combinational Circuits (1)
•
Digital Circuit Design:
– Word description of a function
 a set of switching equations
 hardware realization (gates, programmable logic devices, etc.)
•
Digital Circuit Analysis:
– Hardware realization
 switching expressions, truth tables, timing diagrams, etc.
•
Analysis is used
– To determine the behavior of the circuit
– To verify the correctness of the circuit
– To assist in converting the circuit to a different form.
Chapter 2
51
Analysis of Combinational Circuits (2)
•
Algebraic Method: Use switching algebra to derive a desired form.
•
Example 2.33: Find a simplified switching expressions and logic network for
the following logic circuit (Fig. 2.21a).
a
P1
b
P4
a
c
b
f (a, b, c)
P2
P3
c
(a )
Chapter 2
52
Analysis of Combinational Circuits (3)
•
•
•
Write switching expression for each gate output:
– P  ab , P  a  c , P3  b  c , P4  P1  P2  ab  ( a  c )
1
2
The output is: f ( a , b , c )  P  P  ( b  c )  ab  ( a  c )
3
4
Simplify the output function using switching algebra:
f ( a , b , c )  ( b  c )  ab  a  c
[Eq. 2.24]
[T8]
[T5(b)]
[T4(a)]
[Eq. 2.32]
 bc  b c  ab  a  c
 bc  b c  ( a  b ) a c
 bc  b c  a b c
 bc  b c
=b c
Therefore, f (a,b,c) = (b
f (a, b, c)
c)' = b  c
b
f (a, b, c)
c
Chapter 2
53
Analysis of Combinational Circuits (4)
•
Example 2.34: Find a simplified switching expressions and logic network for
the following logic circuit (Fig. 2.22).
a
a
b
b
(a
b)(b
c)
b
c
b
a
a+b
c
f (a, b, c)
b
a+b+a+c
a
c
a+c
G iv e n c irc u it
Chapter 2
54
Analysis of Combinational Circuits (5)
•
Derive the output expression:
f(a,b,c)
= ( a  b )( b  c )  ( a  b  a  c )
= ( a  b )( b  c )  a  b  a  c )
= ( a  b )( b  c )  ( a  b )( a  c )
= ( a b  a b )( b c  b c )  ( a  b )( a  c )
= a b b c  a b b c  a bb c  a b b c  a a  a c  a b
= ab c  a bc  a c  ab  b c
= a bc  a c  ab  b c
= a bc  a c  ab
a
= a b  a c  ab
c
= ac  a  b
bc
f (a, b, c)
[T8(b)]
[T8(a)]
[Eq. 2.24]
[P5(b)]
[P6(b), T4(a)]
[T4(a)]
[T9(a)]
[T7(a)]
[Eq. 2.24]
a
b
S im p lifie d c irc u it
Chapter 2
55
Analysis of Combinational Circuits (6)
•
Truth Table Method: Derive the truth table one gate at a time.
•
The truth table for Example 2.34:
Chapter 2
ab
abc
000
001
010
011
100
ac
0
1
0
1
0
0
0
1
1
1
f(a,b,c)
0
1
1
1
1
101
0
1
1
110
111
0
0
0
0
0
0
56
Analysis of Combinational Circuits (7)
•
Analysis of Timing Diagrams
– Timing diagram is a graphical representation of input and output signal
relationships over the time dimension.
– Timing diagrams may show intermediate signals and propagation delays.
Chapter 2
57
Analysis of Combinational Circuits (8)
•
Example 2.35: Derivation of truth table from a timing diagram
A
A
B
B
Y = fa (A, B, C)
C
I n p u ts
O u tp u ts
Z = fb (A, B, C)
Y = fa (A, B, C)
Z = fb (A, B, C)
C
t0
(a )
t2
t3
t4
t5
t6
t7
(b )
I n p u ts
T im e
Chapter 2
t1
ABC
O u tp u ts
fa(A, B, C)
fb(A, B, C)
t0
0 0 0
0
0
t1
0 0 1
1
1
t2
0 1 0
1
0
t3
0 1 1
0
1
t4
1 0 0
0
0
t5
1 0 1
0
1
t6
1 1 0
1
1
t7
1 1 1
1
0
(c )
58
Analysis of Combinational Circuits (9)
•
Propagation Delay
– Physical characteristics of a logic circuit to be considered:
• Propagation delays
• Gate fan-in and fan-out restrictions
• Power consumption
• Size and weight
– Propagation delay: The delay between the time of an input change and the
corresponding output change.
– Typical two propagation delay parameters:
• tPLH = propagation delay time, low-to-high-level output
• tPHL = propagation delay time, high-to-low-level output
– Approximation:
• t  t PLH  t PHL
PD
Chapter 2
2
59
Analysis of Combinational Circuits (10)
•
Propagation delay through a logic gate
a
b
a
c
b
c
(a ) T w o -in p u t A N D g a te
a
a
b
b
c
c
tP D
tP D
(c )tP D = tP L H = tP H L
Chapter 2
(b ) Id e a l (z e ro ) d e la y
tP L H
tP H L
(d )tP L H < tP H L
60
Analysis of Combinational Circuits (11)
•
Power dissipation and propagation delays for several logic families (Table 2.7)
L ogic
F am ily
7400
74H 00
74L 00
74L S 00
P ropagation D elay
t P D (ns)
10
6
33
9.5
P ow er D issipation
P er G ate (m W )
10
22
1
2
74S 00
74A L S 00
3
3.5
19
1.3
74A S 00
74H C 00
3
8
8
0.17
Chapter 2
T echnology
S tandard T T L
H igh-speed T T L
L ow -pow er T T L
L ow -pow er S chottky T T L
S chottky T T L
A dvanced low -pow er
S chottky T T L
A dvanced S chottky T T L
H igh-speed C M O S
61
Analysis of Combinational Circuits (12)
•
Propagation delays of primitive 74LS series gates (Table 2.8)
tP LH
T y pical
M ax im u m
9
15
tPH L
T y pical
M axim u m
10
15
C h ip
74LS04
F u n ctio n
NOT
74LS00
NAND
9
15
10
15
74LS02
74LS08
74LS32
NOR
AND
OR
10
8
14
15
15
22
10
10
14
15
20
22
22
Chapter 2
62
Analysis of Combinational Circuits (13)
•
Example 2.36: Given a circuit diagram and the timing diagram, find the truth
table and minimum switching expression.
D
C
F
ABC
A
0
0
0
0
1
1
1
1
Y = f (A, B, C)
E
B
G
A
0
0
1
1
0
0
1
1
f (A, B, C)
0
1
0
1
0
1
0
1
0
1
0
0
1
1
1
0
B
C
f ( A, B , C )
D
E
  m (1, 4 , 5 , 6 )
F
 A B C  A B C  A B C  AB C
G
 AC  B C
f (A, B, C)
t0
t1
t3
t1 + 2 t2 t2 + 2
t1 + 1
Chapter 2
t2 + 1
t4
t5
t4 + 3
t4 + 2
t4 + 1
t6
t7
t7 + 3
t7 + 2
t7 + 1
63
Synthesis of Combinational Logic Circuits (1)
•
AND-OR and NAND Networks
– Switching expression must be in SOP form.
– Example: f  ( p , q , r , s )  p r  qrs  p s
Bu
b bles
Ò can
cel
Ó
p
p
r
r
q
r
s
fd (p, q, r, s)
q
r
s
p
p
s
s
(a ) A N D -O R n e tw o rk
–
p
x1
fd (p, q, r, s)
x2
x3
q
r
s
p
fd (p, q, r, s)
x2
x3
s
(b ) N A N D n e tw o rk
where x  p r , x  qrs ,
1
2
(c ) N A N D n e tw o rk (p re fe rre d fo rm )
[T3]
[T8(a)]
f  ( p , q , r , s )  p r  qrs  p s
 p r  qrs  p s
 x1  x 2  x 3
Chapter 2
x1
r
and x  p s
3
64
Synthesis of Combinational Logic Circuits (2)
•
OR-AND and NOR Networks
– Switching expression must be in POS form.
– Example: f  ( A , B , C , D )  ( A  B  C )( B  C  D )( A  D )
A
B
C
A
B
C
B
C
D
fe (A, B, C, D)
B
C
D
A
A
D
D
(a ) O R - A N D n e tw o rk
A
B
C
y1
fe (A, B, C, D)
y2
y3
y1
B
C
D
fe (A, B, C, D)
y2
A
y3
D
(b ) N O R n e tw o rk
(c ) N O R n e tw o rk (p r e fe r re d fo r m )
– f  ( A , B , C , D )  ( A  B  C )( B  C  D )( A  D )
 A BC BC D A D
[T3]
[T8(b)]
 y1  y 2  y 3
where y  A  B  C ,
1
Chapter 2
y2  B  C  D ,
and y  A  D
3
65
Synthesis of Combinational Logic Circuits (3)
•
Two-level Circuits
– Input signals pass through two levels of gates before reaching the output.
p
p
x1
r
q
r
s
p
fd (p, q, r, s)
x2
x1
r
x3
s
q
r
s
p
fd (p, q, r, s)
x2
x3
s
L evel 2
L evel 1
(a ) T w o -le v e l n e tw o rk
L e v e l 3L e v e l 2
L evel 1
(b ) T h re e -le v e l n e tw o rk
– Implementation procedure for NAND (NOR) logic:
• Step 1. Express the function in minterm (maxterm) list form.
• Step 2. Write out the minterms (maxterms) in algebraic form.
• Step 3. Simplify the function in SOP (POS) form.
• Step 4. Transform the expression into the NAND (NOR) form.
• Step 5. Draw the NAND (NOR) logic diagram.
Chapter 2
66
Synthesis of Combinational Logic Circuits (4)
•
Circuits with more than two levels are often needed due to fan-in constraints.
a
b
c
f = abcde
d
e
(a ) A sin g le fiv e -in p u t A N D g a te
a
a
b
b
c
c
f = abcde
d
e
d
e
(b ) T h re e -le v e l n e tw o rk o f tw o -in p u t g a te s
Chapter 2
f = abcde
(c ) F o u r-le v e l n e tw o rk o f tw o -in p u t g a te s.
67
Synthesis of Combinational Logic Circuits (5)
•
Example 2.37: NAND implementation of f (X,Y,Z) = Sm(0,3,4,5,7)
1. f (X,Y,Z) = Sm(0,3,4,5,7)
2. f (X,Y,Z) = m0 + m3 + m4 + m5 + m7
 X Y Z  X YZ  X Y Z  X Y Z  XYZ
3. f  ( X , Y , Z )  Y Z  YZ  XZ
4a. f ( X , Y , Z )  Y Z  YZ  XZ

or
4b. f  ( X , Y , Z )  Y Z  YZ  XZ
 Y Z  YZ  XZ
[T6(a)]
[T4]
[T3]
[T8(a)]
Y
Z
Y
f (X, Y, Z)
Z
X
Z
(a ) N A N D im p le m e n ta tio n
Chapter 2
68
Synthesis of Combinational Logic Circuits (6)
•
AND-OR-invert Circuits
– A set of AND gates followed by a NOR gate.
– Used to readily realize two-level SOP circuits.
– 7454 circuit: F  AB  CD  EF  GH
M a k e n o e x te rn a l
c o n n e c tio n
Vcc
14
B
13
H
12
11
10
G
9
Y
8
Y1
Y2
A
B
C
D
Y
Y3
Y4
1
A
Chapter 2
2
C
3
D
4
E
5
F
6
7
NC
GND
(a ) 7 4 5 4 c irc u it p a c k a g e (to p v ie w )
O u tp u t
E
F
G
H
E n a b le lin e s
(b ) 7 4 5 4 u se d a s a 4 -to -1 m u ltip le x e r
69
Synthesis of Combinational Logic Circuits (7)
•
•
Factoring
– A technique to obtain higher-level forms of switching functions.
– Higher-level forms:
• May need less hardware
• May be used when there are fan-in constraints
• More difficult to design
• Slower
Example 2.39:
f ( A , B , C , D )  A B  A D  A C  A ( B  D  C )  A ( BCD )
A
B
A
A
f (A, B, C, D)
f (A, B, C, D)
D
B
C
D
A
C
Chapter 2
(a ) O rig in a l fo rm
(b ) A fte r fa c to rin g
70
Synthesis of Combinational Logic Circuits (8)
•
Example 2.40: f (a,b,c,d) = Sm(8,13) with only two-input AND and OR gates.
– Write the canonical SOP form:
f (a,b,c,d) = Sm(8,13) = a b c d  ab c d
(2.34)
Two four-input AND gates and one two-input OR gate are needed.
– Apply factoring:
(2.35)
f ( a , b , c , d )  a b c d  ab c d  ( a c )( bd  b d )
b
d
f = (a, b, c, d)
c
a
Chapter 2
71
Synthesis of Combinational Logic Circuits (9)
•
Example 2.41: A burglar alarm with four control switches, each of which
produces logic 1 when:
Switch A: Secret switch is closed
Switch B: Safe is in its normal position in the closet
Switch C: Clock is between 1000 and 1400 hours
Switch D: Closet door is closed.
Write the equations of the control logic that produces logic 1 when
the safe is moved AND the secret switch is closed,
OR
the closet is opened after banking hours,
OR
the closet is opened with the control switch open.
f ( A, B , C , D )  A B  C D  A D
Chapter 2
72
Synthesis of Combinational Logic Circuits (10)
•
Example 2.42: The Doe family voter:
– Vote for either hamburgers (0) or chicken (1).
– Majority wins.
– If Mom and Dad agree, they win.
– John (Dad): A, Jane (Mom):B, Joe: C, Sue: D.
– The logic function is:
f ( A , B , C , D )  A BCD  A B CD  AB C D  AB C D  ABC D  ABCD
 A BCD  A B CD  AB
 AB  ACD  A BCD
 AB  ACD  BCD
A
B
C
D
Chapter 2
f (A, B, C, D)
73
Synthesis of Combinational Logic Circuits (11)
•
Example 2.43: Logic equations for a circuit that adds two 2-bit binary
numbers (A1A0)2 and (B1B0)2, and produces sum bits (S1S0)2 and carry bit C1;
A1A0
+ B1B0
C1S1S0
Chapter 2
74
Synthesis of Combinational Logic Circuits (12)
•
Truth Table:
A1 A0 B1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
Chapter 2
•
B0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
C1
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
S1
0
0
1
1
0
1
1
0
1
1
0
0
1
0
0
0
S0
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
Logic equations:
S0 = A A B B  A A B B  A A B B
1 0 1 0
1 0 1 0
1 0 1 0
 A1 A0 B1 B 0  A1 A0 B1 B 0  A1 A0 B1 B 0
 A1 A0 B1 B 0  A1 A0 B1 B 0
S1 = A1 A0 B1 B 0  A1 A0 B1 B 0  A1 A0 B1 B 0
 A1 A0 B1 B 0  A1 A0 B1 B 0  A1 A0 B1 B 0
 A1 A0 B1 B 0  A1 A0 B1 B 0
C1 = A A B B  A A B B  A A B B
1 0 1 0
1 0 1 0
1 0 1 0
 A1 A0 B1 B 0  A1 A0 B1 B 0  A1 A0 B1 B 0
75
Synthesis of Combinational Logic Circuits (13)
•
Reduced equations:
S0 =
A0 B 0  A0  B 0
S1 =
A1 A0 B1  A1 B1 B 0  A1 A0 B1 B 0
 A1 A0 B1 B 0  A1 B1 B 0  A1 A0 B1
C1 =
Chapter 2
A0 B1 B 0  A1 A0 B 0  A1 B1
76
Computer-aided Design (1)
•
Design Cycle
Concept
M o d e lin g
and
d e sig n c a p tu re
S y n th e s is
D e sig n
o p tim iz a tio n
D e sig n
d a ta b a se
T e st
v e c to rs
L o g ic
sim u la tio n
A n a ly sis
F a il
R e su lts
?
P a ss
Im p le m e n ta tio n
R e a liz a tio n
P h y sic a l
d e sig n
T e s tin g
T e st
F in ish e d c irc u it
Chapter 2
77
Computer-aided Design (2)
•
Digital Circuit Modeling
– Purpose of modeling:
• Helps the designer formalize a solution.
• To check errors, verify correctness, and predict timing characteristics.
– CAD tools are available for design optimization and transformation of
design from abstract form to a physical realization.
– Model can represent different levels of design abstraction.
Chapter 2
L ev el
B eh av io ral
A b stractio n
A lg o rith m s to b e realized
R eg ister
T ran sfer
 S tru ctu re o f m o d u les
 D ata flo w am o n g m o d u les an d co n tro l alg o rith m
G ate
S tru ctu re o f p rim itiv e lo g ic gates
T ran sisto r
L ay o u t
S tru ctu re o f tran sisto rs an d lo w -lev el co m p o n en ts
G eo m etric pattern s o f m aterials fo r IC lay o u t
78
Computer-aided Design (3)
•
High-level abstract model (behavioral model)
– Describes only desired behavior.
– Usually represented using a hardware description language (HDL), e.g.,
VHDL or Verilog.
– Other representation mechanisms: logic equations, truth tables, and
minterm or maxterm lists.
Chapter 2
79
Computer-aided Design (4)
•
Behavioral models of a full-adder circuit:
(a) block diagram, (b) truth table, (c) logic equations.
a
b
ci n
F u ll_ a d d e r
s
co u t
(a )
Chapter 2
a
b
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
ci n
co u t
s
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
s=a
b
ci n
co ut = a b + a cin + b cin
(c )
(b )
80
Computer-aided Design (5)
•
VHDL behavioral model of a full adder circuit (Figure 2.38)
– Entity defines the interface between the circuit and the outside world.
– Architecture defines the function implemented within the circuit.
– Multiple architectures may be defined for a given entity.
•
Structural model
– Interconnection of components.
– Behavior is deduced from the behavioral models of individual components
and their interconnection.
– Represented by:
• Logic or schematic diagram
• Netlist (textual representation of schematic diagram)
• HDL description of circuit structures.
Chapter 2
81
Computer-aided Design (6)
•
Structural models of a full-adder circuit:
(a) schematic diagram, (b) netlist
I1
I2
I3
a
b
X1
x1
X2
s
O1
ci n
A1
A2
A3
a1
a2
a3
(a )
R1
co u t
O2
I1
I2
I3
X1
X2
A1
A2
A3
R1
O1
O2
IN
a
IN
b
IN
cin
X O R 2 x1
XOR2
s
A N D 2 a1
A N D 2 a2
A N D 2 a3
O R 3 co ut
OUT
s
O U T co u t
a
x1
a
a
b
a1
b
cin
b
cin
cin
a2
a3
(b )
– In a netlist, each circuit element is defined as follows:
gate_name, gate_type, output, input1, input2, …, inputN
– VHDL structural model of a full-adder circuit: Figure 2.40.
Chapter 2
82
Computer-aided Design (7)
•
Mixed-mode model
– Contains both behavioral and structural components.
(b) circuit for sum function, (c) truth table for carry function.
a
a
b
ci n
Sum
m o d u le
s
C a rry
m o d u le
co u t
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
ci n
co u t
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
(c )
(a )
a
s
b
ci n
(b )
Chapter 2
83
Computer-aided Design (8)
•
Design synthesis process
B e h a v io r a l m o d e ls
H D L m odel
F u n c tio n
lib ra ry
A u to m a tic
sy n th e sis
T ru th ta b leL o g ic e q u a tio n s
A u to m a tic
sy n th e sis
S tr u c tu r a l m o d e ls
S c h e m a tic
L o g ic
e q u a tio n s
C o n stra in ts
C om ponent
lib ra ry
N e tlist
D e sig n
o p tim iz a tio n
M in im iz e
S c h e m a tic
O p tim iz e d
lo g ic
e q u a tio n s
B ack
a n n o ta tio n
C om ponent
lib ra ry
N e tlist
g e n e ra tio n
M a p d e sig n
o n to c irc u it
e le m e n ts
C irc u it
n e tlist
Chapter 2
84
Computer-aided Design (9)
•
Capture tools
– Each circuit model in the design process must be captured in a format that
can be stored and processed by a digital computer.
– Schematic capture: an interactive graphics tool with which a designer
draws a logic diagram.
Chapter 2
85
Computer-aided Design (10)
•
Schematic capture process
M ENU
D R A W IN G A R E A
M ENU
D R A W IN G A R E A
P a rts L ib ra ry
ZOOM ZOOM
IN
OUT
and2
and3
o r2
o r3
nand2
nand3
n o r2
n o r3
x o r2
not
in
out
SELECT
DELETE
COPY M OVE
PLA CE D RA W
COM P NET
N A M E PA RA M
O PEN SA V E
SH EET SH EET
(a )
M ENU
(b )
D R A W IN G A R E A
ZOOM ZOOM
IN
OUT
M ENU
ZOOM ZOOM
IN
OUT
SELECT
DELETE
SELECT
DELETE
COPY M OVE
COPY M OVE
PLA CE D RA W
COM P NET
PLA CE D RA W
COM P NET
N A M E PA RA M
N A M E PA RA M
O PEN SA V E
SH EET SH EET
O PEN SA V E
SH EET SH EET
D R A W IN G A R E A
11
12
13
a
b
X1
Chapter 2
X2
s
O1
c in
A1
A2
(c )
x1
A3
a1
a2
R1
cout
O2
a3
(d )
86
Computer-aided Design (11)
•
Logic Simulation
– Three primary purposes:
1. Logic verification: only logical correctness is checked.
2. Performance analysis: propagation delays and potential timing
problems are analyzed.
3. Test development (fault simulation): helps develop optimal test set.
– Simulation environment
D es ign
N e tlist
C om ponent
m o d e ls
S im ulator
L o g ic
v e rific atio n
d a ta
Chapter 2
T e st
v e c to rs
T im in g
a n a ly sis
d a ta
87
Computer-aided Design (12)
•
Simulation Test Inputs
– Test set: a carefully designed set of test inputs.
– For logic verification, a list of input vectors is used (time is ignored).
– For timing analysis, the time of each input change is also specified.
functional
test set for
input
tabular
waveform
waveform
format
format
a
0
0
0
0
1
1
1
1
Chapter 2
b cin
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
T im e a b
a
0
5
10
15
b
c
0
5
10
0
0
1
1
0
1
1
0
ci n
0
0
0
0
a = 0:0, 10
: 1;
b = 0:0, 5:1 ,15:0;
cin = 0:0;
15
88
Computer-aided Design (13)
•
Event-Driven Simulation
– Event: a change in the value of a signal at a given time.
– Event-driven simulation example for an AND gate:
a
b
a
c
b
c
T0
(a )
Chapter 2
T1 T1 +
t
T2
(b )
89
Computer-aided Design (14)
•
Event-driven simulation procedure
– Input test set is converted into a set of events.
– The set of events are entered into an event queue (or event list).
– In each simulation step, the first event is retrieved and is made to occur.
– Output of each affected gate is recomputed, and new event is created.
– Record of all events along with output results are maintained.
– Simulation continues until the event queue is empty or time limit expires.
T im e a b
a
b
cin
co u t
s
0
Chapter 2
5 7
10 12
15 17
20
0
2
4
6
8
10
12
14
16
18
20
0
0
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1 0
1 0
1 0
cinco u t
0
0
0
0
0
0
0
0
0
0
0
X
0
0
0
0
0
1
1
1
0
0
s
X
0
0
0
1
1
0
0
0
1
1
T im e a b
0
2
5
7
10
12
15
17
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
cinco u t
0
0
0
0
0
0
0
0
X
0
0
0
0
1
1
0
s
X
0
0
1
1
0
0
1
90
Computer-aided Design (15)
•
erroneous
circuit
a
b
simulation output:
error in s at time 3
T im e a
cin
s
T im e
0
0
0
0
0
0
0
X
1
1
1
0
0
1
0
1
2
3
5
10
12
13
15
17
18
n1
n2
s
n3
cin
n4
Chapter 2
b
0
3
5
10
13
15
18
0
0
0
1
1
1
1
0
0
1
1
1
0
0
expanded simulation:
isolates error to n3
a
0
0
0
0
0
1
1
1
1
1
1
b cin n1 n2 n3 n4 s
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
X
1
1
1
1
1
1
1
1
1
1
X
1
1
1
1
1
1
1
1
0
0
X X X
X 1 X
0
1 X
0
1 1
0
1 1
0
1 1
1
1 1
1
1 0
1
1 0
1
1 0
1
1 1
91
Computer-aided Design (16)
•
Detection of static hazard via simulation
– A glitch in g at time t3 can be detected from the output waveforms.
– This occurs because both e and f become 0 momentarily between t2 and t3.
a
b
c
d
e
f
a
e
b
g
g
d
c
f
(a )
Chapter 2
T im e
t
t1
t
t2
t
t3
t4
(b )
92
Computer-aided Design (17)
•
Symbolic Logic Signal Values
– Designers sometimes need signal values other than just 0 or 1.
– Logic signal values are represented by a state and a strength.
– A third state X represents an unknown state or a potential problem.
– Truth tables for three-valued logic (with X added)
AND 0
0
1
X
1 X
0 0 0
0 1 X
0 X X
1 X
OR
0
0
1
X
0 1 X
1 1 1
X 1 X
NOT 0
0
1
X
1
0
X
– Signal strength values:
• Forcing (F): signal line is strongly forced to a given state.
• Resistive (R): signal line is weakly forced to a given state.
• Floating (Z): signal line is not forced forced at all.
• Unknown (U): signal strength cannot be determined.
Chapter 2
93
Computer-aided Design (18)
•
Signal strengths are used to resolve conflicting gate outputs:
output resolved in favor of
stronger signal.
output value
unable to be resolved
VC C
F0
I1
F1
Ux
F0
I1
F1
R1
I2
F0
F0
F1
(b )
I2
F0
Chapter 2
94
Computer-aided Design (19)
•
Primitive Device Delay Models
– Every primitive logic gate has an intrinsic delay.
– A gate can be modeled as an ideal (zero-delay) gate and a transport delay
element.
a
c*
b
Id e al
g a te
t
c
T im e
d e la y
– Different models of transport delays:
• Unit/Nominal Delay
• Rise Fall Delay
• Ambiguous or Min/Max Delay
Chapter 2
95
Computer-aided Design (20)
•
Unit/Nominal Delay
– Unit delay: assign to each gate in a circuit the same unit delay.
– Nominal delay: delays are determined separately for each type of gate
(e.g., on time unit for NOR and two time units for XOR).
a
b
c
t
Chapter 2
t
96
Computer-aided Design (21)
•
Rise/Fall Delay
– Different delays for 0 to 1 transition and 1 to 0 transition.
– tPLH (rise time): propagation delay from low to high.
– tPHL (fall time): propagation delay from high to low.
a
b
c
tP L H
(rise tim e )
Chapter 2
tP H L
(fa ll tim e )
97
Computer-aided Design (22)
•
Ambiguous or Min/Max Delay
– Sometimes it is impossible to predict exact rise or fall time of a signal.
– For worst-case performance analysis, {tmin, tmax} is specified for each
timing parameter.
a
b
c
tm i n
tm ax
Chapter 2
98
Computer-aided Design (23)
•
A problem with min/max delay: the results tend to be pessimistic.
circuit model
a
worst-case delays:
ambiguity region gets larger
at each successive level
f
b
h
c
d
e
g
d
e
g
h
15
10 12 14 16
Chapter 2
20
25
99
Computer-aided Design (24)
•
Inertial Delay
– An input value must persist for some minimum duration of time to provide
the output with the needed inertia to change.
– The minimum duration is called inertial delay.
– Effect of inertial delay:
a
a
b
b
c
c
(a) T ran sp o rt d elay m o d el
(b ) In ertial d elay m o d el
– Gate model with both inertial delay and transport delay:
a
t
a*
c*
b
Chapter 2
t
In ertial
d elay
t
c
b*
Id eal
g ate
T ran sp o rt
d elay
100