CSE 140: Components and Design Techniques for

Digital Systems

Lecture 8:
Sequential Networks and Finite State
Machines

CK Cheng
Dept. of Computer Science and Engineering
University of California, San Diego

1
3. Implementation
• Specification:
– Finite State Machine:
• Behavior, State Diagram, State Table
• Register Transfer Level Description
• Design Flow
• Excitation Table
• Mealy and Moore Machines
• Examples

2
Specification
• Combinational Logic
– Truth Table
– Boolean Expression
– Logic Diagram (No feedback loops)
• Sequential Networks: Finite State Machines
– State Diagram, State Assignment, State Table
– Excitation Table and Characteristic Expression
– Register-Transfer Level Description
– Logic Diagram (FFs and feedback loops)

3
FINITE STATE MACHINE: OVERVIEW USING AN EXAMPLE

Not all sequences are created equal: A coin has two faces.
A toss of the coin lands either Head or Tail with equal
probability. A series of tossing creates a sequence. Given
two patterns, say HHH and HTT, the pattern appears first
wins.
H H H T H H
A. The two patterns have an
equal chance to win
B. HHH wins more times
C. HTT wins more times
D. None of the above
FINITE STATE MACHINE: NOT ALL SEQUENCES ARE CREATED EQUAL

State Diagram of HHH

H/0 H/1
H/0
S H H H
T/0
T/0 T/0
Different diagrams
yield different
State Diagram of HTT expectations

H/0 T/0 T/1

S H T T
H/0 H/0
T/0
Specification: Register-Transfer Level Description
Y

A B C D
Combinational
X
S(t)
CLK CLK
RTL: Register-Transfer Level
Description
CLK
• VHDL
• Verilog Conceptually, we can
• BVS align all registers into one
single column
6
Design Flow
• Input Output Relation
• State Diagram (Transition of states)
• State Assignment (Map states into binary
code)
– Binary code, Gray encoding, One hot
encoding, Coding optimization
• State Table (Truth table of states)
• Excitation Table (Truth table of FF inputs)
– K Map, Minimal Expression
– Logic Diagram
• Verification: Simulation
7
 Design Flow: Examples
• Example 1: a counter from description, state
diagram, state table, netlist, to I/O behavior.
• Example 2: a pattern recognizer from state
diagram to netlist to demonstrate the
difference of two machines.

8
 Example: A Counter
Behavior over time
Symbol/ Circuit

CLK

Free running time

2 bit Counter
Q0

Q1

𝑄 𝑡 + 1 = (𝑄 𝑡 + 1) 𝑚𝑜𝑑 4
9
Counter: Input-output relation ⇒ State diagram

Diagram that depicts

Symbol/ Circuit behavior over time

2 bit Counter

10
 Counter: State diagram ⇒ State assignment
State Diagram State Table: Symbol
S0
Current state Next State
S0 S1
S3 S1
S1 S2
S2 S3
S2 S3 S0
State
Assignment
State Q1 Q0 Q1(t) Q0(t) Q1(t+1) Q0(t+1)

S0 0 0
S1 0 1
S2 1 0
S3 1 1 State Table: Binary
11
 Counter: State assignment ⇒ Excitation table

S0 Current state Next State

S0 S1
S3 S1 S1 S2
S2 S3
S3 S0
S2

Q1(t) Q0(t) Q1(t+1) Q0(t+1)

State Diagram
0 0 0 1
0 1 1 0
1 0 1 1
1 1 0 0

State Table 12
 Counter: Excitation table ⇒ K map ⇒ Logic Diagram

Q1(t) Q0(t) Q1(t+1) Q0(t+1) D0(t) = Q0(t)’

0 0 0 1 D1(t) = Q0(t) Q1(t)’ + Q0(t)’ Q1(t)
0 1 1 0
1 0 1 1
1 1 0 0

Q0(t)
Q
Combinational D
Q’
circuit Q1(t)
D Q
Q’

CLK

Circuit with 2 flip flops

13
Counter: Excitation table ⇒ K map ⇒ Logic Diagram

Q1(t) Q0(t) Q1(t+1) Q0(t+1) We store the current state using D-

0 0 0 1 flip flops so that:
•Inputs to the combinational circuit
0 1 1 0
don’t change while the next output
1 0 1 1 is being computed
1 1 0 0 •The transition to the next state only
State Table occurs at the rising edge of the clock
Q
D Q0(t+1) = Q0(t)’
Q’
Q0(t) Q1(t+1) = Q0(t) Q1(t)’ + Q0(t)’ Q1(t)
D Q
Q’

CLK
Q1(t)

14
Counter: Verification (Simulation)
Q
D
Q’
Q0(t)
Current state Next State Q
D
S0 S1 Q’
S1 S2
S2 S3 CLK
Q1(t)
S3 S0

Example: State sequence

Time 0 1 2 3 4 5
𝑄1 0
𝑄0 0

15
Example: Simulation from state table/state diagram

PS\Input X=0 X=1 1/1

0/0
S0 S0,0 S2,0 0/1
S1 S3,0 S3,0 S0 S1 S3
S2 S2,0 S1,0 1/0 0, 1/0

S3 S1,1 S0,1 1/0 S2

Example: Output sequence 0/0

Time 0 1 2 3 4 5
Input 0 1 1 0 1 -
State S0
Output
16
Example: Simulation from state table/state diagram

PS\Input X=0 X=1 1/1

0/0
S0 S0,0 S2,0 0/1
S1 S3,0 S3,0 S0 S1 S3
S2 S2,0 S1,0 1/0 0, 1/0

S3 S1,1 S0,1 1/0 S2

Example: Output sequence 0/0

Time 0 1 2 3 4 5
Input 0 1 1 0 1 -
State S0 S0 S2 S1 S3 S0
Output 0 0 0 0 1 0
17
 Example: Life on Mars?
Mars rover has a binary input x. When it receives the input sequence
x(t-2, t) = 001 from its life detection sensors, it means that the it has
detected life on Mars ☺ and the output y(t) = 1, otherwise y(t) = 0 (no
life on Mars ).

Implement the Life-on-Mars

Pattern Recognizer!

18
 Mars Life Recognizer FSM
Which of the following diagrams is a correct Mealy solution
for the 001 pattern recognizer on the Mars rover?

1/1
A.
0/0 0/0
1/0 S0 S1 S2
0/0
1/0

B. 0/0
0/0 1/1 Input/output
1/0 S0 S1 S2
1/0
0/0
C. Both A and B are correct
D. None of the above 19
 Mars Life Recognizer FFs
Mealy Machine
Pattern Recognizer ‘001’
x(t)
1/0 1/1
C1 C2 y(t)
0/0 0/0
S0 S1 S2
CLK
1/0 0/0 S(t)

What does state table need to show to design controls of C1?

A. next state S(t+1) vs. input x(t), and present state S(t)
B. output y(t) vs. input x(t), and present state S(t)
C. output y(t) vs. present state S(t)
D. None of the above

20
 State Diagram => State Table with State Assignment

1/1 x(t)

C1 C2 y(t)
0/0 0/0
1/0 S0 S1 S2 0/0
CLK
S(t)
1/0
Mealy Machine

S(t)\x 0 1 State Assignment S(t)\x 0 1

S0 S1,0 S0,0 S0: 00 00 01,0 00,0
S1 S2,0 S0,0 S1: 01 01 10,0 00,0
S2 S2,0 S0,1 S2: 10 10 10,0 00,1
Q1(t+1)Q0(t+1), y

21
State Diagram => State Table => Excitation Table =>
Circuit
Q1(t) Q0(t)\x 0 1 id Q1Q0x D1 D0 y
00 01,0 00,0 0 000 0 1 0
01 10,0 00,0
1 001 0 0 0
10 10,0 00,1
2 010 1 0 0
x(t) 3 011 0 0 0
C1 C2 y(t) 4 100 1 0 0
5 101 0 0 1
CLK 6 110
S(t)
Mealy Machine 7 111

22
State Diagram => State Table => Excitation Table =>
Circuit id Q1Q0x D1 D0 y
Q1(t) Q0(t)\x 0 1
0 000 0 1 0
00 01,0 00,0
01 10,0 00,0
1 001 0 0 0
10 10,0 00,1 2 010 1 0 0
x(t) 3 011 0 0 0
C1 C2 y(t) 4 100 1 0 0
5 101 0 0 1
CLK 6 110
S(t)
Mealy Machine 7 111
Example: What to fill in rows 6 and 7 of excitation table?
A. All 0s
B. All 1s
C. All Don’t Cares 23
State Diagram => State Table => Excitation Table => Circuit

Q0
id Q1Q0x D1 D0 y D1(t):
0 2 6 4
0 000 0 1 0 0 1 X 1
1 3 7 5
1 001 0 0 0 x(t) 0 0 X 0
2 010 1 0 0 Q1

3 011 0 0 0
4 100 1 0 0 D1(t) = x’Q0 + x’Q1
D0 (t)= Q’1Q’0 x’
5 101 0 0 1
y= Q1x
6 110 X X X
7 111 X X X

24
State Diagram => State Table => Excitation Table => Circuit

Q’1 D0 Q0
Q
Q’0 D
x’ Q’
x’ Q1 y
D1 Q
D
Q0 Q’

Q1
x
x(t)

C1 C2 y(t)
D1(t) = x’Q0 + x’Q1
D0 (t)= Q’1Q’0 x’
y= Q1x CLK
S(t)
Mealy Machine 25
 Mealy and Moore Machines: Canonical Form

x(t) y(t)
Combinational
Logic

CLK

x(t) C2 y(t)
x(t)

C1 C2 y(t)
C1
CLK
CLK
26
 Mealy and Moore Machines: Canonical Form

Mealy Machine: yi(t) = fi(X(t), S(t))

Moore Machine: yi(t) = fi(S(t))

si(t+1) = gi(X(t), S(t))

x(t) x(t) y(t)

C1 C2
C1 C2 y(t)
CLK
S(t)
CLK S(t)
Moore Machine
Mealy Machine

27
Mealy and Moore Machines: Canonical Form
Mealy Machine: yi(t) = fi(X(t), S(t))
Moore Machine: yi(t) = fi(S(t))
si(t+1) = gi(X(t), S(t))
Mealy Machine Moore Machine
x(t) x(t) y(t)
C1 C2
y(t)
C1 C2
CLK
S(t)
CLK S(t)

Input Input
PS NS, output PS NS Output

input/output input
Si
S Sj Si
S Sj
output output

28
 Mealy and Moore Machines: Mars Life Recognizer
Which of the following diagrams is a correct Moore solution to the ‘001’
pattern recognizer? input/output
1/1
A.
1/0 0/0 0/0
S0 S1 S2
0/0
1/0
B. 1 0
1
0 0 S2
1 S3
S0 S1 1
0 input 0
1 0
output
C. Both A and B are correct
29
D. None of the above
 Mealy and Moore Machines: Mars Life Recognizer
Pattern Recognizer ‘001’
x(t)
C1 S(t) C2 y(t)
1
1 0

0 0 S2 1 S3
S0 S1
0 0 1 CLK
1 0
Moore Machine
What does state table need to show to design controls of C2?
A.(current input x(t), current state S(t) vs. next state, S(t+1))
B.(current input, current state vs. current output y(t))
C.(current state vs. current output y(t) and next state)
D.(current state vs. current output y(t) )
E. None of the above

30
 Mealy and Moore Machines: Mars Life Recognizer

1
1 0
S2 1 S3
S0 0 S1 0 1
0 0
1

0
ID Q1Q0x D1 D0 y
S(t)\x 0 1
0 000 0 1 0
S0 S1,0 S0,0
S1 S2,0 S0,0 1 001 0 0 0
S2 S2,0 S3,0 2 010 1 0 0
S3 S1,1 S0,1
3 011 0 0 0
Q1Q0\x 0 1 4 100 1 0 0
00 01,0 00,0
5 101 1 1 0
01 10,0 00,0
10 10,0 11,0 6 110 0 1 1
11 01,1 00,1 7 111 0 0 1
Q1(t+1)Q0(t+1), y
 Mealy and Moore Machines: Mars Life Recognizer
Q0
D1(t):
0 2 6 4
0 1 0 1
1 3 7 5

x(t) 0 0 0 1
id Q1Q0x D1 D0 y
Q1
0 000 0 1 0
Q0
1 001 0 0 0 D0(t):
0 2 6 4
1 0 1 0
2 010 1 0 0 1 3 7 5

011 0 0 0 1
3 0 0 0 x(t)

Q1
4 100 1 0 0
Q0
y(t):
5 101 1 1 0 0 2 6 4
0 0 1 0
6 110 0 1 1 1 3 7 5

x(t) 0 0 1 0
7 111 0 0 1
Q1
 Mealy and Moore Machines: Mars Life Recognizer

State Diagram => State Table => Excitation Table => Circuit

D0 Q0
Q y
D
Q’
Q1
D1 Q
D
Q’

x(t) y(t)
C1 C2
D1(t)= Q1(t)Q0(t)’+Q1(t)’Q0(t) x(t)
D0(t)= Q1(t)’Q0(t)’x(t)’+
Q1(t)Q0(t) x(t)’+Q1(t)Q0(t)’ x(t) CLK
y(t)= Q1(t)Q0(t) S(t)
Moore Machine 33
 Conversion from Mealy to Moore Machine
1/1
1
1 0
S 1 S
S0 0 S1 0
0/0 0/0 0 0 2 3
S1 1
1/0 S0 S 0/ 1 0
2
0 0
1/
0

S(t)\x 0 1 S(t)\x 0 1

S0 S1,0 S0,0 S0 S1,0 S0,0

S1 S2,0 S0,0
S1 S2,0 S0,0
S2 S2,0 S3,0
S2 S2,0 S0,1
S3 S1,1 S0,1
 Conversion from Mealy to Moore Machine
S(t)\x 0 1 S(t)\x 0 1 y

S0 S1,0 S0,0 S0 S1 S0 0

S1 S2,0 S0,0 S1 S2 S0 0

S2 S2,0 S0,1 S2 S2 S3 0
S3
Algorithm
1. Identify distinct (NS, y) pair
2. Replace each distinct (NS, y) pair with distinct new states
3. Insert rows of present state = new states
Conversion from Mealy to Moore Machine
Mealy S(t)\x 0 1 S(t)\x 0 1 y Moore
S0 S1,0 S0,0 S0 S1 S0 0

S1 S2,0 S0,0 S1 S2 S0 0

S2 S2,0 S0,1 S2 S2 S3 0
S3
1. Find distinct NS, y
2. Add new states to represent distinct NS, y
iClicker
For the above Moore machine, what are the next states with
respect to present state S3?
A. S2, S3, 1
B. S2, S0, 1
C. S1, S0, 1
D. S1, S0. 0
E. None of the above.
 Conversion from Mealy to Moore Machine
1
1/1 1 0
S 1 S
S0 0 S1 0 3
0 0 2
0/0 0/0 1 0 1
1/0 S0 S1 S2 0/ 0
0
1/0 S(t)\x 0 1
S(t)\x 0 1 S0 S1,0 S0,0
S0 S1,0 S0,0 S1 S2,0 S0,0
S1 S2,0 S0,0 S2 S2,0 S3,0
S2 S2,0 S0,1 S3 S1,1 S0,1

Time 0 1 2 3 4 5 6 7 8
x 0 1 0 0 1 1 0 0 1
Smealy S0 S1 S0 S1 S2 S0 S0 S1 S2
ymealy
Smoore S0
ymoore
 Conversion from Mealy to Moore Machine
1
1/1 1 0
S 1 S
S0 0 S1 0 3
S0 0/0 S1 0/0 0 0 2
1/0 S2 0/ 1 0 1

0 0
1/0 S(t)\x 0 1
S(t)\x 0 1
S0 S1,0 S0,0
S0 S1,0 S0,0
S1 S2,0 S0,0
S1 S2,0 S0,0
S2 S2,0 S3,0
S2 S2,0 S0,1 S3 S1,1 S0,1

Time 0 1 2 3 4 5 6 7 8 iClicker Smoore[0-5]

x 0 1 0 0 1 1 0 0 1 A. S0,S1,S0,S1,S2,S3
Smealy S0 S1 S0 S1 S2 S0 S0 S1 S2 B. S0,S1,S0,S1,S2,S0
ymealy C. S3,S1,S0,S1,S2,S3
Smoore S0 D. S3,S1,S0,S1,S2,S0
ymoore E. None of the above
 Conversion from Mealy to Moore Machine
1
1/1 1 0
S 1 S
S0 0 S1 0 3
S0 0/0 S1 0/0 0 0 2
1/0 S2 0/ 1 0 1

0 0
1/0 S(t)\x 0 1
S(t)\x 0 1
S0 S1,0 S0,0
S0 S1,0 S0,0
S1 S2,0 S0,0
S1 S2,0 S0,0
S2 S2,0 S3,0
S2 S2,0 S0,1 S3 S1,1 S0,1

Time 0 1 2 3 4 5 6 7 8 iClicker ymoore[0-5]

x 0 1 0 0 1 1 0 0 1 A. 0,0,0,0,1,0
Smealy S0 S1 S0 S1 S2 S0 S0 S1 S2 B. 0,0,0,0,0,1
ymealy C. 0,1,0,0,0,0
Smoore S0 D. 0,0,0,0,0,0,
ymoore E. None of the above
Conversion from Mealy to Moore Machine

Algorithm
1. Identify distinct (NS, y) pair
2. Replace each distinct (NS, y) pair with distinct new states
3. Insert rows of present state = new states
4. Append each present state with its output y
 Example: Traffic Light Controller
– Traffic sensors: TA, TB (TRUE when there’s traffic)
– Lights: LA, LB

Bravado
Dining
Hall
LB

LA TB
LA

Academic TA TA Ave.

Labs TB LB Dorms
Blvd.

Fields

41
 Traffic Light Controller: FSM Black Box

• Inputs: CLK, Reset, TA, TB

• Outputs: LA, LB

CLK

TA Traffic LA
Light
TB Controller LB

Reset

42
 FSM State Transition Diagram
• Moore FSM: outputs labeled in each state
• States: Circles
• Transitions: Arcs
Reset
S0
LA: green
LB: red

43
 FSM State Transition Diagram
• Moore FSM: outputs labeled in each state
• States: Circles
• Transitions: Arcs T
Reset A

S0 TA S1
LA: green LA: yellow
LB: red LB: red

S3 S2
LA: red LA: red
LB: yellow LB: green
TB
TB

44
FSM State Transition Table

PS Inputs NS
TA TB
S0 0 X S1
S0 1 X S0
S1 X X S2
S2 X 0 S3
S2 X 1 S2
S3 X X S0 45
 State Transition Table
PS Inputs NS
Q1(t) Q0(t) TA TB Q1(t +1) Q0(t +1)
0 0 0 X 0 1
State Encoding
0 0 1 X 0 0
S0 00
0 1 X X 1 0
S1 01
1 0 X 0 1 1 S2 10
1 0 X 1 1 0 S3 11
1 1 X X 0 0
Q1(t+1)= Q1(t)Q0(t)
Q0(t+1)= Q’1(t)Q’0(t)T’A + Q1(t)Q’0(t)T’B
46
Traffic Light Controller: FSM Output Table
PS Outputs Output Encoding
Q1 Q0 LA1 LA0 LB1 LB0 green 00
0 0 0 0 1 0
yellow 01
0 1 0 1 1 0
red 10
1 0 1 0 0 0
1 1 1 0 0 1 LA1 = Q1
LA0 = Q’1Q0
LB1 = Q’1
LB0 = Q1Q0

47
Traffic Light Controller: State Register

CLK
S'1 S1

S'0 S0
r
Reset
state register

48
 Traffic Light Controller: Logic Diagram

CLK
S'1 S1

TA S'0 S0
r
TB Reset
S1 S0

inputs next state logic state register

49
 Traffic Light Controller: Output Logic

CLK LA1
S'1 S1
LA0

TA S'0 S0
LB1
r
TB Reset
S1 S0 LB0

inputs next state logic state register output logic outputs

50
 Summary: Implementation
• Set up canonical form
• Mealy or Moore machine
• Identify the next states
• state diagram ⇨ state table
• state assignment
• Derive excitation table
• Inputs of flip flops
• Design the combinational logic
• don’t care set utilization

51