WEEK 4 REVIEW

Sequential Circuits

▪ How can same input 0

lead to different
outputs? 3 1
▪ Sequential logic 2
depends on the
sequence of inputs, not
just current input
▪ They have some
internal state
Creating sequential circuits
Key idea:
split the sequential circuit to
two parts.
▪ A bunch of flip-flops to Inputs
Combinational
Outputs

store state. Circuit

 This week
▪ A combinatorial circuit to Storage
handle the logic to Units
manage state and output.
 More next week.
Feedback for Storing State

▪ I want to store the output of an AND gate and

reuse it as input.
Q

Store Q…

▪ Does the following work?

Q
…and reuse it

▪ How do we reason about this circuit?

There is a Propagation Delay

A
B Y

Ideal Considering delays

B B

A A

Y Y

time time

T T+1
Feedback Circuit Example (AND)
▪ Let’s analyze it

A
Q

QT QT+1

QT and QT+1 A QT QT+1

represent the values 0 0 0
of Q at a time T, and
0 1 0
a point in time
immediately after 1 0 0
(T+1) 1 1 1
 Feedback Circuit Examples
▪ Some gates don’t have useful results when
outputs are fed back on inputs.
A A
Q Q

A QT QT+1 A QT QT+1
Stuck
at 0 0 0 0 0 0 0
0 1 0 0 1 1 Stuck as 1
1 0 0 1 0 1
1 1 1 1 1 1
Feedback behaviour
▪ NAND behaviour ▪ NOR behaviour
A QT QT+1 A QT QT+1

0 0 1 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 0

▪ Output QT+1 can be changed, based on A.

▪ They are unstable – oscillations.
A

Q
Latches

▪ We overcome oscillations by combining

multiple NAND or NOR gates.
A A
Q Q

Q Q
B B

▪ These circuits are called latches.

Question #3 R
Q
▪ Complete the truth table
 Don’t-care inputs allowed.
Q
▪ And name the 4 possible S

S,R input combinations

S R QT QT QT+1 QT+1

0 0 0 1 0 1
 Hold
0 0 1 0 1 0
0 1 X X 0 1  Reset
1 0 X X 1 0  Set
1 1 X X 0 0  Forbidden
Question #3 R
Q
▪ Complete the truth table
 Don’t-care inputs allowed.
Q
▪ And name the 4 possible S

S,R input combinations

S R QT QT QT+1 QT+1

0 0 0 1 0 1
 Hold
0 0 1 0 1 0
0 1 X X 0 1  Reset
1 0 X X 1 0  Set
1 1 X X 0 0  Forbidden
 Summary: S’R’ and SR latches

S R QT QT QT+1 QT+1

0 0 X X 1 1 Forbidden state S Q
0 1 X X 1 0 Set Q to 1
SR-latch 1 0 X X 0 1 Reset Q to 0 R Q
1 1 0 1 0 1
1 1 1 0 1 0
Maintain Q
“set” and “reset”
S R QT QT QT+1 QT+1 cannot be both true!
0 0 0 1 0 1
SR-latch 0 0 1 0 1 0
Maintain Q
S Q
0 1 X X 0 1 Reset Q to 0
1 0 X X 1 0 Set Q to 1
1 1 X X 0 0 Forbidden state R Q

12
Question #4

▪ Given the input waveforms, sketch the output

Q of an SR latch. Assume Q was zero initially.

Q
Clocks

▪ A periodic signal that gives timing for our circuit

voltage

time

▪ Frequency = the number of pulses occur per

second.
5 Hz

1 second
Clocked/Gated latches

▪ Add a new input C that acts like a “gate” over

the inputs:

▪ If C=0 the latch ignores input

 Maintains state. S Q
C
▪ If C=1 the latch is “active”
R Q
 Responds to input
 D latch
D
Q D Q
C C
Q
Q

▪ This design is good!

 Easy to store a bit: just set D to what you want to store.
 Can maintain state as long as C is low
 No weird forbidden inputs.
D latch is transparent
▪ Any changes to its inputs
are visible to the output
when control signal D Q
C
(Clock) is 1.
Q
 Output keeps toggling
back and forth.
▪ We want output
C
to change exactly
once per cycle. Q
Flip-flops

▪ Positive edge: D Q
triggered on rising edge of the
C
clock Q

▪ Negative edge: D Q
triggered on falling edge of
C
the clock Q
Flip-flops
▪ For input to propagate to
output, it takes each of the CLK
latches to be active once.
▪ First latch changes on “flip”.
▪ Output can only change
upon “flop”, which is CLK
basically the falling edge of
the clock signal
▪ At most one change per
clock cycle
Flip-flops

▪ We have:
 D flip-flops (most common type!)
 SR flip-flops
 T flip-flops (for “toggle”)
 JK flip-flops
Week 5: Sequential
Circuit Design
Part A: registers
Assembly Language

Processors
Arithmetic Finite State
Logic Units Machines
Devices Flip-flops
Circuits
Gates

Transistors
 We are here
Assembly Language

Processors
Arithmetic Finite State
Logic Units Machines
Devices Flip-flops
Circuits
Gates

Transistors
Circuits using flip-flops
▪ Now that we know Inputs
Combinational
Outputs

about flip-flops and Circuit

what they do, how do
we use them in circuit Storage
design? Units

▪ What’s the benefit in using

flip-flops in a circuit at all?
Example #1: Registers
 Registers
▪ An n-bit register: a bank of n flip-flops that share a
common clock.
▪ Registers store a multi-bit value.

D0 Q D1 Q D2 Q D15 Q
…
Q Q Q Q

Clk

▪ All bits written at the same time.

▪ Key building block of sequential systems and CPUs.
Shift Registers
▪ A series of D flip-flops where output of flip-
flop i is connected to input of i+1
Sin D0 Q D1 Q D2 Q D15 Q

Q Q Q Q

Clk

▪ To set the value of an n-bit shift register, shift

data into it one bit at a time, over n clock
cycles.
Shift registers
▪ Illustration: shifting in 0101010101010101
0
1
SI D0 Q D1 Q D2 Q D15 Q

Q Q Q Q

Clk
Shift registers
▪ Illustration: shifting in 0101010101010101

1 0 1 0
SI D0 Q D1 Q D2 Q D15 Q

Q Q Q Q

Clk

▪ After 16 clock cycles….

Load registers
▪ One can also load a register’s values all at
once, by feeding signals into each flip-flop:
 In this example: a 4-bit load register.

D0 D1 D2 D3

D Q D Q D Q D Q

Q Q Q Q

Clk
Load registers
▪ D flip-flop with enable: controls when the
flip-flop is allowed to load D :
 When EN = 1, D2 is whatever D is → load D
 When EN = 0, D2 is whatever Q is → maintain Q

EN
D2 Q D Q
D EN
Clk Q Q
Load registers
▪ D flip-flop with enable: controls when the
flip-flop is allowed to load D :
 When EN = 1, D2 is whatever D is → load D
 When EN = 0, D2 is whatever Q is → maintain Q

EN

0 D Q D Q
D 1 EN
Clk Q Q
Load registers
D0 D1 D2 D3

D Q D Q D Q D Q
EN EN EN EN
Q Q Q Q
Write
Clk

▪ A register implemented with these new D

flip-flops will maintain the old value in the
register until overwritten by setting EN high.
 Shift vs Load
▪ Shift registers are serial – load bits one at
a time
12-bit
▪ Load registers are parallel – load all bits load
immediately. register

▪ Load registers (a.k.a “registers”) seem

easier to work with… so why?
▪ Sometimes one wire is better than many. 12-bit
shift
 Lack of space on circuit for many wires. register
 Clock skew on long wires, fast clocks.
 Physics.
Serial vs Parallel

PCI PCIe
▪ Parallel ▪ Serial
▪ Many pins ▪ Fewer pins… yet faster
 Memory Hierarchy
▪ In computer architecture, registers are
the first level in the memory hierarchy.
• registers
▪ The CPU’s most local, fastest storage
 30+ of them on-chip.
• cache
▪ They are the memory units that the
CPU interacts with directly for
• RAM
computation.
 Anything else is too far, and is mediated
by registers. • disk

▪ Higher levels: cache, RAM, disk, etc.

37
▪ What else can we build?
Week 5, part B: Counters
Idea for A Counter
▪ Load register + Ripple Carry Adder

n
n
adder register
n
…00001
Clk
Idea for A Counter
▪ Example: 4-bit counter
0 0 0 1

X3 Y3 X2 Y2 X1 Y1 X0 Y0
1
4-bit adder
S3 S2 S1 S0

D Q D Q D Q D Q
EN EN EN EN
Q Q Q Q

Write
Clk
Idea for A Counter
▪ Will this work?

n
n
adder register
n
…00001
Clk

▪ Yes, but lots of gates needed for the adder.

A better idea
T Q
▪ Consider the T flip-flop:
 Output is inverted when Q
input T is high.
▪ What happens when a
series of T flip-flops are
connected together in
sequence?
▪ More interesting: T D Q
Connect the output of Clk
one flip-flop to the clock Q
input of the next!
Counters
1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

Q Q Q Q
Counters
1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

Q Q Q Q

▪ This is a 4-bit ripple counter.

▪ Let’s see how it works
Counters 1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

C
▪ Timing diagram Q Q Q Q

Q0

Q1

Q2

Q3
Counters 1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

C
▪ Timing diagram Q Q Q Q

Q0 0 1 0 1 0 1 0 1 0

Q1 0 0 1 1 0 0 1 1 0

Q2 0 0 0 0 1 1 1 1 0

Q3 0 0 0 0 0 0 0 0 1
Counters 1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

C
▪ Timing diagram Q Q Q Q

Q= 0 1 2 3 4 5 6 7 8

Q0 0 1 0 1 0 1 0 1 0

Q1 0 0 1 1 0 0 1 1 0

Q2 0 0 0 0 1 1 1 1 0

Q3 0 0 0 0 0 0 0 0 1
Counters 1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

C
▪ Timing diagram Q Q Q Q

 Propagation delay increases for later Qs

Q0

Q1

Q2

Q3
Counters
1
Q0 Q1 Q2 Q3

T Q T Q T Q T Q

Q Q Q Q

▪ The ripple counter, is an example of an

asynchronous circuit:
outputs do not all change with the same clock signal.
▪ Timing isn’t quite synchronized with the rising clock
pulse → hard to know when output is ready.
 Cheap to implement, but unreliable for timing.
 Synchronous Counter
Write

T Q T Q
T Q T Q Q2 Q3
Q0 Q1

Q Q
Q Q

Clk

▪ This is a synchronous counter, with a slight delay.

▪ Each AND gate combine outputs of all previous
flip-flops
▪ Each flip-flop only changes when all previous flip
flops are set
 How it works
▪ The first FF Q3
Q0 Q1 Q2
toggles every
clock cycle.
▪ Every other FF “looks to the left”
 That’s what the AND gates do!
▪ If all FFs to the left are 1 on clock edge, toggle.
 Like a carry bit generated from adder!
▪ Otherwise, do not toggle.
▪ Result:
 1 1 1 0 → 0 0 0 1 → 1 0 0 1 → 0 1 0 1
 Read from right to left: 0111 → 1000 → 1001
How it works? Like this

[Link]
 When load is high,
Counters with Load read from Ri instead
of toggling
Load
Write
R0 R1

1 1
D Q 0 D Q
0

Q Q

Clk
Clear

only advance when Counter with parallel load, write,

write is high
(like T in T flip-flop)
and clear (reset) inputs.
▪ Useful for countdowns and more.
What About Custom Designs?
▪ Registers and counters are simple.
▪ What about more sophisticate designs?