Welcome to Computer Organization and Assembly!
Sequential Logic,
Registers, and Clocking
CS/COE 0447
Jarrett Billingsley
1
Class announcements
this is the only class this week!
another mini-break wheeeeee
CS447
2
2
Combinational Logic
Or “combinatorial,” both are used
CS447
3
Smooshing bits together to get other bits
all the logic we’ve talked about so far is combinational logic.
you give it some combination of inputs, and you get an output.
CS447
4
+
gates, muxes, adders… these are all combinational.
for combinational logic, the outputs only depend on the current inputs.
– they’re like a mathematical function. they just compute something and give an answer.
– for each combination of inputs, there is exactly one possible output. 3 + 4 is always 7.
4
Calculators and computers
both calculators and computers do arithmetic on bits.
but what can’t this calculator do that computers can?
CS447
5
it can’t run programs.
and programs are a sequence of steps.
how do you do a sequence of steps with combinational logic?
– programmable calculators are just tiny computers. that’s why I have to keep saying “four-function calculator.”
5
You, uh, can’t.
if you put a certain input into a combinational circuit…
the output will never change.
so you can’t get a “sequence” of things coming out.
well, the output changes when we change the inputs.
and when electrical signals move through it (due to gate delay).
remember the ripple carry adder?
but that’s a bad thing, right? we got strange, incorrect answers for a while until it “settled” on the final answer.
surely we couldn’t… use that weirdness for something useful.
CS447
6
6
Using that weirdness for something useful
CS447
7
The RS Latch (or SR latch)
here’s a confusing circuit.
CS447
8
A B Y
0 0 1
0 1 0
1 0 0
1 1 0
NOR
what’s the logic formula for Q?
this doesn’t make sense from a combinational viewpoint. how can a gate’s input depend on its own output?
well, let’s build it in Logisim. what’s the worst that could happen, right?
A NOR B = ¬(A B)
Q = ¬(R ∨ ¬(S ∨ ¬(R ∨ ¬(S ∨ ¬(R …
R
S
Q
(see RS_latch.circ)
– we tend to use Q as the output of sequential circuits and Y for combinational
– remember, Logisim doesn’t simulate gates catching fire. thankfully.
8
Whaaaat is going on here?
when you build it, it starts off looking angry, but…
CS447
9
poking R or S makes it “settle” into one state or another.
and you can switch between states, too.
it remembers.
this is one kind of memory: a circuit that remembers information.
and memory is the basis of sequential circuits.
– this is just one kind though. there are many
9
Why does it work? (animated)
because of gate delay.
CS447
10
Q
R
S
we say this circuit is bistable – it has two (bi) states where its output is stable (steady).
A B Y
0 0 1
0 1 0
1 0 0
1 1 0
NOR
it’s like a light switch: you can’t really put it in the middle.
– it’s called “gate delay” (or “propagation delay”)
– each gate is keeping the other gate stuck at a certain value
– like a light switch, it has two “low-energy” states and a “hill” between them that takes some energy to cross
10
But it can break… (animated)
CS447
11
Q
R
S
if we input 1 for both R and S…
that’s stable. but the problem is when we input 0 on both now
which input went to 0 first?
A B Y
0 0 1
0 1 0
1 0 0
1 1 0
NOR
if R went to 0 first, then Q = 1
if S went to 0 first, then Q = 0
if they both went to 0 at the exact same time, it will oscillate (flip back and forth)!
– oscillation is a real problem, but due to unavoidable imperfections in real life, the oscillation is self-damping and will stop after a short time
– but what state it settles into after it stops is still completely unpredictable.
11
So how do we fix it?
wellllllll uhhhhhhhhhhhhhhhh we actually can’t, not 100% 💦
but we can reduce the chance of it happening so much that we don’t really have to worry about it
anyway, let me wave my hands and present to you: the flip flop.
CS447
12
this is made up of a couple RS latches and some other gates.
it stores a single bit, but in a more robust, non-breaky way.
D
Q
en
data in
data out
???
???
oh boy, question marks! that means we get to learn more stuff!
– see D_latch.circ for an intermediate step (an RS latch with some stuff on it), and D_flipflop.circ for the flip flop itself (two chained D latches).
12
Time
CS447
13
13
Keep your eye on the prize
sequential circuits can perform sequences of operations.
which means those things happen over time.
consider a CPU.
CS447
14
lw t0, x
add s0, s0, t0
sw s0, x2
the instructions happen one after another. but how? who says “it’s time to run the next instruction?”
we need something to keep track of time… like… I dunno…
a clock?
– TICK TOCK
14
Tick tock
the clock signal says when we move onto “the next step.”
it keeps all the sequential circuits in sync.
(combinational circuits don’t need or use the clock.)
CS447
15
1
0
time
rising edge
falling edge
clock edges are when it changes between 0 and 1.
the clock switches between 0 and 1 in a steady rhythm.
we’ll use rising edges for this class.
15
All our hearts beating as one
no matter how many memory components there are in your circuit…
you will always have exactly one clock component.
CS447
16
Wiring > Clock makes it:
Simulate > Ticks Enabled makes it tick continuously.
you can also Ctrl/Cmd+T to make it tick once.
now you can hook this up to every component which needs it. this is a great use for tunnels!
– and you can change how fast those automatic ticks happen in the Simulate menu too.
16
Great! So what? (animated)
how does the clock actually make things “take a step?”
CS447
17
D
Q
this triangular input on the flip-flop is where the clock connects.
for a rising edge-triggered flip-flop…
a rising edge of the clock makes it “take a snapshot” of whatever is on its input, and remember it.
now!!
now the input can change but the flip flop remembers what it saw at the last rising clock edge.
– btw “triggered” is not a synonym for “annoyed” and if you use it like that it makes you sound like either 1. a child who doesn’t know that words can affect people or 2. a douchebag who knows, but doesn’t care. either way it’s not great!
17
The clock input symbol
whenever you see this little triangle…
CS447
18
that means this component remembers things.
often I won’t draw the clock signal wire on the slides, but always assume it’s hooked up. (it wouldn’t work otherwise.)
this is the clock signal input.
Registers
CS447
19
19
A 1-bit register
let’s make a 1-bit register:
CS447
20
D
Q
en
done.
a flip-flop is a 1-bit register.
well, if a 32-bit adder is 32 1-bit adders…
what do you think a multi-bit register is?
20
Tangent: Pull n peel
splitters are how we convert between bundles and individual wires.
CS447
21
4
4
a splitter lets us split up wire bundles…
…or bundle wires back together.
we can do fun stuff in the middle.
4
An n-bit register
an n bit register is n flip-flops next to each other
CS447
22
write enable
4
each flip-flop holds 1 bit of the 4-bit value
D
Q
en
wait what is this “en” thing
D
Q
en
D
Q
en
D
Q
en
now we have a 4-bit register!
(see register_4bit.circ)
22
Write Enables
CS447
23
23
One at a time, now
let’s assume that each MIPS instruction takes one clock cycle.*
in the following code, what register changes on each step?
CS447
24
lw t0, x
add s0, s0, t0
sw s0, x2
t0 changes.
s0 changes.
none change.
we have 32 registers, but on each step, at most one register changes.
so we have to have some way to enable and disable registers. a way to say “don’t write on this clock cycle.”
* this is going to be true for the simplistic kind of CPU we’ll build and talk about over the next few weeks, but it’s not true in general.
24
Take a picture, but only when I say so (animated)
a write enable is like a door on the input of the register.
CS447
25
D
Q
en
now!!
when the write enable is 0, it ignores the clock, and the value never changes.
the only way to change its value is when the write enable is 1 and the clock has a rising edge.
0
huh…?
The bigger picture
a write enable chooses if we change a register’s value on each cycle.
CS447
26
time
CLK
WE
REG
because of that, a register with a write enable can remember a value across multiple steps, instead of just “until the next step.”
this is really important when you have a complicated circuit with lots of registers (like uhhhhhh a CPU!)
– this is a real kind of diagram; it comes up a lot in logic analysis and simulation. software like gtkwave can show these “traces.”
– see how REG shows Xs when the value is changing, and a solid pair of lines when the value is stable (remembered/stored).
26
Logisim’s register component
if you place a Memory > Register, you get this:
CS447
27
data goes in here
data comes out here
(always outputs the
stored value)
write enable – if not
connected, it’s always enabled!
clock!
the stored value, in hex
don’t get confused: the
“en” is for the left input,
not the clock on the bottom
– if you make a register with a data size of 1, it’s basically a flip-flop.
27
OK but what can we do with a register?
CS447
28
Blinky blinky (animated)
what if we had a register that stored 1 bit (a flip-flop)
CS447
29
D
Q
0
1
and we had a NOT gate hooked up in a loop like this…
and we had a light hooked up to the register output…
and we tick the clock? (assuming the register is always enabled)
we get a blinky. it’s the “hello world” of hardware.
– in reality, the clock is ticking at many MHz or GHz, so you have to use a counter to count millions of cycles and turn the light on when the top bit is a 1, but the idea is the same OKAY
29
Wait, why does this work? (animated)
why doesn’t this circuit oscillate when the register changes value?
again, we have gate delay to thank for this.
CS447
30
D
Q
when the input is a 1 and the clock ticks, the register stores the value, but…
0
1
1
0
0
…there is a delay before the register starts outputting its new value…
…and then another delay for the NOT to compute its output.
by the time the 0 makes it to the input, the register has “closed the door.”
it won’t accept any new values until the next rising clock edge.
1
– it’s like writing “x = x + 1” in an HLL. the “x + 1” happens, and then the assignment to x happens.
30
The circle of life
let’s generalize that pattern of combinational and sequential circuits.
CS447
31
74
…sequential circuits let us remember the results…
combinational circuits let us do any computation…
…and connecting them in a loop lets us do multi-step operations.
you might call those “programs.” 😉
– this circuit pattern will show up over and over and over for the rest of the term. get used to it!
31
Let’s make a Thing!
first, let’s look at simple_counter.circ.
it’s a simple counter. HUH.
now, let’s modify it to make it do something a little more interesting.
maybe it only counts when the user holds a button.
maybe it only counts when the value is less than 10.
maybe it can count up or down, depending on some input.
CS447
32
/docProps/thumbnail.jpeg