State Graphs

FSMs

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 1
 Binary Counter State Graph
Q1 Q0 N1 N0
0 0 0 1
0 1 1 0
1 0 1 1
1 1 0 0
00

State graphs are graphical

representations of TT’s
11 01
They contain the same information:
no more, no less
State
10
Transition

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 2
 Design Procedure Using State Graphs

1. Draw the state graph

2. Create an equivalent transition table

3. If transition table contains input don’t cares,

- unfold it to a full transition table

4. Complete the design using KMaps, gates, FF’s

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 3
 State Graphs With Moore Outputs

Z
00
Q1 Q0 N1 N0 Z
Z 0 0 0 1 1
11 01 0 1 1 0 0
1 0 1 1 0
1 1 0 0 1
10

Write the output next to the states it is asserted in…

Underline it to make it more clear
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 4
 Another SG With A Moore Output
INC Q1 Q0 N1 N0 Z INC’
0 0 0 0 0 1
0 0 1 0 1 0
Z
0 1 0 1 0 0 00
0 1 1 1 1 1 INC INC
1 0 0 0 1 1
1 0 1 1 0 0 Z
1 1 0 1 1 0
1 1 1 0 0 1
11 01 INC’
INC’
INC
INC
10

Moore output shows up in multiple TT rows… INC’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 5
 State Graphs and Mealy Outputs
INC’

INC Q1 Q0 N1 N0 Y 00
0 0 0 0 0 0 INC / Y INC
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 1 1 0 11 01 INC’
1 0 0 0 1 0 INC’
1 0 1 1 0 0 INC
1 1 0 1 1 0 INC
1 1 1 0 0 1 10

INC’
Mealy output is associated with an arc in SG

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 6
 Properly Formed State Graphs

• A properly formed state graph is both:

Complete

and

Conflict-free

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 7
 An Incomplete State Graph

• This SG is incomplete. Can you see why?

INC’

00
INC INC

INC’ 11 01 INC’

INC
INC
10
What happens in state ’10’ when INC=0?

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 8
 An Incomplete State Graph

• This SG is incomplete. Can you see why?

INC’

INC Q1 Q0 N1 N0
00 0 0 0 0 0
INC INC 0 0 1 0 1
0 1 1 1 1
1 0 0 0 1
INC’ 11 01 INC’ 1 0 1 1 0
1 1 0 1 1
1 1 1 0 0
INC
INC
10
There is a missing row in the TT as well…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 9
 Complete State Graphs

• For a SG to be complete:
– Paths leaving each state must cover all cases

• To check:
– OR together conditions on all arcs leaving a
given state
– If result = ‘1’, state is complete
– If result ≠ ‘1’, state is incomplete

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 10
 Checking for Completeness
INC’ INC + INC’ = 1
INC + INC’ = 1 State 00 is OK
State 11 is OK

00
INC INC

INC’ 11 01 INC’

INC
INC
10
INC ≠ 1 INC + INC’ = 1
State 10 is not OK State 01 is OK

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 11
 Alternate Check for Completeness

• Full transition table (no input don’t cares)

should have 2n rows where:

n = (#inputs + #state variables)

INC Q1 Q0 N1 N0
0 0 0 0 0
0 0 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 1 1 0
1 1 0 1 1
1 1 1 0 0
This only has 7 rows, something is missing…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 12
 Additional Completeness Considerations

• If some input combination will never occur

– Don’t need to enforce completeness
CLR’ • INC’

01
CLR INC

What about the case of CLR•INC?

If INC=CLR=‘1’ will never occur,

this incomplete state is OK
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 13
 Conflicts in State Graphs
• This SG has a conflict, can you find it?
CLR
CLR’ • INC’
00
CLR’ • INC CLR’ • INC

CLR CLR
CLR’ • INC’ 11 01 CLR’ • INC’

CLR
INC CLR’ • INC
10

CLR’ • INC’
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 14
 Conflicts in State Graphs
• This SG has a conflict, can you find it?
CLR
CLR’ • INC’
00
CLR’ • INC CLR’ • INC

CLR CLR
CLR’ • INC’ 11 01 CLR’ • INC’

CLR
INC CLR’ • INC
10
What happens in state ’10’
when CLR=INC=‘1’?
CLR’ • INC’
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 15
 Conflicts in State Graphs
• This SG has a conflict, can you find it?
CLR
CLR’ • INC’
00
CLR’ • INC CLR’ • INC

CLR CLR
CLR’ • INC’ 11 01 CLR’ • INC’

CLR
INC CLR’ • INC
10 One arc says to go to state 00,
another says to go to state 11
CLR’ • INC’
This is a conflict…
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 16
 Conflicts in State Graphs
• The corresponding transition table has a
problem as well… CLR
CLR’ • INC’
00
CLR INC Q1 Q0 N1 N0 CLR’ • INC CLR’ • INC
0 0 0 0 0 0
0 0 0 1 0 1 CLR CLR
0 0 1 0 1 0 11 01 CLR’ • INC’
0 0 1 1 1 1
0 1 0 0 0 1 CLR’ • INC’ CLR
0 1 0 1 1 0 INC CLR’ • INC
1 - 1 0 0 0
- 1 1 0 1 1 10
0 1 1 1 0 0
1 - - - 0 0
CLR’ • INC’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 17
 Conflicts in State Graphs
• The corresponding transition table has a
problem as well… CLR
CLR’ • INC’
00
CLR INC Q1 Q0 N1 N0 CLR’ • INC CLR’ • INC
0 0 0 0 0 0
0 0 0 1 0 1 CLR CLR
0 0 1 0 1 0 11 01 CLR’ • INC’
0 0 1 1 1 1
0 1 0 0 0 1 CLR’ • INC’ CLR
0 1 0 1 1 0 INC CLR’ • INC
1 - 1 0 0 0
- 1 1 0 1 1 10
0 1 1 1 0 0 Do you want 2 TT
1 - - - 0 0 rows active at
CLR’ • INC’
the same time?
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 18
 Conflict-Free State Graphs

• For a State Graph to not have conflicts:

– Paths leaving each state must not conflict with
one another
• To check:
– For each pair of arcs leaving a given state,
AND together their conditions
– If result = ‘0’, arcs have no conflict
– If result ≠ ‘0’, arcs have a conflict

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 19
 Checking for Conflicts
CLR • (CLR’ • INC’) = 0
These arcs OK
CLR
CLR’ • INC’
00
CLR’ • INC CLR’ • INC
(CLR’ • INC’) • (CLR’ • INC) = 0
These arcs OK
CLR CLR
CLR’ • INC’ 11 01 CLR’ • INC’

CLR
INC CLR’ • INC

INC • CLR ≠ 0 10
These arcs not OK Remember – you must do
all pairs of arcs leaving
CLR’ • INC’ each state…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 20
 Alternate Check for Conflicts

• Full transition table (no input don’t cares)

should have 2n rows where: CLR INC Q1 Q0 N1 N0
0 0 0 0 0 0
0 0 0 1 0 1
0 0 1 0 1 0
n = (#inputs + #state variables) 0
0
0
1
1
0
1
0
1
0
1
1
0 1 0 1 1 0
1 0 1 0 0 0
1 1 1 0 0 0
0 1 1 0 1 1
1 1 1 0 1 1
0 1 1 1 0 0
1 0 0 0 0 0
1 0 0 1 0 0
1 0 1 1 0 0
1 1 0 0 0 0
1 1 0 1 0 0
This has 18 rows, something is wrong… 1 1 1 0 0 0
1 1 1 1 0 0

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 21
 Additional Conflict Considerations

• If some input combination will never occur

– Don’t need to worry about conflicts
CLR’ • INC’

01
CLR INC

If INC=CLR=‘1’ will never occur, the conflict shown here is OK.

But, you will have to make a decision on how to write the TT

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 22
Summary - Properly Formed State Graphs

• A properly formed state graph is both

– Complete
– Conflict-free

• Perform tests to ensure you have covered all

the cases once and only once

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 23
 INC’ INC Q1 Q0 N1 N0
00 0 0 0 0 0

Summary – SG’s vs. TT’s

0 0 1 0 1
INC INC
0 1 0 1 0
11 01 0 1 1 1 1
INC’ INC’ 1 0 0 0 1
1 0 1 1 0
INC 10 INC
1 1 0 1 1
1 1 1 0 0
INC’

• A state graph is simply a graphical way of

writing a Transition Table
– No additional information

• You should be adept at converting between

them

• Design is always done from TT to KMaps to

gates/FF’s

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 24
Finite State Machines

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 25
 State Machine Concepts

• State, current state, next state, state

registers
• IFL, OFL, Moore outputs, Mealy outputs
• Transition tables
– With output don’t cares (X’s)
– With input don’t cares (-’s)
• State graphs
– And their correspondence to TT’s

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 26
 Counters as State Machines

• A counter is a state machine

– Where the state encodings are significant

0000
1001 0001

1000
0010 Q0
Q1 7 Segment
0111 Q2 Decoder
0011
Q3

0110 0100
0101

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 27
 State Machines

• A state machine is a sequential circuit which

progresses through a series of states in
reponse to inputs
– The output values are usually significant
– The state encodings are usually not significant
• Unlike with counters

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 28
 State Encodings

• In this machine, the state encodings don’t

matter
• The output values do…

Event 1
Event 1 Event 2
…
Output2 Output3
Output1

Event 2 Event 3

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 29
 A State Machine Controller for a
Photocopier
Buttons Lamps

Finite
Inputs Outputs
Timers State Motors
Machine

Switches Display

1) FSM receives inputs from copier

2) FSM generates control outputs in response
3) States help it remember where it is in the copy process…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 30
 A Sequence Detector FSM
Xin

Because the encodings don’t matter,

we will use symbolic state names
S0
Xin’

S3 Z S1 Xin’

Xin
Xin
S2 Xin’ What does this machine do?

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 31
 A Sequence Detector FSM
Xin

It is a sequence detector.

S0 It has 1 input: ‘Xin’ and one output: ‘Z’

Xin’

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

It detects the sequence 0..1..1 on the input.

When detected, output ‘Z’ is asserted.

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 32
 A Sequence Detector FSM
Xin

As long as Xin=1, we stay in state S0

S0
Xin’ 1..1..1..1..1..

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 33
 A Sequence Detector FSM
Xin

When Xin=0, we go to state S1

S0
Xin’ 1..1..1..1..1..0..

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 34
 A Sequence Detector FSM
Xin

As long as Xin=0, we stay in state S1

S0
Xin’ 1..1..1..1..1..0..0..0..0..

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 35
 A Sequence Detector FSM
Xin

When Xin=1, we go to state S2

S0
Xin’ 1..1..1..1..1..0..0..0..0..1..

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 36
 A Sequence Detector FSM
Xin

If Xin=1 again, we go to state S3

S0
Xin’ 1..1..1..1..1..0..0..0..0..1..1

S3 Z S1 Xin’

Xin
Xin SUCCESS! Raise the Z output
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 37
 A Sequence Detector FSM
Xin

Once we enter state S3, we never leave…

S0
Xin’

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 38
 A Sequence Detector FSM
Xin

What if we don’t see the second Xin=1?

S0
Xin’ 1..1..1..1..1..0..0..0..0..1..0..

S3 Z S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 39
 Implementing the Sequence Detector
FSM
1. Create symbolic Transition Table
2. Assign state encoding
3. Create conventional Transition Table
4. Do standard implementation steps

Xin CS NS Z Xin Q1 Q0 N1 N0 Z
0 S0 S1 0 0 0 0 0 1 0
1 S0 S0 0 1 0 0 0 0 0
0 S1 S1 0 S0 = 00 0 0 1 0 1 0
1 S1 S2 0 S1 = 01 1 0 1 1 0 0
0 S2 S1 0 S2 = 10 0 1 0 0 1 0
1 S2 S3 0 S3 = 11 1 1 0 1 1 0
- S3 S3 1 - 1 1 1 1 1

Symbolic TT State Assignment Conventional TT

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 40
Sequence Detector Implementation

N1 = Q1•Q0 + Xin•Q1 + Xin•Q0

N0 = Xin’ + Q1
Z = Q1•Q0

Q1 Z
Q0
Q1 N1 Q1
D Q
Xin
Xin
Q0
CLK

Xin’ N0 Q0
D Q
Q1

CLK
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 41
 A Problem With the Sequence Detector

• This FSM only detects first occurrence of

011 on input…
• Here is a timing diagram
– actual screenshot from a simulation

1 0 1 0 0 1 1 1 1

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 42
 Improved Sequence Detector

• This starts over each time 011 is detected…

Xin

S0
Xin Xin’

Xin’
Z S3 S1 Xin’

Xin
Xin
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 43
Improved Detector Timing Diagram

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

Z=1 any time state is S3

Looking at Xin, does it look like Z is a cycle late?

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 44
Mealy Version of Sequence Detector
Xin
Output is asserted during the second ‘1’
of the 011 sequence…
S0
Xin Xin’

Xin’
S3 S1 Xin’

Xin
Xin / Y
S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 45
 Mealy Version Timing Diagram

0 1 1 1 0 1 1 1
Y

Note how Mealy output follows input during state S2

Output is a cycle earlier than in Moore machine –

it appears in S2 rather than in S3

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 46
 Simplified Mealy Sequence Detector

• A characteristic ofMealy
machines is they often require Xin

fewer states than Moore

machines
S0
Xin’

• Here is simplified but

equivalent FSM Xin / Y S1 Xin’

Xin

S2 Xin’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 47
 Example FSM’s

Two Car Wash Controllers

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 48
 Basic Car Wash FSM Operation

1. Wait for a token to be inserted

2. Reset timer
3. Turn on water pump until timer expires
4. Start over

• This assumes existence of:

– Token acceptance mechanism
– Timer
– Digitally-controlled water pump

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 49
 Basic Car Wash FSM SG
TOKEN’
Wait for token…

S_IDLE

TOKEN

Clear timer…
S_TOKEN CLRT
TDONE

SPRAY S_SPRAY Spray car while

waiting for timer
to expire…

TDONE’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 50
 TOKEN TDONE CS NS CLRT SPRAY
0 - S_IDLE S_IDLE 0 0
1 - S_IDLE S_TOKEN 0 0
- - S_TOKEN S_SPRAY 1 0 TOKEN TDONE Q1 Q0 N1 N0 CLRT SPRAY
- 0 S_SPRAY S_SPRAY 0 1
0 0 0 0 0 0 0 0
- 1 S_SPRAY S_IDLE 0 1 0 0 0 1 1 0 1 0
0 0 1 0 1 0 0 1
0 0 1 1 X X X X
0 1 0 0 0 0 0 0
0 1 0 1 1 0 1 0
0 1 1 0 0 0 0 1
0 1 1 1 X X X X
1 0 0 0 0 1 0 0
1 0 0 1 1 0 1 0
1 0 1 0 1 0 0 1
1 0 1 1 X X X X
TOKEN TDONE Q1 Q0 N1 N0 CLRT SPRAY
1 1 0 0 0 1 0 0
0 - 00 00 0 0 1 1 0 1 1 0 1 0
1 - 00 01 0 0 1 1 1 0 0 0 0 1
1 1 1 1 X X X X
- - 01 10 1 0
- 0 10 10 0 1
- 1 10 00 0 1

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 51
 Basic Car Wash Implementation
SPRAY

Q0 N1 Q1
D Q
Q1
TDONE’
CLK
CLRT
TOKEN
N0
Q1’ D Q Q0
Q0’

CLK

This is what you get from a KMap solution

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 52
 Simplified State Graph
TOKEN’
Clear timer while waiting for a
token and eliminate a state

S_IDLE CLRT

TDONE TOKEN
TOKEN TDONE CS NS CLRT SPRAY
0 - S_IDLE S_IDLE 1 0
1 - S_IDLE S_SPRAY 1 0
SPRAY S_SPRAY - 0 S_SPRAY S_SPRAY 0 1
- 1 S_SPRAY S_IDLE 0 1

TDONE’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 53
 Simplified Car Wash Implementation
State Encoding: S_IDLE = 0, S_SPRAY = 1

NS = CS’•TOKEN + CS•TDONE’
CLRT = CS’
SPRAY = CS

CS
CS’
NS SPRAY
TOKEN D Q
CS
TDONE’ CLRT
CLK

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 54
 A Fancy Car Wash Controller

• Two types of washes:

– Regular wash (spray only) = 1 token
– Deluxe wash (spray, soap, spray) = 2 tokens

• Customer:
– Inserts 1 token and pushes START for Regular
– Inserts 2 tokens for Deluxe

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 55
 TOKEN’
Straightforward process to
write transition table and
reduce to gates
S0
T1DONE
TOKEN

TOKEN’ • START’
CLRT1 S1

START TOKEN • START’

T1DONE’ S4 SPRAY
SPRAY, CLRT2 T1DONE’
S2
T2DONE
T1DONE
S3 SOAP, CLRT1 Creativity in FSM design
is designing the initial
state graph…
T2DONE’ 18 STATEGRAPHS/FSM © 2006
ECE 238L
Page 56
Enhancements to Fancy Controller

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 57
 TOKEN’
There is no way to cause coinbox
to refuse tokens. Coins inserted
after wash commences are
S0 ACCEPTCOIN presumably kept by the machine.
T1DONE
TOKEN

CLRT1, TOKEN’ • START’

ACCEPTCOIN S1

START TOKEN • START’

T1DONE’ S4 SPRAY
SPRAY, CLRT2 T1DONE’
S2
T2DONE
T1DONE
S3 SOAP, CLRT1 Let’s add an ACCEPTCOIN output
to control when coinbox will
accept tokens…
T2DONE’ 18 STATEGRAPHS/FSM © 2006
ECE 238L
Page 58
 TOKEN’
If customer pushes START at
precisely the same time as he
inserts another TOKEN, the
S0 ACCEPTCOIN FSM will take the token, but
T1DONE deliver a Regular Wash.
TOKEN
ACCEPTCOIN TOKEN’ • START’
CLRT1 S1

START TOKEN • START’

T1DONE’ S4 SPRAY
SPRAY, CLRT2 T1DONE’
S2
T2DONE
T1DONE
S3 SOAP, CLRT1 That is, START has
precedence over TOKEN

T2DONE’ 18 STATEGRAPHS/FSM © 2006

ECE 238L
Page 59
 TOKEN’
This changes the precedence so
the machine won’t steal the
second token, but will give a
S0 ACCEPTCOIN deluxe wash in this case.
T1DONE
TOKEN
ACCEPTCOIN TOKEN’ • START’
CLRT1 S1

START•TOKEN’ TOKEN

T1DONE’ S4 SPRAY
SPRAY, CLRT2 T1DONE’
S2
T2DONE
T1DONE
S3 SOAP, CLRT1

T2DONE’ 18 STATEGRAPHS/FSM © 2006

ECE 238L
Page 60
 Completeness and Conflict Revisited

• State S1 is a typical problem spot

• Carefully analyze the state graph to ensure no

conflicts exist and that all cases covered.

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 61
 Resetting State Machines

• Ability to reset the FSM is essential for

testing most systems

• Always include a reset capability

– Add CLR signal to state graph
– Use flip flops with clear inputs

– Either method will work

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 62
 Another Example

An Electronic Key Lock

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 63
 Example: Electronic Key Lock
1) There are 10 keypads 0-9
2) The unlock sequence is 7..8..9
3) When a pad is pushed the signal for that number is asserted
4) When any of the keypads are pushed a PUSHED signal is asserted
5) If you push a number out of sequence, you get an error indicator
and you get to start over
6) After three wrong tries, you must wait ½ hr. before trying again
7) If you entered the correct sequence, the lock unlocks.
8) Once the lock has opened, nothing happens until it is manually
locked again.

Inputs: Keypads signals 0-9 Outputs: INC

PUSHED signal CLRTIMER
ECNT3 (error count = 3) CLRCNTR
WAITDONE ERROR
LOCKED UNLOCK

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 64
 LOCKED’

D
LOCKED/ CLRCNTR
PUSHED•9/ UNLOCK
PUSHED’

PUSHED’

PUSHED’ PUSHED•7 PUSHED•8

A B C
Start

PUSHED•7’/ PUSHED•8’/
WAITDONE/ INC
CLRCNTR INC
PUSHED•9’/
ECNT3’ INC

F E ERROR
ECNT3/ CLRTIMER

WAITDONE’

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 65
 LOCKED’
Let’s create the transition table… D
LOCKED/ CLRCNTR
PUSHED’ PUSHED•9/ UNLOCK

PUSHED’
PUSHED•8
PUSHED’ A
Start
PUSHED•7
B C
WAITDONE/ PUSHED•7’/ PUSHED•8’/
INC INC
CLRCNTR PUSHED•9’/
ECNT3’ INC

WAITDONE’ F E ERROR
ECNT3/ CLRTIMER

PUSHED 7 8 9 ECNT3 WAITDONE LOCKED STATE NEXTSTATE INC ERROR CLRCNTR CLRTIMER UNLOCK
0 - - - - - - A A 0 0 0 - 0
1 0 - - - - - A E 1 0 0 - 0
1 1 - - - - - A B 0 0 0 - 0
0 - - - - - - B B 0 0 0 - 0
1 - 0 - - - - B E 1 0 0 - 0
1 - 1 - - - - B C 0 0 0 - 0
0 - - - - - - C C 0 0 0 - 0
1 - - 0 - - - C E 1 0 0 - 0
1 - - 1 - - - C D 0 0 - - 1
- - - - - - 0 D D - 0 - - 0
- - - - - - 1 D A 0 0 1 - 0
- - - - 0 - - E A 0 1 0 - 0
- - - - 1 - - E F - 1 0 1 0
- - - - - 0 - F F - 0 0 0 0
- - - - - 1 - F A 0 0 1 0 0
ECE 238L 18 STATEGRAPHS/FSM © 2006
Page 66
Now let’s expand State A

PUSHED 7 8 9 ECNT3 WAITDONE LOCKED STATE NEXTSTATE INC ERROR CLRCNTR CLRTIMER UNLOCK
0 0 0 0 0 0 0 A A 0 0 0 - 0
0 0 0 0 0 0 1 A A 0 0 0 - 0
0 0 0 0 0 1 0 A A 0 0 0 - 0
0 0 0 0 0 1 1 A A 0 0 0 - 0
0 0 0 0 1 0 0 A A 0 0 0 - 0
0 0 0 0 1 0 1 A A 0 0 0 - 0
0 0 0 0 1 1 0 A A 0 0 0 - 0
0 0 0 0 1 1 1 A A 0 0 0 - 0
0 0 0 1 0 0 0 A A 0 0 0 - 0
0 0 0 1 0 0 1 A A 0 0 0 - 0
0 0 0 1 0 1 0 A A 0 0 0 - 0
0 0 0 1 0 1 1 A A 0 0 0 - 0
0 0 0 1 1 0 0 A A 0 0 0 - 0
0 0 0 1 1 0 1 A A 0 0 0 - 0
0 0 0 1 1 1 0 A A 0 0 0 - 0
…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 67
 This is going to get ugly fast…

• 7 inputs + 3 state bits = 1024 rows in TT

• Can you do a 10-variable KMap?

• There is a technique called One-Hot state

machines we can use instead…

ECE 238L 18 STATEGRAPHS/FSM © 2006

Page 68