Sequential

Logic
CS270
Max Luttrell, Spring 2017
 sequential logic
• combinational logic: output is a function of
present input only

• sequential logic: output is a function of present

input and also the history of input. in other words,
sequential logic has memory

• how can we store one bit?

three NOT gates

Doesn't work! Unstable!

two NOT gates

A B

Stabilizes to A=B'
 set-reset latch
(SR latch)
S R Q Q'
0 0

S ​Q′  0 1
1 0
1 1

Q R x
0
y
0
or nor
0 1
0 1 1 0
1 0 1 0
1 1 1 0
 set-reset latch
(SR latch)

​Q′ 
S R Q Q'
S 0 0 Q Q'

0 1 0 1

1 0 1 0

Q R 1 1 ? ?

1,1 is not allowed

 SR latch
S Q
​Q′ 
R S R Q Q' Note

0 0 Q Q' hold

S ​Q′  0 1 0 1 reset

1 0 1 0 set
not
1 1 ? ?
allowed

Q R
 D latch
(unclocked)

D Q Q'

S 0
D ​Q′ 

1
R
Q

x y or nor
0 0 0 1
D S Q
0 1 1 0
R Q’
1 0 1 0
1 1 1 0
 D latch
(unclocked)

D Q Q'

S 0 0 1
D ​Q′ 

1 1 0
R
Q

x y or nor
0 0 0 1
D S Q
0 1 1 0
R Q’
1 0 1 0
1 1 1 0
 clocks
• clocks are used to coordinate state changes

• clock generator typically is a crystal oscillator, an oscillation occurs

once per fixed period

• frequency = 1/period; period = 1/frequency; Hz = Hertz = cycles per

second

• for 1 Hz clock frequency, period = 1 / 1 Hz = 1 s

• for 1 kHz clock frequency, period = 1/1000 Hz = 1/1000 s = 1 ms

• for 1.2 GHz clock frequency, period = 1/1.2 billion Hz = 833

picoseconds
clock
high rising
falling
edge
edge

1
0
clock
period clock
low
 D latch
(clocked)
clk D Q Q'
D S Q 0 0

0 1

clk R Q’ 1 0

1 1
 D latch
(clocked)
D S Q clk D Q Q'

0 0 Q Q'
clk R Q’
0 1 Q Q'

1 0 0 1

clk 1 1 1 0

D
Q
time
 edge-triggered D flip flop
(clocked)
1 0 0 clk D Q Q'
D D Q X D Q Q 0 0 Q Q'
0 ​Q  1 ​Q  ​Q  0 1 Q Q'
clk L Q' c L Q' Q'
1 0 0 1
c
1 1 1 0

clk
D
X
Q
time
 edge-triggered D flip flop
(clocked)
• data captured when
1 0 0 clock is high
D D Q X D Q Q
0 ​Q  1 ​Q  ​Q 
clk L Q' c L Q' Q' • output only changes
on falling clock
c
edge

clk

D
X
Q
time
 register
D0
• D flip flops in parallel
with a shared clock
D1
• could add a "write
enable (WE)" input
D2 (only allow writes if
WE==1)

D3

clk
4 bit register
 summary
• Set-Reset (SR) Latch can store one bit, and we can
change its value. But, it has a forbidden state.

• D-Latch (unclocked) can store one bit, and we can

change it. It has no forbidden state.

• Edge-Triggered D Flip-Flop stores one bit. The bit can be

changed synchronized to a falling clock edge. Also
known as a master-slave flip flop.

• n D Flip-Flops can be combined to create an n-bit register

 building blocks
• we have created the following building blocks:

• n-bit register (stores n bits)

• n-to-1 multiplexer (selects one of n inputs)

2
• decoder (n bits input - exactly one of n output bits is 1; other outputs
are 0)

• ALU (n-bit adder, subtractor, bitwise or, bitwise and)

• 7 segment display decoder (we implemented combinational logic

circuits for segment a and e)

• ROM (read only memory)

• PLA (programmable logic array)

 counter
• a 2-bit counter cycles through numbers: 00, 01,
10, 11

• we can write the next state (D) as a function of

the current state (Q).

current next
state state
Q1 Q0 D1 D0
0 0
0 1
1 0

1 1
 counter
• a 2-bit counter cycles through numbers: 00, 01,
10, 11

• we can write the next state (D) as a function of

the current state (Q).
current next
state state D1 = Q1'Q0 + Q1Q0'
Q1 Q0 D1 D0
D0 = Q0'
0 0 0 1
0 1 1 0
1 0 1 1

1 1 0 0
•
counter with ROM
instead of combinational logic, we could also use a 4x2 ROM to
implement our counter. recall: a 4x2 ROM:

• contains 4 2-bit words

• has 2 input lines and 2 output lines

4x2 ROM
2 bit address contents
register
>clk 00 01
01 10
10 11
11 00

ROM outputs
 finite state machine
• a finite state machine has:

• a set of external inputs

• a set of externally visible outputs

• an internal state

• outputs and next state depend on:

• inputs

• current state
 finite state machine
(Mealy Machine)
Current
Registers

State Comb. Output

Logic
Input Next State

output / next state depends on current state and input

 finite state machine
(Moore Machine)
Registers Current Comb.
State Logic Output
Comb.
Input Logic Next State

output only depends on current state

next state depends on current state and input
 finite state machine
example: traffic light controller

Bravado
• inputs Dining
Hall
• traffic sensors: TA, LB
TB (1 if car on
LA TB
sensor, 0 if not) LA

Academic TA TA Ave.
• outputs
Labs TB LB Dorms
• lights: LA, LB

Blvd.
Fields
 finite state machine
example: traffic light controller
• inputs
CLK
• traffic sensors: TA,
TB (1 if car on
sensor, 0 if not)
TA Traffic LA
Light
• reset TB Controller LB

• clock

• outputs Reset

• lights: LA, LB
 traffic rules
• when reset is 1, LA is
green and LB is red

• as long as traffic on

Bravado
Dining
Academic Ave (TA is 1), Hall
keep LA green LB

LA TB
• when TA goes low, LA

sequence to traffic on Academic TA TA Ave.

Bravado TB LB Dorms
Labs

• follow same algorithm for

Blvd.
Bravado Fields

• clock period is 5 seconds

 states
• reset puts us in state
S0, where LA is green
and LB is red.

Bravado
Dining
Hall
LB

S0 LA TB
LA
LA: green
LB: red Academic TA TA Ave.

Labs TB LB Dorms

Blvd.
Fields
 state transition diagram
• outputs are shown in the
state
TA
Reset
• states: circles TA
S0 S1
LA: green LA: yellow
• transitions: arcs LB: red LB: red
Bravado

Dining
Hall
LB

LA TB S3 S2
LA
LA: red LA: red
Academic TA TA Ave. LB: yellow LB: green
TB
Labs TB LB Dorms TB
Blvd.

Fields
 state transition table
Current Next
Inputs TA
state state Reset
S0 TA S1
S TA TB S+
LA: green LA: yellow
S0 0 X S1 LB: red LB: red

S0 1 X S0

S1 X X S2

S2 X 0 S3 S3 S2
LA: red LA: red
S2 X 1 S2 LB: yellow LB: green
TB
S3 X X S0 TB
 encoded state
transition table
State Encoding
S0 00
TA
S1 01 Reset
S0 TA S1
S2 10
LA: green LA: yellow
S3 11 LB: red LB: red

Current state Inputs Next state

a b TA TB a+ b+
0 0 0 X 0 1
S3 S2
0 0 1 X 0 0 LA: red LA: red
0 1 X X 1 0 LB: yellow LB: green
TB
1 0 X 0 1 1 TB
1 0 X 1 1 0
1 1 X X 0 0
 encoded output table

Bravado
Dining
Output Encoding Hall
LB
green 00
LA TB
LA
yellow 01
Academic TA TA Ave.
red 10 TB LB Dorms
Labs

Blvd.
Current State Outputs Fields
Sa1 Sb0 LA1 LA0 LB1 LB0
0 0 0 0 1 0
LA1 = a
0 1 0 1 1 0 LA0 = a'b
1 0 1 0 0 0 LB1 = a'
1 1 1 0 0 1 LB0 = ab
 state table with inputs and
outputs
Current
Inputs Next state Outputs
state
a b TA TB a+ b+ LA1 LA0 LB1 LB0
0 0 0 X 0 1 0 0 1 0
0 0 1 X 0 0 0 0 1 0
0 1 X X 1 0 0 1 1 0

Bravado
Dining
1 0 X 0 1 1 1 0 0 0 Hall
1 0 X 1 1 0 1 0 0 0 LB

1 1 X X 0 0 1 0 0 1 LA TB
LA

Academic TA TA Ave.

Labs TB LB Dorms

Blvd.
Fields
 state register
CLK
a+
S'1 a
S1

b+
S'0 b
S0
r
Reset
state register

a 2 bit register to hold our current state

Reset changes state back to state 00

ab = current state; a+b+ = next state
 next state logic
Current state Inputs Next state
a b TA TB a+ b+
0 0 0 X 0 1
0 0 1 X 0 0
0 1 X X 1 0
1 0 X 0 1 1
1 0 X 1 1 0 CLK
1 1 X X 0 0 a+
S' a1
S
1

TA b+
S' 0
b0
S
r
TB Reset
Sa1 b0
S

inputs next state logic state register

 output logic / full circuit
LA1 = a
LA0 = a'b
LB1 = a'
LB0 = ab
CLK LA1
a+
S'1 a1
S
LA0

TA b+
S'0 b0
S
LB1
r
TB Reset
Sa1 S
b0 LB0

inputs next state logic state register output logic outputs

 Exercise 9A
1. Draw the circuit for a SR latch. Set the outputs to Q=1 and
Q'=0. Set both S and R to 0. Draw the logic values at each
location in the circuit. Can you see how this configuration is
stable and "remembers" its current value?
2. Draw the circuit again, and do the same thing as question 1,
but for Q=0 and Q'=1.
3. Draw the circuit again, set S=1 and R=0. What happens to
Q and Q'? Can you see how S means "set"?
4. Draw the circuit again, and do the same as question 3 but
S=0 and R=1. Can you see how R means "reset"?
5. Set S=1 and R=1. Demonstrate how this configuration
violates the condition that Q should be the inverse of Q'.
 Exercise 9B
1. Using two D flip-flops and any combinational logic you like,
create a Gray code counter. Recall that for a gray code,
only one bit changes at a time, so the counter should count
00, 01, 11, 10, 00, etc. Each D flip flop stores one bit, and
has outputs Q (the bit) and Q' (the bit's inverse).
2. Create a 4x2 ROM that contains the next state for your Gray
Code counter from question 1. Place a register in front of
the ROM inputs and attach the ROM's output functions to
the input of the register. Satisfy yourself that this circuit
functions correctly.
3. Create a PLA to implement your ROM from part 2 (should be
easy)
 Exercise 9C
• draw the finite state machine state transition diagram and the state table
(including inputs and outputs) for a traffic light with two directions A and
B. It functions like this:
• it starts with a green light in the A direction, which continues for at
least 3 cycles. Then it stays green in the A direction as long as traffic is
passing in the A direction and no traffic is waiting in the B direction. If
either of these two conditions is not met, the green direction changes
to B. Thus, there are two inputs: TA and TB, indicating there is traffic
flowing (or waiting) in the corresponding direction.
• B stays green for 3 cycles irrespective of traffic flow and then it goes
back to A green.
• you do not need to cycle through different light colors (red, green,
yellow). Just assume the change from A to B direction is immediate
and no accidents result. Implement only two outputs Agreen and Bgreen.
• implement a circuit for your machine using whatever building blocks
you want. note: if you use a PLA, you don’t have to do any
minimization.