Transcript oldappendixC

CS/COE0447
Computer Organization &
Assembly Language
Logic Design
Appendix C
1
Outline
•
•
•
•
•
Example to begin: let’s implement a MUX
Gates, Truth Tables, and Logic Equations
Combinatorial Logic
Constructing an ALU
Memory Elements: Flip-flops, Latches,
and Registers
2
Logic Gates
A
2-input AND
Y
Y=A&B
Y
Y=A|B
Y
Y=~(A&B)
Y
Y=~(A|B)
B
A
2-input OR
2-input NAND
B
A
B
A
2-input NOR
B
3
Multiplexor
A
0
C
B
1
If S then
C=B
else
C=A
How many bits is S?
S
1, since it is choosing between 2 values
Let’s see how to implement a 2-input MUX using gates.
Hint: the answer uses AND gates, an OR gate, and one INVERTER
Answer in lecture
4
Computers and Logic
• Digital electronics operate with only two voltage
levels of interest: high and low voltage.
– All other voltage levels are temporary and occur while
transitioning between values
• We’ll talk about them as signals that are
– Logically true; 1; asserted
– Logically false; 0, deasserted
• 0 and 1 are complements and inverses of each
other
5
Combinational vs. Sequential Logic
• Combinational logic
– A function whose outputs depend only on the
current input
• Sequential logic
– Memory elements, i.e., state elements
– Outputs are dependent on current input and
current state
– Next state is also dependent on current input
and current state
6
…
inputs
…
Combinational Logic
outputs
7
…
inputs
…
Sequential Logic
current
state
outputs
next
state
clock
8
• The next set of topics [until the sequential
logic picture we just saw pops up again]
will only be about combinatorial logic
9
?
…
inputs
…
Functions Implemented Using
Gates
outputs
Combinatorial logic blocks implement logical functions, mapping inputs
to outputs
10
Describing a Function
•
•
•
•
OutputA = F(Input0, Input1, …, InputN-1)
OutputB = F’(Input0, Input1, …, InputN-1)
OutputC = F’’(Input0, Input1, …, InputN-1)
Methods
– Truth table (since combinatorial logic has no
memory, it can be completely specified by a
truth table)
– …[in a moment]
11
Truth Table
Input
Output
A
B
Cin
S
Cout
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
12
Truth Tables
• In a truth table, there is one row for every
possible combination of values of the inputs
• Specifically, if there are N inputs, the possible
combinations are the binary numbers 0 through
2EN - 1. For example:
– 3 bits (0-7): 000 through 111
– 4 bits (0-15): 0000 through 1111
– 5 bits (0-31): 00000 through 11111
• While we could always use a truth table, they
quickly grow in size and become hard to
understand and work with
• Boolean logic equations are more succinct
13
Describing a Function
•
•
•
•
OutputA = F(Input0, Input1, …, InputN-1)
OutputB = F’(Input0, Input1, …, InputN-1)
OutputC = F’’(Input0, Input1, …, InputN-1)
Methods
– Truth table
– Boolean logic equations
• Sum of products
• Products of sums
14
Truth Table and Equations
Input
Output
A
B
Cin
S
Cout
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
• S = A’B’Cin+A’BCin’+AB’Cin’+ABCin
• Cout = A’BCin+AB’Cin+ABCin’+ABCin
Each output has its own…?
Column in the truth table
And its own Boolean equation
15
Truth Tables and Equations
• All functions specified by truth tables can
also be specified by Boolean formulas
[and vice versa]
• So, let’s look more closely at Boolean
algebra
16
Boolean Algebra
• Boole, George (1815~1864): mathematician and
philosopher; inventor of Boolean Algebra, the
basis of all computer arithmetic
• Binary values: 0, 1
• Two binary operations: AND (/), OR ()
– AND is also called the logical product since its result
is 1 only if both operands are 1
– OR is also called the logical sum since its result is 1 if
either operand is 1
• One unary operation: NOT (~)
17
Laws of Boolean Algebra
• Identity, Zero, and One laws
– aa = a+a = a
– a1 =a; a+0 = a [“copy” operations]
– a0 =0; a+1 = 1 [deassert by ANDing with 0; assert by ORing with 1]
• Inverse
– aa = 0; a+a = 1
• Commutative
– ab = ba
– a+b = b+a
• Associative
– a(bc) = (ab)c
– a+(b+c) = (a+b)+c
• Distributive
– a(b+c) = ab + ac
– a+(bc) = (a+b)(a+c)
18
Laws of Boolean Algebra
• De Morgan’s laws
– ~(a+b) = ~a~b
– ~(ab) = ~a+~b
• More…
– a+(ab) = a
– a(a+b) = a
– ~~a=a
• You’ll see this again in CS441 and CS1502
19
Examples
•
•
•
•
To get used to Boolean equations
To see the relationships among Truth
Tables, Boolean Equations, and
hardware implementations in gates
To see that a “sum of products” formula
can always be derived from a truth table
To see that equations can often be
simplified
20
Example equation
• E = (A’ B C) + (A B’ C) + (A B C’)
• What is the value of the equation if A = 1, B = 0
and C = 0?
• E = (1’ 0 0) + (1 0’ 0) + (1 0 0’)
• E = (0 0 0) + (1 1 0) + (1 0 1) = 0
• What is the value of the equation if A = 0, B = 1,
and C = 1?
• E = (0’ 1 1) + (0 1’ 1) + (0 1 1’)
• E = (1 1 1) + (0 0 1) + (0 1 0) = 1
21
Truth Table for E
A
B
C
D
E
F
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
•You can read our equation for E right from the truth table:
• E = (A’ B C) + (A B’ C) + (A B C’)
•These are the three cases when E is 1.
•Now, give a Boolean equation for F:
F=ABC
22
Give a Boolean Equation for D
A
B
C
D
E
F
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
D = (A’ B’ C) + (A’ B C’) + (A’ B C) + (A B’ C’) + (A B’ C) + (A B C’) + (A B
There are many logically equivalent equations (in general)
D = (A’ B’ C’)’ [D is true in all cases except A=0 B=0 C=0.] Apply DeMorgan’s law
D = A’’ + B’’ + C’’ = A + B + C
23
Example: boolean equation of a circuit
First add the boolean equations at the output for each AND gate
A
A•B
B
Y
C
B•C
24
Example:
Next add the Boolean equations at the output for the OR gate
A
A•B
(A•B) + (B•C)
Y
B
C
B•C
The Boolean equation for the complete logic circuit is:
Y = (A•B)+(B•C)
25
Example: Truth Table
Y = (A•B)+(B•C)
A
B
C
Y
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Reading an equation from the Table: Y = (A’ B C) + (A B C’) + (A B C)
The equations are logically equivalent: one way to see this is to consider
each row in the truth table. If the two equations have the same outputs for26
each input, then they are logically equivalent.
Example: MUX
(A S’)
A
C
B
S
(B S)
(A S’) + (B S)
If the equation below were implemented directly:
four (3-input) AND gates and one (4-input) OR
gate would be needed
A
B
S
C
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
Equation read from the Table:
Again, the two formulas
are equivalent
[next slide]
C = (A’ B S) + (A B’ S’) + (A B S’) + (A B S)
27
Example: MUX
BS
C = (A S’) + (B S) C = (A’ B S) + (A B’ S’) + (A B S’) + (A B S)
AS’
If B ==0: (AS’) + 0
If B == 1: 0 + (AS’)
So, this is the same as AS’
Methods
perform such simplifications
automatically
You can see they
are equivalent by
comparing values
for each row
A
B
S
C
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
28
Expressive Power
• Any Boolean algebra function can be constructed using
AND gates, OR gates, and Inverters
– [For your interest: NAND and NOR are both universal: any logic
function can be built with just that one gate type]
• There are “canonical forms” for Boolean functions: all
equations can be expressed in these forms
• This made it possible to create translation programs that,
given a logic equation or truth table as input, can
automatically design a circuit that implements it
29
Outline
•
•
•
•
•
Example to begin: let’s implement a MUX!
Gates, Truth Tables, and Logic Equations
Combinatorial Logic
Constructing an ALU
Memory Elements: Flip-flops, Latches,
and Registers
30
Since we were talking about
MUXs…
• How are larger MUXs implemented
– Wider inputs than 1 bit
– More choices
31
A 32-bit wide 2-to-1 Multiplexor
1-bit input to
to all 32 MUXs
Choosing between 2
32-bit wide buses
Bus: collection of data lines
treated as a single value.
E.g., MUX controlled by
MemtoReg.
Each MUX is the
same; just like the
one we saw earlier
32
Use a Decoder to build a MUX with more choices
Decoder
n bit input value and 2^n outputs (Fig B.3, pB8)
I1
I2
O3
O2
O1
O0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
This is a 2-to-4 decoder
Page B-9 shows the truth table for a 3-to-8 decoder
33
Decoder: implementation with gates
Decoder
A
B
C
D
=
=
=
=
n bit input value and 2^n outputs
X•Y
X•Y
X•Y
X•Y
X
Y
X
Y
A
B
C
D
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
A
B
C
D
34
N input MUX using a decoder
• Example in lecture
35
Implementing Combinatorial Logic
• PLA (Programming Logic Array)
– A direct implementation of sum of products
form pla.html (thanks to:
www.cs.umd.edu/class/spring2003/cmsc311/Notes/C
omb/pla.html)
• ROM (Read Only Memory)
– Interpret the truth table as fixed values stored
in memory
• Using logic gate chips (74LS…)
36
74LS Series
• Chips contain several logic gates
32
08
04
13
12
11
10
9
8
5
6
3
4
1
2
1
2
3
1
2
3
4
5
6
4
5
6
9
10
8
9
10
8
12
13
11
12
13
11
SN 74LS04 Hex
SN 74LS08 Quad
inverter gate
2-input AND gate
SN 74LS32 Quad
2-input OR gate
37
Fig 5.28 (added for reference)
38
ALU Symbol
• Note that it’s combinational logic
39
Building a 1-bit ALU
• ALU = Arithmetic Logic Unit
40
Building a 32-bit ALU
41
Implementing “SUB”
42
Implementing “NAND”/”NOR”
43
Implementing “SLT”
44
Implementing “SLT”, cont’d
45
Supporting “BEQ”/”BNE”
• Need a “zero-detector”
46
ALU Symbol
• Note that it’s a combinational logic
47
…
inputs
…
Sequential Logic
current
state
outputs
next
state
clock
48
RS Latch
• Note that there are feedbacks!
49
RS Latch, cont’d
0
1
0
1
1
0
• When R=0, S=1
50
RS Latch, cont’d
1
0
1
0
0
1
• When R=1, S=0
51
RS Latch, cont’d
0
0
1
0
0
1
• When R=0, S=0, and Q was 0
52
RS Latch, cont’d
0
1
0
1
0
0
• When R=0, S=0, and Q was 1
53
RS Latch, cont’d
1
1
• What happens if R=S=1?
54
D Latch
• Note that we have an R-S latch as a back-end
55
D Latch, cont’d
R
S
• Note that S, R inputs always get inverted input of D when
C=1
• When C=0, S=R=0, remembering the previous value
56
D Latch, cont’d
R
S
C
D
Q(t)
0
0
Q(t-1)
0
1
Q(t-1)
1
0
0
1
1
1
57
D Latch, cont’d
D
Q
D Latch
C
Q’
58
D Flip-Flop (D-FF)
• Two D latches are cascaded, with opposite clock
59
D Flip-Flop, cont’d
D
Q
D-FF
C
Q’
60
Register File Implementation we’ll
return to this in appendix B
61
Reg. File Impl., cont’d we’ll return to
this in appendix B
1
1
0
1
1
0
1
0x11223344
0
0
0
0
0x11223344
62
To Summarize…
• In digital logic, transistors are used as
simple switches
• Logic gate is an abstraction of multiple
transistor network
• A combinational logic block has inputs and
outputs that depend on the current inputs
• A sequential logic block is composed of
some combinational logic and memory
that keeps the current state
63
To Summarize…, cont’d
• Boolean algebra provides theory for digital
logic
• Combinational logic can be implemented
using PLA (and many other methods)
• An ALU for MIPS architecture has been
built!
64
To Summarize…, cont’d
• Flip-flops were used as a memory element
• An FSM can be implemented using FFs
and some combinational logic
65