Applications Note:
Predicting the Output of Finite State Machines.
Predicting the Output of Finite State Machines
Introduction
The design of finite state machines is a key application of the HDL Designer Series™ tools. Just as it is possible
for a designer to write VHDL that results in poorly performing state machines, it is possible to use HDL Designer
Series™ tools to generate VHDL that results in poorly performing state machines. A key component for the
successful application of a HDL design tool is the users’ confidence that the tool can be used to generate
predictable, high-performance, finite state machine, HDL code.
This applications note explains how elements of the HDL Designer Series™ state diagram editor greatly impact
the resulting HDL code.
The examples in this applications note apply to VHDL. The concepts are equally applicable to designing with the
Verilog™ hardware description language.
This applications note covers the following topics:
Simple “Moore” machines
Simple “Mealy” machines with registered outputs
Simple “Mealy” machines with clocked outputs
The difference between
REGISTERED
and
CLOCKED
output
Signals Status.
Explicitly encoded “Moore” machines
Duplicate states in explicitly encoded “Moore” machines
Some tradeoffs between alternative state machine implementations
Finite state machines using the truth table spreadsheet editor
Page 1 of 23
Revision 2.1
8-Jan-2002
© Mentor Graphics, 1986-2002
Applications Note:
Predicting the Output of Finite State Machines.
Simple “Moore” Machines
The following is an example of a simple “Moore” machine captured using HDL Designer Series™ tools:
Package List
ieee std_logic_1164
ieee numeric_std
Global Actions
b = '1'
2
s0
b = '1'
1
a = '1'
2
Signals Status
SIGNAL SCOPE DEFAULT
x
OUT
'0'
y
OUT
'0'
Declarations
RESET
STATUS
COMB
COMB
s2
y <= '1';
a = '1'
1
s1
x <= '1';
Concurrent Statements
Process Declarations
State Register Block
Generated VHDL code for this finite state machine is on the next page.
The implementation of this “Moore” state machine could be represented as follows:
current_state
nextstate
a
b
next_state
clocked
output
x
y
clk
rst
The inputs
a
and
b
are combined with the
current_state
to determine the
next_state.
The value of the
current_state is decoded to produce the outputs
x
and
y.
This structure is generated because:
1.
2.
The output actions (the assignments of
x
and
y)
are associated with a state, not a transition.
The
Signals Status
declares
x
and
y
as
COMBINATORIAL
outputs.
Page 2 of 23
Revision 2.1
8-Jan-2002
© Mentor Graphics, 1986-2002
Applications Note:
Note:
1.
Predicting the Output of Finite State Machines.
The output actions (the assignments of
x
and
y)
are only explicitly assigned with their “interesting”
values. Wherever the values of
x
and
y
would otherwise be assigned ‘0’, this is accomplished by
using the
DEFAULT VALUES
in the
Signal Status.
Review the “output” process, (line 62) in the
VHDL code and the interaction between the global action and the explicit state action will be
apparent.
Using
DEFAULT VALUES
(or
GLOBAL ACTIONS
for more complex common actions) ensure
the signals are always assigned on every clock edge, thus avoiding the creation of unwanted
latches during synthesis.
The
RESET
values in the
Signals Status
are empty since the outputs are combinatorial.
2.
3.
VHDL for the “Moore” Machine Example
The VHDL code for the state machine on the previous page follows. (This code has been formatted to compact it
slightly.)
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
--
-- VHDL Architecture Sandbox.appsnote_fsm.fsm
-- Generated by Mentor Graphics' HDL Designer(TM)
--
LIBRARY
ieee ;
USE
ieee.std_logic_1164.all;
USE
ieee.numeric_std.all;
ARCHITECTURE
fsm_moore
OF
appsnote_fsm
IS
-- Architecture Declarations
TYPE
state_type
IS
( s0, s1, s2 );
-- State vector declaration
ATTRIBUTE
state_vector : string;
ATTRIBUTE
state_vector
OF
fsm : architecture
IS
"current_state" ;
-- Declare current and next state signals
SIGNAL
current_state, next_state : state_type ;
BEGIN
--------------------------------------------------------------------
clocked :
PROCESS
( clk, rst )
--------------------------------------------------------------------
BEGIN
IF
(rst = '1')
THEN
current_state <= s0;
-- Reset Values
ELSIF
(clk'EVENT
AND
clk = '1')
THEN
current_state <= next_state;
-- Default Assignment To Internals
END IF;
END PROCESS
clocked;
-- continued on the following page.
Page 3 of 23
Revision 2.1
8-Jan-2002
© Mentor Graphics, 1986-2002
Applications Note:
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
Predicting the Output of Finite State Machines.
--------------------------------------------------------------------
nextstate :
PROCESS
( a, b, current_state )
--------------------------------------------------------------------
BEGIN
CASE
current_state
IS
WHEN
s0 =>
IF
(a = '1')
THEN
next_state <= s1;
ELSIF
(b = '1')
THEN
next_state <= s2;
ELSE
next_state <= s0;
END IF;
WHEN
s1 =>
IF
(a = '1')
THEN
next_state <= s2;
ELSIF
(b = '1')
THEN
next_state <= s0;
ELSE
next_state <= s1;
END IF;
WHEN
s2 =>
next_state <= s0;
WHEN OTHERS
=> next_state <= s0;
END CASE;
END PROCESS
nextstate;
--------------------------------------------------------------------
output :
PROCESS
( current_state )
--------------------------------------------------------------------
BEGIN
-- Default Assignment
x <= '0';
y <= '0';
-- Default Assignment To Internals
-- State Actions
CASE
current_state
IS
WHEN
s1 =>
x <= '1';
WHEN
s2 =>
y <= '1';
WHEN OTHERS
=>
NULL;
END CASE;
END PROCESS
output;
-- Concurrent Statements
END
fsm_moore;
Note:
1.
2.
There are three processes: “clocked”, “nextstate” and “output”.
In the “output” process, the
DEFAULT VALUES
(line 65) define the output values, except where
overridden by the explicit assignments associated with states (line 72).
Page 4 of 23
Revision 2.1
8-Jan-2002
© Mentor Graphics, 1986-2002
Applications Note:
Predicting the Output of Finite State Machines.
“Moore” Machine Post Synthesis Timing Behavior
The performance of the “Moore” machine after synthesis is as follows:
a/b
clk
next_state
current_state
x/y
t
clocked
Note:
t
output
t
nextstate
The delay on the outputs
x
and
y
is (t
clocked
+ t
output
) and the outputs
x
and
y
may glitch. They are
synchronous and will be stable before the next rising edge of the clock –
assuming that (t
clocked
+ t
output
+ t
setup
) < the clock period.
Page 5 of 23
Revision 2.1
8-Jan-2002
© Mentor Graphics, 1986-2002
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论