Mealy and Moore FSM

Mealy machine: Output is a function of input and the

state.
Moore machine: Output is a function of the state alone.
1/0 1/1
0/1 0/0 0/1 1/0

S0 S1 S0/1 S1/0

1/1 0/0

Mealy machine Moore machine

G. H. Mealy, “A Method for Synthesizing Sequential Circuits,” Bell
Systems Tech. J., vol. 34, pp. 1045-1079, September 1955.
E. F. Moore, “Gedanken-Experiments on Sequential Machines,” Annals of
Mathematical Studies, no. 34, pp. 129-153 ,1956, Princeton Univ. Press, NJ.
 Steps in FSM Synthesis
Examine specified function to identify inputs,
outputs and memory states.
Draw a state diagram.
Minimize states.
Assign binary codes to states.
Derive truth tables for state variables and output
functions.
Minimize multi-output logic circuit.
Connect flip-flops for state variables. Don’t forget
to connect clock and clear signals.
 Architecture of an FSM
The Huffman model, containing:
Flip-flops for storing the state.
Combinational logic to generate outputs and next state from
inputs and present state.

Inputs Outputs
Combinational logic
Present Next
state state

Flip-
flops Clock
Clear
D. A. Huffman, “The Synthesis of Sequential Switching Circuits,
J. Franklin Inst., vol. 257, pp. 275-303, March-April 1954.
 Robot Control
A robot moves in a straight line, encounters an obstacle and
turns right or left until path is clear; on successive obstacles
right and left turn strategies are used.
Define input: One bit
X = 0, no obstacle
X = 1, an obstacle encountered
Define outputs: Two bits to represent three possible actions.
Z1, Z2 = 00 no turn
Z1, Z2 = 01 turn right by a predetermined angle
Z1, Z2 = 10 turn left by a predetermined angle
Z1, Z2 = 11 output not used
 Robot Control (Continued . . . 2)
Because turning strategy depends on the action for the previous obstacle,
the robot must remember the past.
Therefore, we define internal memory states:
State A = no obstacle detected, last turn was left
State B = obstacle detected, turning right
State C = no obstacle detected, last turn was right
State D = obstacle detected, turning left
 Robot Control (Continued . . . 3)
Construct state diagram.
X Z1 Z2
A: no obstacle, last turn was left 0/00 1/01
B: obstacle, turn right 1/01
C: no obstacle, last turn was right A B
D: obstacle, turn left

Input: X = 0, no obstacle
X = 1, obstacle 0/00
0/00

Outputs: 1/10 0/00

Z1, Z2 = 00, no turn 1/10
Z1, Z2 = 01, right turn D C
Z1, Z2 = 10, left turn
 Robot Control (Continued . . . 4)
Construct state table.
X Z1 Z2 X
Present 0 1
0/00 1/01
state
1/01
A B A A/00 B/01

B C/00 B/01

0/00 C C/00 D/10

0/00
D A/00 D/10
1/10 0/00
1/10
D C Outputs
Next
Z1, Z2
state
 Robot Control
State assignment: Each state is assigned a unique binary code.
Need log24 = 2 binary state variables to represent 4 states.
Let memory variables be Y1,Y2:
A: {Y1,Y2} = 00; B: {Y1,Y2} = 01; C: {Y1,Y2} = 11, D: {Y1,Y2} = 10
X X
Present 0 1 Y1 Y2 0 1
state
A A/00 B/01 00 00/00 01/01

B C/00 B/01 01 11/00 01/01

C C/00 D/10 11 11/00 10/10

D A/00 D/10 10 00/00 10/10

 Realization of FSM
Primary input: X
Primary outputs: Z1, Z2
Present state variables: Y1, Y2
Next state variables: Y1*, Y2*
Z1
X
Y1 Combinational logic Z2

Y2 Y1*
Y2*
Flip-
Clock flop

Clear Flip-
flop
Robot Control (Continued . . . 6)
Construct truth tables for outputs, Z1 and Z2, and next state
variables, Y1* and Y2*.
Present
Input Outputs Next state
X state
Y1 Y2 0 1 X Y1 Y2 Z1 Z2 Y1* Y2*
0 0 0 0 0 0 0
00 00/00 01/01
0 0 1 0 0 1 1
01 11/00 01/01 0 1 0 0 0 0 0
0 1 1 0 0 1 1
11 11/00 10/10
1 0 0 0 1 0 1
10 00/00 10/10 1 0 1 0 1 0 1
1 1 0 1 0 1 0
Next Outputs
1 1 1 1 0 1 0
State, Y1*, Y2* Z1, Z2
 Robot Control (Continued . . . 7)
Synthesize logic functions, Z1, Z2, Y1*, Y2*.
Present
Input Outputs Next state Z1 = XY1Y2 + XY1 Y2 = XY1
state
X Y1 Y2 Z1 Z2 Y1* Y2* Z2 = XY1Y2 + XY1 Y2 = XY1
0 0 0 0 0 0 0
0 0 1 0 0 1 1 Y1* = XY1 Y2 + . . .
0 1 0 0 0 0 0
Y2* = XY1 Y2 + . . .
0 1 1 0 0 1 1
1 0 0 0 1 0 1
1 0 1 0 1 0 1
1 1 0 1 0 1 0
1 1 1 1 0 1 0
Robot Control (Continued . . . 8)
Synthesize logic functions, Z1, Z2, Y1*, Y2*.
X X
Z1 Y1*
1 1

Y2 1 Y2 1 1 1

Y1 Y1
X X
Z2 Y2*

1 1

Y2 1 Y2 1 1 1

Y1 Y1
 Robot Control (Continued . . . 9)
Synthesize logic and connect memory elements (flip-flops).
X Combinational logic
Z1

Y2*
Z2
Y1*

Y1
CLEAR
Y1

Y2
Y2 CK