Intro. To Comp. Eng. Chapter Viii-1 Finite State Machines

INTRO. TO COMP. ENG.
•CHAPTER VIII
CHAPTER VIII-1
FINITE STATE MACHINES
CHAPTER VIII
FINITE STATE MACHINES (FSM)
R.M. Dansereau; v.1.0

CHAPTER VIII-2
STATE MACHINES •STATE MACHINES
-INTRODUCTION

INTRODUCTION
• From the previous chapter we can make simple memory elements.

• Latches as well as latches with control signals
• Flip-flops
• Registers
• The goal now is to use the memory elements to hold the running state of
the machine.
• The state of the machine can be used to perform sequential operations.
• This chapter will discuss how to represent the state of the machine for
design and communication purposes.

CHAPTER VIII-3
-INTRODUCTION

MEALY & MOORE MACHINES
• Mealy machine
• Sequential system where Sequential System
output depends on current Input Output
Combinational
input and state. Logic
Memory
(state)
• Moore machine
• Sequential system where Sequential System
output depends only on Input
Combinational
current state. Logic
Memory Output
(state)

CHAPTER VIII-4
-INTRODUCTION
SYNC. & ASYNC. SYSTEMS -MEALY & MOORE MACH.
• Synchronous sequential system

• Behaviour depends on the inputs and outputs at discrete instants of time.
• Flip-flops, registers, and latches that are enabled/controlled with a signal
derived from clock form a synchronous sequential system.
• Asynchronous sequential system
• Behaviour depends on inputs at any instant of time.
• Latches without control signals behave in an asynchronous manner.
• The state machines discussed in this chapter will be synchronous

sequential systems (i.e. controlled by a clock)
• This allows us to form timed Boolean functions such as
• N ( t ) = D A ( t + 1 ) where N is the next state of a D flip-flop D A .

CHAPTER VIII-5
STATE DIAGRAMS •STATE MACHINES
-INTRODUCTION
ELEMENTS OF DIAGRAMS -MEALY & MOORE MACH.
FINITE STATE MACHINES -SYNC. & ASYNC SYSTEMS
• A state diagram represents a finite state machine (FSM) and contains

• Circles: represent the machine states
• Labelled with a binary encoded number or S k reflecting state.
• Directed arcs: represent the transitions between states
• Labelled with input/output for that state transition.
a /p Input: x ( t ) ∈ { a, b }
Output: z ( t ) ∈ { p, q }
Sk Sj State: s ( t ) ∈ { S k, S j }
Initial state: s ( 0 ) = Sk
State
b /q
Input/Output

CHAPTER VIII-6
•STATE DIAGRAMS
PROPERTIES -ELEMENTS OF DIAGRAMS
• Some restrictions that are placed on the state diagrams:

• FSM can only be in one state at a time!
• Therefore, only in one state, or one circle, at a time.
• State transitions are followed only on clock cycles. (synchronous!)
• Mealy machines and Moore machines can be labelled differently.

• Mealy machine: Since output depends on state and inputs:
• Label directed arcs with input/output for that state transition.
• Moore machine: Since output depends only on state:
• Label directed arcs with input for that state transistion.
• Label state circles with S k /output.

CHAPTER VIII-7
•STATE DIAGRAMS
STATE DIAGRAM EXAMPLES -ELEMENTS OF DIAGRAMS
FINITE STATE MACHINES -PROPERTIES
• The following is a simple example. What does this state machine do?
0/1 0/0 Input: x ( t ) ∈ { 0, 1 }
Output: z ( t ) ∈ { 0, 1 }
S0 S1 1/0 State: s ( t ) ∈ { S 0, S 1 }
Initial state: s ( 0 ) = S0
1/0
• Here is a simplified way of forming the above state machine.
0/1, 1/0 0/0,1/0

S0 S1
• An input of 0 or 1 causes the transition with output 1 and 0, respectively.

CHAPTER VIII-8
STATE DIAGRAMS •STATE DIAGRAMS
-ELEMENTS OF DIAGRAMS
BIT FLIPPER EXAMPLE -PROPERTIES
FINITE STATE MACHINES -STATE DIAGRAM EX.
• Consider the simple bit flipper looked at the in previous chapter. How
would a state diagram be formed?
• Below is one possible way of drawing the state diagram for the bit flipper.
-/1
S0 S1
-/0
• Since the bit flipper is a Moore machine, the state diagram can also be
-
S0 ⁄ 0 S1 ⁄ 1

CHAPTER VIII-9
-PROPERTIES
PATTERN DETECT EXAMPLE -STATE DIAGRAM EX.
FINITE STATE MACHINES -BIT FLIPPER EX.
• Suppose we want a sequential system that has the following behaviour

Input: x ( t ) ∈ { 0, 1 }
Output: z ( t ) ∈ { 0, 1 }
1 if x ( t – 3, t ) = 1101
Function: z(t) = 
0 otherwise
• Effectively, the system should output a 1 when the last set of four inputs
have been 1101.
• For instance, the following output z(t) is obtained for the input x(t)
t 0123456789...
x(t) 100100100100110101101101001101001
z(t) ???000000000000100001001000001000

CHAPTER VIII-10
-STATE DIAGRAM EX.
PATTERN DETECT EXAMPLE -BIT FLIPPER EX.
FINITE STATE MACHINES -PATTERN DETECT EX.
• The following state diagram gives the behaviour of the desired 1101 pattern
detector.
• Consider S 0 to be the initial state, S 1 when first symbol detected (1), S 2
when subpattern 11 detected, and S 3 when subpattern 110 detected.

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

CHAPTER VIII-11
STATE TABLES •STATE DIAGRAMS
-STATE DIAGRAM EX.
INTRODUCTION -BIT FLIPPER EX.
• State tables also express a systems behaviour and consists of

• Present state
• The present state of the system, typically given in binary encoded
form or with S k . So, a state of S 5 in our state diagram with 10
states would be represented as 0101 since we require 4 bits.
• Inputs
• Whatever external inputs used to cause the state transitions.
• Next state
• The next state, generally in binary encoded form.
• Outputs
• Whatever outputs, other then the state, for the system. Note that
there would be no outputs in a Moore machine.

CHAPTER VIII-12
•STATE TABLES
BIT FLIPPER EXAMPLE -INTRODUCTION
• Consider again the bit flipper example with state diagram
-
S0 ⁄ 0 S1 ⁄ 1
• The state table for this state diagram would be

Present State Input Next State Output
S 0 or 0 - 1 -
S 1 or 1 - 0 -

CHAPTER VIII-13
•STATE TABLES
TRANSLATE FROM DIAGRAM -INTRODUCTION
FINITE STATE MACHINES -BIT FLIPPER EX.
• From a state diagram, a state table is fairly easy to obtain.

• Determine the number of states in the state diagram.
• If there are m states and n 1-bit inputs, then there will be m 2 n rows in
the state table.
• Example: If there are 3 states and 2 1-bit inputs, each state will
have 2 2 = 4 possible inputs, for a total of 3*4=12 rows.
• Write out for each state, the 2 n possible input rows.
• For each state/input pair, follow the directed arc in the state diagram to
determine the next state and the output.

CHAPTER VIII-14
STATE TABLES •STATE TABLES
-INTRODUCTION
PATTERN DETECT EXAMPLE -BIT FLIPPER EX.
FINITE STATE MACHINES -TRANSLATE DIAGRAM
• If we consider the pattern detection example previously discussed, the

following would be the state table.
P1 P0 X N1 N0 Z
S 0 or 0 0 0 S 0 or 0 0 0
S 0 or 0 0 1 S 1 or 0 1 0
S 1 or 0 1 0 S 0 or 0 0 0
S 1 or 0 1 1 S 2 or 1 0 0
S 2 or 1 0 0 S 3 or 1 1 0
S 2 or 1 0 1 S 2 or 1 0 0
S 3 or 1 1 0 S 0 or 0 0 0
S 3 or 1 1 1 S 1 or 0 1 1

CHAPTER VIII-15
STATE TABLES •STATE TABLES
-BIT FLIPPER EX.
TRANSLATE TO DIAGRAM -TRANSLATE DIAGRAM
• If given a state table, the state diagram can be developed as follows.

• Determine the number of states in the table and draw a state circle
corresponding to each one.
• Label the circle with the state name for a Mealy machine.
• Label the circle with the state name/output for a Moore machine.
• For each row in the table, identify the present state circle and draw a
directed arc to the next state circle.
• Label the arc with the input/output pair for a Mealy machine.
• Label the arc with the input for a Moore machine.

CHAPTER VIII-16
SEQ. CIRCUITS •STATE TABLES
-TRANSLATE DIAGRAM
INTRODUCTION -PATTERN DETECT EX.
FINITE STATE MACHINES -TRANSLATE TO DIAGRAM
• With the descriptions of a FSM as a state diagram and a state table, the
next question is how to develop a sequential circuit, or logic diagram from
the FSM.
• Effectively, we wish to form a circuit as follows.
Inputs
Combinational Outputs
Network (Mealy machine)
State
FF
Present State φ 1φ 2 Next State
FF Outputs
φ 1φ 2 (Moore machine)

CHAPTER VIII-17
•SEQUENTIAL CIRCUITS
FROM STATE TABLE -INTRODUCTION
• The procedure for developing a logic circuit from a state table is the same
as with a regular truth table.
• Generate Boolean functions for
• each external outputs using external inputs and present state bits
• each next state bit using external inputs and present state bits
• Use Boolean algebra, Karnaugh maps, etc. as normal to simplify.
• Draw a register for each state bit.
• Draw logic diagram components connecting external outputs to external
inputs and outputs of state bit registers (which have the present state).
• Draw logic diagram components connecting inputs of state bits (for next
state) to the external inputs and outputs of state bit registers (which have
the present state).

CHAPTER VIII-18
•SEQUENTIAL CIRCUITS
PATTERN DETECT EXAMPLE -INTRODUCTION
FINITE STATE MACHINES -DEVEL. LOGIC CIRCUITS
• Following the procedure outlined, Boolean functions for the pattern

detector state table can be formed using Karnaugh maps as follows.
P1P0 P1P0 P1P0
X 00 01 11 10 X 00 01 11 10 X 00 01 11 10
0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 1 1 0 1 0 1 0 0 1 0
N1 N0 Z
N 1 = XP 1 + XP 1 P 0
N 0 = XP 1 P 0 + XP 1 P 0 + XP 1 P 0 = XP 1 P 0 + X ( P 1 ⊕ P 0 )
Z = XP 1 P 0

CHAPTER VIII-19
SEQ. CIRCUITS •SEQUENTIAL CIRCUITS
-INTRODUCTION
PATTERN DETECT EXAMPLE -DEVEL. LOGIC CIRCUITS
• Notice that the previous Boolean functions can also be expressed with time
as follows.
N1 ( t ) = P1 ( t + 1 ) = X ( t ) ⋅ P1 ( t ) + X ( t ) ⋅ P1 ( t ) ⋅ P0 ( t )
N0 ( t ) = P0 ( t + 1 ) = X ( t ) ⋅ P1 ( t ) ⋅ P0 ( t ) + X ( t ) ⋅ P1 ( t ) ⋅ P0 ( t )
+ X ( t ) ⋅ P1 ( t ) ⋅ P0 ( t )
= X ( t ) ⋅ P1 ( t ) ⋅ P0 ( t ) + X ( t ) ⋅ P1 ( t ) ⊕ P0 ( t )
Z ( t ) = X ⋅ P1 ( t ) ⋅ P0 ( t )
• An important thing to note in these equations is the relation between the

present states P and the next states N.

CHAPTER VIII-20
SEQ. CIRCUITS •SEQUENTIAL CIRCUITS
-INTRODUCTION
PATTERN DETECT EXAMPLE -DEVEL. LOGIC CIRCUITS
• The following logic circuit implements the pattern detect example.
N0 P0
φ1 φ2
N1 P1
φ1 φ2
Z
X

CHAPTER VIII-21
FSM EXAMPLES •SEQUENTIAL CIRCUITS
-INTRODUCTION
EXAMPLE #1 -DEVEL. LOGIC CIRCUITS
• Consider the following system description.

• A sequential system has
• One input = {a, b, c}
• One output = {p, q}
• Output is
• q when input sequence has even # of a’s and odd # of b’s
• p otherwise

CHAPTER VIII-22
•FSM EXAMPLES
EXAMPLE #1 -EXAMPLE #1
• We can begin forming a state machine for the system description by

reviewing the possible states. In addition, assign each state a state name.
• S EE: even # of a’s and even # of b’s / output is p
• S EO : even # of a’s and odd # of b’s / output is q
• S OO : odd # of a’s and odd # of b’s / output is p
• S OE : odd # of a’s and even # of b’s / output is p
• Note that this machine can be a Moore machine. So, we can associate the
output with each state.

CHAPTER VIII-23
•FSM EXAMPLES
• Now draw a circle with each state.
S EE ⁄ p S EO ⁄ q S OO ⁄ p S OE ⁄ p

CHAPTER VIII-24
•FSM EXAMPLES
• Finally, for each state, consider the effect for each possible input.
• For instance, starting with state S EE , the next state for the three input a,
b, and c are determined as follows.
S EE ⁄ p b S EO ⁄ q S OO ⁄ p S OE ⁄ p
c

CHAPTER VIII-25
•FSM EXAMPLES
• Finishing the state diagram, the following is obtained.
b a b
b a b
c S EE ⁄ p S EO ⁄ q S OO ⁄ p S OE ⁄ p c
c c

CHAPTER VIII-26
•FSM EXAMPLES
• A state table can also be formed for this state diagram as follows.
• First, assign a binary number to each state
• S EE = 00 , S EO = 01 , S OO = 10 , S OE = 11
• Assign a binary number to each input
• a = 00, b = 01, c = 10
• Assign a binary number to each output
• p = 0, q = 1
• Then for each state, find the next state for each input. In this case there
are three possible input values, so, three possible state transitions from
each state.
• The state table on the following slide shows the results for this example.

CHAPTER VIII-27
•FSM EXAMPLES

P1 P0 X N1 N0 Z
SEE = 0 0 a = 00 SOE = 1 1 p=0
SEE = 0 0 b = 01 SEO = 0 1 p=0
SEE = 0 0 c = 10 SEE = 0 0 p=0
SEO = 0 1 a = 00 SOO = 1 0 q=1
SEO = 0 1 b = 01 SEE = 0 0 q=1
SEO = 0 1 c = 10 SEO = 0 1 q=1
SOO = 1 0 a = 00 SEO = 0 1 p=0
SOO = 1 0 b = 01 SOE = 1 1 p=0
SOO = 1 0 c = 10 SOO = 1 0 p=0
SOE = 1 1 a = 00 SEE = 0 0 p=0
SOE = 1 1 b = 01 SOO = 1 0 p=0
SOE = 1 1 c = 10 SOE = 1 1 p=0

CHAPTER VIII-28
•FSM EXAMPLES
• The Boolean function for the output can be determined from a Karnaugh
map as follows.
• Note that an input of 11 is not possible since we only have three inputs
that we have assigned to 00, 01, and 10. We can therefore use don’t
cares for this possible input.
P1P0
X1X0 00 01 11 10
00 0 1 0 0
01 0 1 0 0 Z = P1 P0
11 X X X X
10 0 1 0 0

CHAPTER VIII-29
•FSM EXAMPLES
• The Boolean function for the next state bit can also be determined from
Karnaugh maps as follows.
P1P0 P1P0
X1X0 00 01 11 10 X1X0 00 01 11 10
00 1 1 0 0 00 1 0 0 1
01 0 0 1 1 01 1 0 0 1
11 X X X X 11 X X X X
10 0 0 1 1 10 0 1 1 0
N1 = P1 ⊕ X1 ⊕ X0 N0 = P0 X1 + P0 X1 = P0 ⊕ X1

CHAPTER VIII-30
•FSM EXAMPLES
• The following logic circuit can be made with these Boolean functions.
N1 = P1 ⊕ X1 ⊕ X0
N0 = P0 ⊕ X1
Z = P1 P0
N0 P0
X1 φ1 φ2
X0
Z
N1 P1
φ1 φ2

CHAPTER VIII-31
•FSM EXAMPLES
• A sequential circuit is defined by the following Boolean functions with input

X , present states P 0 , P 1 , and P 2 , and next states N 0 , N 1 , and N 2 .
• N2 = X ( P 1 ⊕ P0 ) + X ( P1 ⊕ P0 )
• N1 = P2
• N0 = P1
• Z = XP 1 P 2
• Derive the state table.
• Derive the state diagram.

CHAPTER VIII-32
•FSM EXAMPLES
FINITE STATE MACHINES -EXAMPLE #2
• The state table is formed as follows.

P2 P1 P0 X N2 N1 N0 Z
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 1 1 1 0 0 0
0 1 0 0 0 0 1 0
0 1 0 1 1 0 1 0
0 1 1 0 1 0 1 0
0 1 1 1 0 0 1 0
1 0 0 0 1 1 0 0
1 0 0 1 0 1 0 0
1 0 1 0 0 1 0 0
1 0 1 1 1 1 0 0
1 1 0 0 0 1 1 0
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 0
1 1 1 1 0 1 1 1

CHAPTER VIII-33
•FSM EXAMPLES
FINITE STATE MACHINES -EXAMPLE #2
• The state diagram can be drawn as follows.
1/0
1/0
S0 0/0 S1 0/0 S2 S3
0/0 1/0 1/0 1/0 0/0

0/0 1/1
0/0
S4 S5 S6 S7
1/0 1/1
0/0
0/0

Intro. To Comp. Eng. Chapter Viii-1 Finite State Machines

Uploaded by

Copyright:

Available Formats

Intro. To Comp. Eng. Chapter Viii-1 Finite State Machines

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Intro. To Comp. Eng. Chapter Viii-1 Finite State Machines

Uploaded by

Copyright:

Available Formats

INTRO. TO COMP. ENG.

FINITE STATE MACHINES (FSM)

R.M. Dansereau; v.1.0

FINITE STATE MACHINES

• From the previous chapter we can make simple memory elements.

R.M. Dansereau; v.1.0

FINITE STATE MACHINES

R.M. Dansereau; v.1.0

• Synchronous sequential system

• The state machines discussed in this chapter will be synchronous

R.M. Dansereau; v.1.0

• A state diagram represents a finite state machine (FSM) and contains

R.M. Dansereau; v.1.0

• Some restrictions that are placed on the state diagrams:

• Mealy machines and Moore machines can be labelled differently.

R.M. Dansereau; v.1.0

• Here is a simplified way of forming the above state machine.

0/1, 1/0 0/0,1/0

• An input of 0 or 1 causes the transition with output 1 and 0, respectively.

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

• Suppose we want a sequential system that has the following behaviour

R.M. Dansereau; v.1.0

when subpattern 11 detected, and S 3 when subpattern 110 detected.

R.M. Dansereau; v.1.0

• State tables also express a systems behaviour and consists of

R.M. Dansereau; v.1.0

• Consider again the bit flipper example with state diagram

• The state table for this state diagram would be

R.M. Dansereau; v.1.0

• From a state diagram, a state table is fairly easy to obtain.

R.M. Dansereau; v.1.0

• If we consider the pattern detection example previously discussed, the

R.M. Dansereau; v.1.0

• If given a state table, the state diagram can be developed as follows.

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

• Following the procedure outlined, Boolean functions for the pattern

R.M. Dansereau; v.1.0

• An important thing to note in these equations is the relation between the

R.M. Dansereau; v.1.0

• The following logic circuit implements the pattern detect example.

R.M. Dansereau; v.1.0

• Consider the following system description.

R.M. Dansereau; v.1.0

• We can begin forming a state machine for the system description by

R.M. Dansereau; v.1.0

• Now draw a circle with each state.

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

• Finishing the state diagram, the following is obtained.

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

Present State Input Next State Output

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0

R.M. Dansereau; v.1.0