Transcript
Transistor: Building Block of Computers Microprocessors contain millions of transistors • • • •
Chapter 3 Digital Logic Structures
Intel Pentium 4 (2000): 48 million IBM PowerPC 750FX (2002): 38 million IBM PowerPC G5 (2003): 58 million Intel Core Duo 2 (2006): 291 million (192+ million in cache alone)
Logically, each transistor acts as a switch Combined to implement logic functions • AND, OR, NOT
Combined to build higher-level structures • Adder, multiplexer, decoder, register, … Based on slides © McGraw-Hill Additional material © 2004/2005/2006 Lewis/Martin
Combined to build processor • LC-3 CSE 240
3-2
How do we represent data in a computer? At the lowest level, a computer has electronic “plumbing” • Operates by controlling the flow of electrons
Easy to recognize two conditions: 1. Presence of a voltage – we’ll call this state “1” 2. Absence of a voltage – we’ll call this state “0”
Computer use transistors as switches to manipulate bits • Before transistors: tubes, electro-mechanical relays (pre 1950s) • Mechanical adders (punch cards, gears) as far back as mid-1600s
Before describing transistors, we present an analogy… CSE 240
3-3
CSE 240
3-4
A Transistor Analogy: Computing with Air
Pressure Inverter
Use air pressure to encode values
High
• High pressure represents a “1” (blow) • Low pressure represents a “0” (suck)
Valve can allow or disallow the flow of air P-Valve
• Two types of valves
N-Valve Low
P-Valve
In
(Off)
Low
(On)
(On)
High
(Off)
Out N-Valve
hole High
Low 3-5
CSE 240
Pressure Inverter (Low to High)
3-6
CSE 240
Pressure Inverter
High
High
P-Valve Low
P-Valve
High N-Valve
N-Valve
Low CSE 240
Low 3-7
CSE 240
3-8
Pressure Inverter (High to Low)
Analogy Explained Pressure differential ! electrical potential (voltage)
High
• Air molecules ! electrons • High pressure ! high voltage • Low pressure ! low voltage
P-Valve Air flow ! electrical current High
Low
• • • •
N-Valve
Low
Pipes ! wires Air only flows from high to low pressure Electrons only flow from high to low voltage Flow only occurs when changing from 1 to 0 or 0 to 1
Valve ! transistor • The transistor: one of the century’s most important inventions 3-9
CSE 240
Transistors as Switches Two types • N-type • P-type
Properties • • • •
Solid state (no moving parts) Reliable (low failure rate) Small (90nm channel length) Fast (<0.1ns switch latency)
CSE 240
3-10
MOS + FET N-Valve
N-MOSFET
P-Valve
P-MOSFET
gate insulator source channel drain (cross-section view of a MOSFET) MOS: three materials needed to make a transistor • Metal (Al, W, Cu): conductor • Oxide (SiO2): insulator • Semiconductor (doped Si): conducts under certain conditions
FET: field effect (the mechanism) transistor • Voltage on gate: current flows source to drain (transistor on) • No voltage on gate: no current (transistor off)
Recall, two types of MOSFET: n and p CSE 240
3-11
CSE 240
3-12
N-type MOS Transistor
P-type MOS Transistor P-type is complementary to n-type
• When Gate has positive voltage, short circuit between #1 and #2 (switch closed) • When Gate has zero voltage, open circuit between #1 and #2 (switch open)
• When Gate has positive voltage, open circuit between #1 and #2 (switch open) • When Gate has zero voltage, short circuit between #1 and #2 (switch closed)
Gate = 1
Gate = 1
Terminal #1 connected to POWER (in this example, +2.9V)
Gate = 0
Terminal #2 connected to GROUND (0V).
3-13
CSE 240
Inverter (NOT Gate)
Gate = 0
CSE 240
3-14
CMOS Circuit Inverter is an example of Complementary MOS (CMOS) Uses both n-type and p-type MOS transistors
Power
• p-type !Attached to POWER (high voltage) !Pulls output voltage UP when input is zero • n-type !Attached to GROUND (low voltage) !Pulls output voltage DOWN when input is one
Truth table Ground
CSE 240
In
Out
0
1
1
0
For all inputs, make sure that output is either connected to GROUND or to POWER, but not both! (why?)
3-15
CSE 240
3-16
NAND Gate (NOT-AND)
AND Gate
Power
Power
Ground CSE 240
A
B
C
0
0
1
0
1
1
1
0
1
1
1
0
Note: Parallel structure on top, serial on bottom.
Ground 3-17
NOR Gate (NOT-OR)
Ground CSE 240
C
0
0
1
0
1
0
1
0
0
1
1
0
Note: Serial structure on top, parallel on bottom.
Ground 3-19
C
0
0
0
0
1
0
1
0
0
1
1
1
Add inverter to NAND. 3-18
Power
Power
B
B
CSE 240
OR Gate
A
A
CSE 240
A
B
C
0
0
0
0
1
1
1
0
1
1
1
1
Add inverter to NOR. 3-20
Basic Gates
More than 2 Inputs?
From Now On… Gates
AND/OR can take any number of inputs
• Covered transistors mostly so that you know they exist • Note: “Logic Gate” not related to “Gate” of transistors
• AND = 1 if all inputs are 1 • OR = 1 if any input is 1 • Similar for NAND/NOR
Will study implementation in terms of gates
Implementation
• Circuits that implement Boolean functions NOT/INV
NAND
AND
• Multiple two-input gates or single CMOS circuit
NOR
OR
More complicated gates from transistors possible • XOR, Multiple-input AND-OR-Invert (AOI) gates 3-21
CSE 240
CSE 240
Visual Shorthand for Multi-bit Gates
Shorthand for Inverting Signals
Use a cross-hatch mark to group wires
Invert a signal by adding either
• Example: calculate the AND of a pair of 4-bit numbers • A3 is “high-order” or “most-significant” bit • If “A” is 1000, then A3 = 1, A2 = 0, A1 = 0, A0 = 0
CSE 240
A0 B0
Out0
A1 B1
Out1
A2 B2
Out2
A3 B3
Out3
A B
4
3-22
• A before/after a gate • A “bar” over letter
4
Out
A B
A AND B
A B
A AND B
A B
A OR B
4
3-23
CSE 240
3-24
Logical Completeness
Logical Completeness via PLAs
AND, OR, NOT can implement ANY truth table
Any truth table as a Programmable Logic Array (PLA)
A
B Cin S
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
• Traditionally a grid of AND and OR gates • Configurable by removing wires
A B Cin
1. AND combinations that yield a "1" in the truth table S
2. OR the results of the AND gates
3-25
CSE 240
Single-output custom PLA (as on previous slide): • One AND gate per row with “1” in output in truth table • Maximum number of AND gates: 2n for n inputs • One OR gate
Multiple-output custom PLA: • Build multiple single-output PLAs • Share AND gates “in common” • One OR gate per output column in truth table CSE 240
3-26
DeMorgan's Law
Summary
Converting AND to OR (with some help from NOT) Consider the following gate: To convert AND to OR
MOS transistors: switches to implement logic functions
A AND B
=
A OR B
(or vice versa), invert inputs and output. A AND B
A B A B A AND B
A OR B
A AND B
0 0 1 1
1
0
0 1 1 0
0
1
1 0 0 1
0
1
1 1 0 0
0
1
CSE 240
=
• n-type: connect to GROUND, turn on (with 1) to pull down to 0 • p-type: connect to POWER, turn on (with 0) to pull up to 1
Basic gates: NOT, NOR, NAND • Logic functions are usually expressed with AND, OR, and NOT • Universal: any truth table to simple gates (via a PLA)
DeMorgan's Law A AND B
Why might this be useful?
=
A OR B
• Convert AND to OR (and vice versa) by inverting inputs/output
Ok, we now have simple logic gates • Next up: how do we combine them into something useful? 3-27
CSE 240
3-28
AND, OR, NOT Gates: What Good Are They? Last time: • Transistors and gates • Can implement any logical function using gates (using PLAs)
Chapter 3 Digital Logic Structures
Today: • We’ll use gates to create some building blocks of a processor • One goal: automate binary arithmetic from Chapter 2 • Continuing on our bottom-up journey
Next time: • Storing bits (memory) • Circuits with “state”
Based on slides © McGraw-Hill Additional material © 2004/2005/2006 Lewis/Martin
3-30
CSE 240
Incrementer Let’s create a incrementer
A
16
16
+1
One-bit Incrementer S
Implement a single-column of an incrementer
• Input: A (as a 16-bit 2’s complement integer) • Output: A+1 (also as a 16-bit 2’s complement integer)
CarryInn
00001011 +00000001 00001100
Approach #1 (impractical): • Use PLA-like techniques to implement circuit • Problem: 216 or 65536 rows, 16 output columns • In theory, possible; in practice, intractable
An
An Cin
An
Approach#2 (pragmatic): • Create a 1-bit incrementer circuit • Replicate it 16 times
1
1
+1
Sn
CarryOutn
Cin Sn Cout
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
S
Cout CSE 240
3-31
CSE 240
3-32
Aside: XOR
N-bit Incrementer Chain N 1-bit incrementers together
An
Cin Sn Cout
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
CarryIn0 A
S
A0
1
CarryIn1 A1
Cout
Cin
4-bit example
A Cin
XOR A
A2
1
Cin
A3 3-33
1
1
S1
CarryOut1 1
+1
CarryIn3
S0
CarryOut0
+1
CarryIn2
S
CSE 240
1
1
+1
S2
…but how do we correctly handle the least-significant bit?
CarryOut2 1
+1
S3
CarryOut3
3-34
CSE 240
N-bit Incrementer, continued
Adder
How do we handle the least-significant bit? 1
Conceptually similar to an incrementer
00001011 +00000001 00001100 00001011 +00000000 00001100
CarryIn0 A0
1
+1
CarryIn1 A1
Cin = 1
1
00001011 +00110011 00111100
S0
CarryOut0 1
+1
CarryIn2 A2
No longer needed; implicitly encoded with Cin
1
1
S1
An Bn
1 1
CarryInn 1
Add
Sn
CarryOutn
CarryOut1 1
+1
S2
CarryOut2
...
CSE 240
• Build a one-bit slice, replicate n times
3-35
CSE 240
3-36
One-bit Adder Add two bits and carry-in produce one-bit sum and carry-out
An Bn
1 1
A B Cin S Cout 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
CSE 240
1
Add
CarryIn
CarryIn
Sn
16
A0
CarryOutn
CarryIn0
CarryIn1
CarryIn2
3-37
S
CarryOut: useful for detecting overflow
CarryOut1 S2
CarryIn: assumed to be zero if not present
CarryOut2
3-38
CSE 240
Subtracter
Full disclosure:
Build a subtracter from an adder
Our adder: Ripple-carry adder No one (sane) actually uses ripple-carry adders Why? way too slow Latency proportional to n
• Calculate A - B = A + -B • Negate B • Recall -B = NOT(B) + 1
Approach#1:
We can do better • • • • •
16
CarryOut
Aside: Efficient Adders • • • •
+
16
S1
Add
B2
B
CarryOut0
Add
B1 A2
S0
Add
B0 A1
A
...
0 0
N-bit Adder
CarryInn
Approach#2: 1
CarryIn
Many ways to create adders with latency proportional to log2(n) In theory: constant latency (build a big PLA) In practice: too much hardware, too many high-degree gates “Constant factor” matters, too More on this topic in CSE371
16
16
A B
16 16
16
16
+1
A S B
CarryIn 16
16
16
S
Now, let’s create an adder/subtracter CSE 240
3-39
CSE 240
3-40
…But First, The Multiplexer (MUX)
The Multiplexer (MUX)
Selector/Chooser of signals
In general
• Multi-way switch
2-to-1 Mux 0
• N select bits chooses from 2N inputs • An incredibly useful building block
4-to-1 Mux
1
00
01
2
10
2
11
2
Multi-bit muxes
2
• Can switch an entire “bus” or group of signals • Switch n-bits with n muxes with the same select bits
S
16
S
16
A
O
16
3-41
CSE 240
Adder/Subtracter - Approach #1 Adder
Adder/Subtracter - Approach #2
CarryIn
1 16
16
B
16
A B
1
16
CarryIn 16
16
Subtracter
CarryIn
A
S
16
Adder
A S
B
CarryOut 16
3-42
CSE 240
Subtracter
16
A
16
16
B
B
2
16 16
16
S
CarryIn
A B
16 16
16
S
CarryOut
Adder/Subtracter
Adder/Subtracter
Add/Sub
16 16
Add/Sub
1
16
1
CarryIn
16
A
S
B
16
16
16 16
S
16 CSE 240
3-43
CSE 240
3-44
Ok, So We Can Add and Subtract Other arithmetic operations similar • Even floating point operations
Chapter 3 Digital Logic Structures
We can calculate; but we can’t remember • Next time: storage and memory • After that: simple “state machines” • After that: a simple processor
Remember: readings, quizzes, and homework • Homework 2 due Friday
CSE 240
Based on slides © McGraw-Hill Additional material © 2004/2005/2006 Lewis/Martin
3-45
Combinational vs. Sequential Logic
Storage - Cross-Coupled Inverters
Combinational Circuit
Cross-coupled inverters (INV) gates
• Always gives the same output for a given set of inputs !For example, adder always generates sum and carry, regardless of previous inputs
• Holds value Q and Q’ (Q’ is the same as Q)
Q’
Sequential Circuit • Stores information • Output depends on stored information (state) plus input !Given input might produce different outputs, depending on stored information • Example: ticket counter !Advances when you push the button !Output depends on previous state • Useful for building “memory” elements and “state machines” CSE 240
3-47
1
0
Q
Q’
0
1
Q
• Read: get value from either Q or Q’
Maintains its “state”, but how do we change the state? • Write: Option #1: put opposite values on Q and Q’ simultaneously !Requires “analog” overdriving of Q and Q’
CSE 240
3-48
Storage - NANDs
Storage - Cross-Coupled NANDs (R-S Latch)
Option #2: “Digital” alternative for changing state Write: change Q to one Maintains state even after S = 1 1 0 1 S S S 1 0Q 0 1Q 0 1Q
Write either a zero or one • When S=1 and R=1, “quiescent” state; maintains value
S
R
1
0Q
1
R
0
1
R
CSE 240
R
0Q
S
0
Maintains state even after R = 1 3-49
CSE 240
R
R
Add logic to an R-S latch
1 0Q
0
3-50
• Create a better interface
Two inputs: D (data) and WE (write enable) • When WE = 1, latch is set to value of D !S = NOT(D), R = D • When WE = 0, latch continues to hold previous value !S = R = 1 • Does not allow S=0, R=0 case to occur
0 1
1Q
0
• Does S or R go to one first? !If they change at the same time? !Oscillation or meta-stability can result • Let’s make sure this can never happen… CSE 240
1
1
1
What happens with S=0 and R=0? • Short answer: bad things • Long answer: value stored will depend on timing on circuit
S
1Q
0
1
Gated D-Latch
R
0Q
1
1
Storage - Cross-Coupled NANDs (R-S Latch)
S
1
• When S=0 and R=1, state changes to one (“set”) • When S=1 and R=0, state changes to zero (“reset” or “clear”)
Write: change Q to zero 1Q
S
1Q
0
R
0
1
1
D
WE
0
1
Q
0 1
3-51
CSE 240
3-52
Register
Aside: More on Representing Multi-bit Values
A register stores a multi-bit value
Number bits from right (0) to left (n-1)
• A collection of D-latches, controlled by a common WE • When WE=1, n-bit value D is written to register
• Just a convention -- could be left to right, but must be consistent
Use brackets to denote range: D[l:r] denotes bit l to bit r, from left to right
WE
15
Q0
D0
D
D1
3
3
D
8
A[14:9] = 101001
Q
0
A[2:0] = 101 16
May also see A<14:9> CSE 240
4
A = 0101 0011 0101 0101
WE
Q1
12
Q1
D2
• Especially in hardware block diagrams. 3-53
Let’s Try to Build a Counter
[14:9]
6
3-54
CSE 240
A clock controls when registers are “updated” 3
Cnt
3
What’s Missing? The Clock
1 3
[2:0]
• Oscillating global signal with fixed period • Typical clock frequencies today: a couple of gigahertz
3
+1
“1” “0”
How quickly will this count?
One Cycle
• Timing dependent
• Corresponds to <1 nanosecond between one rise and the next • Generated on-chip by special circuitry (for example, oscillating ring of inverters)
Will it even work? • Probably not • D-latches are “transparent” !Allows next input to immediately flow to output !Outputs will never be “stable” CSE 240
time!
3-55
CSE 240
3-56
clock
Let’s Try Again: a Counter
Example of Incorrect Operation Initial state: 0102
Clock 3
D latch
3
3
1
WE 0
+1
1
D 0 A0 latch
Solves half the problem
1
• Controls the rate of updates
D 1 A1 latch
Remaining problem
0
• When clock=1, same problem • D-latches are still transparent
D 0 A2 latch
3-57
CSE 240
S +1 1 0 0
S +1 1 1
0
S +1 0 2
3-58
CSE 240
clock
clock
Example of Incorrect Operation
Example of Incorrect Operation
Set WE (Write Enable) to 1
D latches write new value: 0112 Goal: 1002
1
WE 1 1
D 0 A0 latch
1
D 1 A1 latch
0
D 0 A2 latch
CSE 240
1
WE 1
S +1 1 0
1
D 1 A0 latch
0
S +1 1 1
1
D 1 A1 latch
0
S +1 0 2
0
D 0 A2 latch
3-59
CSE 240
S +1 1 0 0
S +1 1 1
0
S +1 0 2
3-60
clock
clock
Example of Incorrect Operation
Example of Incorrect Operation
Incrementer calculates 1st bit
Incrementer calculates 2nd bit, 1st bit latched 1
WE 1 0
D 1 A0 latch
1
D 1 A1 latch
0
D 0 A2 latch
S +1 0 0
0
D 0 A0 latch
1
S +1 1 1
0
D 1 A1 latch
0
S +1 0 2
0
D 0 A2 latch
3-61
CSE 240
1
WE 1
S +1 0 0 1
S +1 0 1
1
S +1 0 2
3-62
CSE 240
clock
clock
Example of Incorrect Operation
Example of Incorrect Operation
Incrementer calculates 3rd bit, 2nd bit latched, 1st bit re-calculated
1st and 3rd bits latched value is: 1012 (not the desired 1002)
1
WE 1
1
D 0 A0 latch
0
D 0 A1 latch
1
D 0 A2 latch
CSE 240
1
WE 1
S +1 1 0
1
D 1 A0 latch
0
S +1 0 1
0
D 0 A1 latch
1
S +1 1 2
1
D 1 A2 latch
3-63
CSE 240
S +1 1 0 0
S +1 0 1
1
S +1 1 2
3-64
clock
Correct Operation
Correct Operation
Additional D-latches, WE is NOT(Clock) and Clock Initial state: 0102
Clock switches to 1, 2nd latch WE = 1
Clock 0
Clock 1
1
1
D 1 Q0 latch
1
D 1 Q1 latch
0
D 0 Q2 latch
D 0 A0 latch
D 1 A1 latch
D 0 A2 latch
1
S +1 1 0
D 1 Q0 latch
0
1
S +1 1 1
D 1 Q1 latch
0
0
S +1 0 2
D 0 Q2 latch
3-65
CSE 240
1
D 0 A0 latch
D 1 A1 latch
D 0 A2 latch
D latches write new value: 0112 Goal: 1002
Incrementer begins calculation
Clock 1
Clock 1
1
D 1 Q0 latch
D 1 Q1 latch
D 0 Q2 latch
CSE 240
0
S +1 0 2
clock
Correct Operation
0
S +1 1 1
3-66
Correct Operation
1
0
CSE 240
clock
1
S +1 1 0
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
1
0
S +1 1 0
D 1 Q0 latch
0
1
S +1 1 1
D 1 Q1 latch
0
0
S +1 0 2
D 0 Q2 latch
3-67
CSE 240
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
S +1 0 0 1
S +1 1 1
0
S +1 0 2 3-68
clock
clock
Correct Operation
Correct Operation
Incrementer calculates 2nd bit, First bit not written to latch
Incrementer calculates 3rd bit, 1st, 2nd bits not written to latch
Clock 1
Clock 1
1
0
D 1 Q0 latch
0
D 1 Q1 latch
0
D 0 Q2 latch
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
0
S +1 0 0
D 1 Q0 latch
1
0
S +1 0 1
D 1 Q1 latch
1
1
S +1 0 2
D 0 Q2 latch
3-69
CSE 240
1
Correct value ready to latch (1002), circuit quiescent
Clock changes to 0
Clock 1
latch
Clock 0
1
D 1 Q0 latch
D 1 Q1 latch
D 0 Q2 latch
CSE 240
D 0 A2
S +1 0 1
1
S +1 1 2
clock
Correct Operation
1
latch
1
3-70
Correct Operation
0
D 1 A1
S +1 0 0
CSE 240
clock
0
D 1 A0 latch
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
1
0
S +1 0 0
D 1 Q0 latch
1
0
S +1 0 1
D 1 Q1 latch
1
1
S +1 1 2
D 0 Q2 latch
3-71
CSE 240
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
S +1 0 0 1
S +1 0 1
1
S +1 1 2 3-72
clock
clock
Correct Operation
Correct Operation
2nd set of latches write correct value, circuit quiescent
Clock changes back to 1, next increment begins
Clock 0
Clock 1
1
0
D 0 Q0 latch
0
D 0 Q1 latch
1
D 1 Q2 latch
D 1 A0 latch
D 1 A1 latch
D 0 A2 latch
1
0
S +1 0 0
D 0 Q0
D 0 A0
latch
1
0
S +1 0 1
D 0 Q1
1
S +1 1 2 3-73
S +1 0 1
latch
D 1 Q2
1
D 1 A2
latch
CSE 240
1
D 0 A1
latch
1
S +1 0 0
latch
S +1 1 2
latch
3-74
CSE 240
clock
D Flip-Flop (or master-slave flip-flop)
D Flip-Flop - Phase 1
D Flip-Flop is a pair of D latches
Latch #1 D
• Stupid name, but it stuck • Isolate next state from current state
Latch #1 D
Qinter
Latch #2 Qinter
Q
Latch #2 0
Q
1 1
Clock Phase 1 Two phases:
• Clock = 1 • Latch 1: writing disabled (output is stable Qinter) • Latch 2: writing enabled (Q = Qinter)
Clock
• Clock = 1, Clock = 0 CSE 240
3-75
CSE 240
3-76
clock
D Flip-Flop - Phase 2
Latches & Flip-Flops
Latch #2
Latch #1 D
Latches
Qinter
1
Q
• “level triggered” (high or low) • “transparent”
Flip-Flops
0
• “edge triggered” (rising/positive edge or falling/negative edge) • “non-transparent” or “opaque” or just “latch” (!!!)
0
Clock
Phase 2
Flip-Flops have WE (write enable) signals, too
• Clock = 0 • Latch 1: writing enabled (Qinter = D) • Latch 2: writing disabled (output is stable Q)
• Uses a gate to suppress the rising (or falling) edge of clock • Once internalized in FF, no need to manipulate clock with logic • Otherwise manipulating clock with logic usually a bad ideaTM
Back to Phase 1 • Q becomes Qinter 3-77
CSE 240
3-78
CSE 240
Working Counter
Memory
Use a clocked register (made of D flip-flops) 1 Clock WE
Now that we know how to store bits, we can build a memory – a logical k by m array of stored bits
3
3
D-ff
3
+1
Address Space: number of locations
More simply • If WE = 1 assumed if WE is not present 3
3
D-ff
(usually a power of 2) 3
• • •
+1
Addressability: number of bits per location
Use WE input for conditional counter (stop watch) CSE 240
k = 2n locations
(e.g., byte-addressable)
3-79
CSE 240
m bits 3-80
Memory Interface A Din
22 by 3-bit memory Read operation
n
A
m
2
WE 3
3
3
Decoder
D0
Memory 3 3 by m-bit) D1
(2n
3
m
3
3
22 or 4 registers
3
3
Dout
3
D2 3
D3
CSE 240
3
D1
Dout
D2 3
3
D0
3
3-81
CSE 240
The Decoder
22 by 3-bit memory
n inputs, 2n outputs
Write operation A
• Exactly one output is 1 for each possible input pattern
3
D3
Din
3-82
2 3
WE 3
3
Decoder
D0
2-bit decoder
3
3
D1 3
3
Dout
3
D2 3 CSE 240
3-83
CSE 240
3
D3
3-84
22 by 3-bit memory - Multiple “Ports”
22 by 3-bit memory - Multiple Read Ports 2
Independent Read/Write AR DW WE AW
AR1 2 AR2
2 3
DW 2
3
WE AW
3
3
2
3
3
3
D1 3
3
DR
3
3
3
3
address
word select
3
DR1 DR2
3
3
3-85
An Efficient 22 by 3-bit Memory - Single Port word WE
3
D2
D3
CSE 240
3
D1
D2 3
3
D0
Decoder
Decoder
D0
3
D3
CSE 240
3-86
More Memory Details
input bits
This is still not the way actual memory is implemented • Real memory: fewer transistors, denser, relies on analog properties
write enable
But the logical structure is similar • Address decoder • Word select line, word write enable • Bit line
latch (not flip-flop)
Two basic kinds of RAM (Random Access Memory) Static RAM (SRAM) - 6 transistors per bit • Fast, maintains data as long as power applied
Dynamic RAM (DRAM) - 1 transistor per bit • Denser but slower, destructive read, bit storage decays – must be periodically refreshed (like a leaky balloon)
address decoder CSE 240
output bits
mux
3-87
CSE 240
Also, non-volatile memories: ROM, PROM, flash, …
3-88
State Machine
Combinational vs. Sequential
Another type of sequential circuit
Two types of “combination” locks
• Combines combinational logic with storage • “Remembers” state, and changes output (and state) based on inputs and current state 25
4 1 8 4
State Machine
Inputs
Combinational Logic Circuit
Outputs
Combinational Success depends only on the values, not the order in which they are set.
Storage Elements
CSE 240
3-89
20
30
15
5 10
Sequential Success depends on the sequence of values (e.g, R-13, L-22, R-3).
CSE 240
3-90
State
State of Sequential Lock
The state of system is snapshot of all relevant elements of system at moment snapshot is taken
Our lock example has four different states, labeled A-D: A: The lock is not open, and no relevant operations have been performed B:The lock is not open, and the user has completed the R-13 operation C:The lock is not open, and the user has completed R-13, followed by L-22 D:The lock is open
Examples • The state of a basketball game can be represented by the scoreboard !Number of points, time remaining, possession, etc. • The state of a tic-tac-toe game can be represented by the placement of X’s and O’s on the board (and turn)
CSE 240
3-91
CSE 240
3-92
Sequential Lock State Diagram
Finite State Machine A description of a system with the following components:
Shows states and actions that cause a transition between states 1. 2. 3. 4. 5.
A finite number of states A finite number of external inputs A finite number of external outputs An explicit specification of all state transitions An explicit specification of what determines each external output value Often described by a state diagram
(open)
• Inputs trigger state transitions • Outputs are associated with each state (or with each transition) 3-93
CSE 240
CSE 240
Implementing a Finite State Machine
Storage
Combinational logic
Master-slave flip-flop stores one state bit
3-94
• Determine outputs and next state.
Storage elements
Number of storage elements (flip-flops)
• Maintain state representation.
• Determined by number of states (and representation of states)
State Machine
Inputs
Clock
CSE 240
Combinational Logic Circuit
Examples • Sequential lock !Four states – two bits • Basketball scoreboard !8 bits for each score, 5 bits for minutes, 6 bits for seconds, 1 bit for possession arrow, 1 bit for half, …
Outputs
Storage Elements
3-95
CSE 240
3-96
Complete Example
Traffic Sign State Diagram
A blinking traffic sign • • • • •
No lights on 1 & 2 on 1, 2, 3, & 4 on 1, 2, 3, 4, & 5 on (repeat as long as switch is turned on)
3 4
1
5
Switch on
2
Switch off
DANGER MOVE RIGHT
State bit S1
3-97
CSE 240
Traffic Sign State Diagram: State 00
CSE 240
Transition on each clock cycle.
CSE 240
State bit S0
Transition on each clock cycle.
Outputs
3-98
Traffic Sign State Diagram: State 01
3-99
CSE 240
Transition on each clock cycle.
3-100
Traffic Sign State Diagram: State 10
CSE 240
Transition on each clock cycle.
Traffic Sign State Diagram: State 11
3-101
Traffic Sign State Diagram: State 00
CSE 240
3-102
Transition on each clock cycle.
Traffic Sign Truth Tables Outputs (depend only on state: S1S0)
Next State: S1’S0’ (depend on state and input) Switch
Lights 1 and 2 Lights 3 and 4 Light 5
CSE 240
Transition on each clock cycle.
3-103
Don’t care (1 or 0)
In
S1
S0 S1 ’ S0 ’
0
X
X
0
0
1
0
0
0
1
S1
S0
Z
Y
X
0
0
0
0
0
1
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
1
CSE 240
Whenever In=0, next state is 00.
3-104
Traffic Sign Logic
Programmable State Machines What if we want to change the pattern of the sign? • An alternative state machine implementation • Use a memory indexed by state number
Input
1
S1 ’ S0 S1
23 by 2-bit
[2] 3
2
2
[1:0]
2
3
’
22
State
Master-slave flip-flop
S0 3-105
CSE 240
by 3-bit 2
CSE 240
Output (Z, Y, X) S
X/Y/Z
00
000
01
100
10
110
11
111
In/S1/S0
S
000
00
001
00
010
00
011
00
100
01
101
10
110
11
111
00
Programmable State Machines
From Logic to Data Path
Change to a two-state pattern:
The data path of a computer is all the logic used to process information.
• All off • All on
Input
1
State: 00
23 by 2-bit
[2] 3
2
State: 10
2
[1:0]
2
3
22 by 3-bit
State
CSE 240
State: 00
2
Output (Z, Y, X) S
Z/Y/Z
00
000
01
--
10
111
11
--
In/S1/S0
S
000
00
001
--
010
00
011
--
100
10
101
--
110
00
111
--
3-106
• See the data path of the LC-3 on next slide
Combinational Logic • Decoders -- convert instructions into control signals • Multiplexers -- select inputs and outputs • ALU (Arithmetic and Logic Unit) -- operations on data
Sequential Logic • State machine -- coordinate control signals and data movement • Registers and latches -- storage elements
3-107
CSE 240
3-108
LC-3 Data Path
Looking Forward… We’ve touched on basic digital logic
Combinational Logic
• • • •
Storage
Transistors Gates Storage (latches, flip-flops, memory) State machines
Built some simple circuits • • • •
State Machine
Incrementer, adder, subtracter, adder/subtracter Counter (consisting of register and incrementer) Hard-coded traffic sign state machine Programmable traffic sign state machine
Up next: a computer as a (simple?) state machine CSE 240
3-109
Next Time Topic • The von Neumann Model
Readings • Chapter 4.0 - 4.2
Online quiz • You know the drill!
CSE 240
3-111
CSE 240
3-110
