Transcript Chapter # 3: Multi-Level Combinational Logic Contemporary

Multi-Level Logic: Conversion of Forms
EE 231 Digital Electronics
Fall 01
NAND-NAND and NOR-NOR Networks
A + B = A • B;
A•B = A + B
Written differently: A + B = A • B;
A•B = A + B
DeMorgan's Law:
In other words,
OR
=
NAND with complemented inputs
A
B
AND
=
OR with complemented inputs
A
B
NOR
=

A
B
NOR with complemented inputs
A
B
NAND =

A
B

A
B
AND with complemented inputs
A
B

A
B
Week 4-1
EE 231 Digital Electronics
Fall 01
Multi-Level Logic: Conversion of Forms
Example: Map AND/OR network to NAND/NAND network
NAND
A
A
B
Z
B
C
C
D
D
Verify equivalence
of the two forms
Z
NAND
NAND
Z  AB CD
 AB  CD
 AB  CD
Week 4-2
EE 231 Digital Electronics
Fall 01
Multi-Level Logic: Mapping Between Forms
Example: Map AND/OR network to NOR/NOR network
NOR
A’
A
NOR
B’
NOR
B
Z
Z
C
NOR
D
NOR
D’
Step 1
Conserve
"Bubbles"
C’
Step 2
Conserve
"Bubbles"
Week 4-3
EE 231 Digital Electronics
Multi-Level Logic: CAD Tools for Simplification
Fall 01
Decomposition:
Take a single Boolean expression and replace with collection of new
expressions:
F = A B C + A B D + A' C' D' + B' C' D' (12 literals)
F rewritten as:
F = X Y + X' Y'
X=AB
Y=C+D
A
B
C
A
B
D
A
C
D
B
C
D
(4 literals)
A
B
X
F
F
C
D
Before Decomposition
Y
After Decomposition
Week 4-4
EE 231 Digital Electronics
Fall 01
Multi-Level Logic: CAD Tools for Simplification
Extraction: common intermediate subfunctions are factored out
F = (A + B) C D + E
G = (A + B) E'
H=CDE
(11 literals)
can be re-written as:
(7 literals)
F=XY + E
G = X E'
H=YE
X=A+B
Y=CD
E
A
B
F
C
D
A
B
G
C
D
E
Before Extraction
A
B
X
C
D
E
Y
F
G
H
H
After Extraction
Week 4-5
EE 231 Digital Electronics
Multi-Level Logic: CAD Tools for Simplification
Fall 01
Factoring: expression in two level form re-expressed in multi-level form
F=AC + AD + BC + BD + E
(9 literals)
can be rewritten as:
(5 literals)
F = (A + B) (C + D) + E
A
C
A
D
A
B
B
C
F
B
D
F
C
D
E
E
Before Factoring
After Factoring
Week 4-6
EE 231 Digital Electronics
Fall 01
Number Systems
Sign and Magnitude Representation
-7
-6
-5
1111
1110
+0
0000
0001
1101
+1
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-3
1011
0100
+4
1 100 = - 4
-2
1010
0101
1001
-1
+5
-
0110
1000
-0
0111
+6
+7
High order bit is sign: 0 = positive (or zero), 1 = negative
Three low order bits is the magnitude: 0 (000) to 7 (111)
Two representations for 0 are: 0000 and 1000
Week 4-7
EE 231 Digital Electronics
Fall 01
Number Systems
Ones Complement
-0
-1
-2
1111
1110
+0
0000
0001
1101
+1
0010
+2
+
-3
1100
0011
+3
0 100 = + 4
-4
1011
0100
+4
1 011 = - 4
-5
1010
0101
1001
-6
+5
-
0110
1000
-7
0111
+6
+7
To negate a number simply flip all the bits.
Still two representations of 0!
Week 4-8
EE 231 Digital Electronics
Fall 01
Number Representations
Twos Complement
-1
-2
-3
1111
1110
+0
0000
0001
1101
+1
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-5
1011
0100
+4
1 100 = - 4
-6
1010
0101
1001
-7
+5
-
0110
1000
-8
0111
+6
+7
To negate: Twos complement = Ones complement + 1
Only one representation for 0
Easier to implement addition and subtraction
Week 4-9
EE 231 Digital Electronics
Fall 01
Number Systems
Overflow Conditions
Add two positive numbers to get a negative number
or two negative numbers to get a positive number
-1
-2
1111
0001
-4
1101
0010
1100
-5
0100
1010
0101
1001
-7
0110
1000
-8
0111
+6
+7
5 + 3 = -8
-3
+2
0011
1011
-6
-2
+1
0000
1110
-3
-1
+0
+3
-4
1111
+1
0000
1110
0001
1101
0010
1100
-5
1011
+4
+5
+0
1010
-6
+3
0100
+4
0110
1000
-8
0011
0101
1001
-7
+2
0111
+7
-7 - 2 = +7
Week 4-10
+6
+5