首页 > 代码库 > 状态机FSM

状态机FSM

2024-11-20 05:37:02   202人阅读

状 态机简写为FSM(Finite State Machine),主要分为2大类：第一类，若输出只和状态有关而与输入无关，则称为Moore状态机；第二类，输出不仅和状态有关而且和输入有关系，则 称为Mealy状态机。要特别注意的是，因为Mealy状态机和输入有关，输出会受到输入的干扰，所以可能会产生毛刺（Glitch）现象，使用时应当注 意。事实上现在市面上有很多EDA工具可以很方便的将 状态图的描述转换成可以综合的VHDL程序代码
中文名
状态机
外文名
Finite State Machine)
缩    写
FSM
又    名
状态转移图

目录

1基本信息

2状态机综述

3两种写法

? 有限状态机FSM ? 竖着写C代码片段

4其它

? Moore状态机 ? 范例 ? Mealy状态机

1基本信息编辑

就 是状态转移图。举个最简单的例子。人有三个状态健康，感冒，康复中。触发的条件有淋雨（t1），吃药（t2），打针（t3），休息（t4）。所以状态机就 是健康-（t3）->健康；健康-（t1）->感冒；感冒-（t3）->健康；感冒-（t2）->康复中；康复中 -（t4）->健康，等等。就是这样状态在不同的条件下跳转到自己或不同状态的图。

2状态机综述编辑

关 于状态机的一个极度确切的描述是它是一个有向图形，由一组节点和一组相应的转移函数组成。状态机通过响应一系列事件而“运行”。每个事件都在属于“当前” 节点的转移函数的控制范围内，其中函数的范围是节点的一个子集。函数返回“下一个”（也许是同一个）节点。这些节点中至少有一个必须是终态。当到达终态， 状态机停止。
包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个 映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。当输入符号串，模型随即进入起始状态。它要改变到新的状态，依赖于转换函数。在有限状态机中，会有有许多 变量，例如，状态 机有很多与动作（actions）转换( Mealy机)或状态（ 摩尔机）关联的动作，多重起始状态，基于没有输入符号的转换，或者指定符号和状态（非定有 限状态机）的多个转换，指派给接收状态（识别者）的一个或多个状态，等等。
传统 应用程序的控制流程基本是顺序的：遵循事先设定的逻辑，从头到尾地执行。很少有事件能改变标准执行流程；而且这些事件主要涉及异常情况。“命令行实用程序”是这种传统 应用程序的典型例子。
另一类 应用程序由外部发生的事件来驱动——换言之，事件在应用程序之外生成，无法由应用程序或程序员来控制。具体需要执行的代码取决于接收到的事件，或者它 相对于其他事件的抵达时间。所以，控制流程既不能是顺序的，也不能是事先设定好的，因为它要依赖于外部事件。 事件驱动的GUI 应用程序是这种应用程序的典 型例子，它们由命令和选择（也就是用户造成的事件）来驱动。
Web 应用程序由提交的 表单和用户请求的网页来驱动，它们也可划归到上述类别。但是，GUI 应用程序对于接收到的事件仍有一定程度的控制，因为这些事件要依赖于向用户显示的窗口和控件，而窗口和控件是由 程序员控制的。Web应用 程序则不然，因为一旦用户采取不在预料之中的操作（比如使用 浏览器的历史记录、手工输入链接以及模拟一次 表单提交等等），就很容易打乱设计好的 应用程序逻辑。
显然，必须采取不同的技术来处理这些情况。它能处理任何顺序的事件，并能提供有意义的响应——即使这些事件发生的顺序和预计的不同。有限状态机正是为了满足这方面的要求而设计的。
有限状态机是一种概念性机器，它能采取某种操作来响应一个外部事件。具体采取的操作不仅能取决于接收到的事件，还能 取决于各个事件的相对发生顺序。之所以能 做到这一点，是因为机器能跟踪一个内部状态，它会在收到事件后进行更新。为一个事件而响应的行动不仅取决于事件本身，还取决于机器的内部状态。另外，采取 的行动还会决定并更新机器的状态。这样一来，任何逻辑都可 建模成一系列事件/状态组合。
[1] 状态机可归纳为4个要素，即现态、条件、动作、次态。这样的归纳，主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：
①现态：是指当前所处的状态。
②条件：又称为“事件”，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
③动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
④次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

3两种写法编辑

有限状态机FSM

思 想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软 件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同 时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用 有限的状态，处理无穷的事务。
有限状态机的工作原理如图1所示，发生事件(event)后，根据当前状态(cur_state) ，决定执行的动作(action)，并设置下一个状态号(nxt_state)。
-------------
| |-------->执行动作action
发生事件event ----->| cur_state |
| |-------->设置下一状态号nxt_state
-------------
当前状态
图1 有限状态机工作原理
e0/a0
--->--
| |
-------->----------
e0/a0 | | S0 |-----
| -<------------ | e1/a1
| | e2/a2 V
---------- ----------
| S2 |-----<-----| S1 |
---------- e2/a2 ----------
图2 一个有限状态机实例
--------------------------------------------
当前状态 s0 s1 s2 | 事件
--------------------------------------------
a0/s0 -- a0/s0 | e0
--------------------------------------------
a1/s1 -- -- | e1
--------------------------------------------
a2/s2 a2/s2 -- | e2
--------------------------------------------
表1 图2状态机实例的二维表格表示(动作/下一状态)
图2为一个状态机实例的状态转移图，它的含义是：
在s0状态，如果发生e0事件，那么就执行a0动作，并保持状态不变；
如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；
如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
在s1状态，如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
在s2状态，如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；
有限状态机不仅能够用状态转移图表示，还可以用二维的表格代表。一般将当前状 态号写在横行上，将事件写在纵列上，如表1所示。其中“--”表示空(不执行动作，也 不进行状态转移)，“an/sn”表示执行动作an,同时将下一状态设置为sn。表1和图2表示 的含义是完全相同的。
观察表1可知，状态机可以用两种方法实现：竖着写(在状态中判断事件)和横着写( 在事件中判断状态)。这两种实现在本质上是完全等效的，但在实际操作中，效果却截然 不同。

竖着写C代码片段

cur_state = nxt_state;
switch(cur_state){ //在当前状态中判断事件
case s0: //在s0状态
if(e0_event){ //如果发生e0事件，那么就执行a0动作，
并保持状态不变；
执行a0动作;
//nxt_state = s0; //因为状态号是自身，所以可以删除此句
，以提高运行速度。
}
else if(e1_event){ //如果发生e1事件，那么就执行a1动作，
并将状态转移到s1态；
执行a1动作;
nxt_state = s1;
}
else if(e2_event){ //如果发生e2事件，那么就执行a2动作，
并将状态转移到s2态；
执行a2动作;
nxt_state = s2;
}
break;
case s1: //在s1状态
if(e2_event){ //如果发生e2事件，那么就执行a2动作，
并将状态转移到s2态；
执行a2动作;
nxt_state = s2;
}
break;
case s2: //在s2状态
if(e0_event){ //如果发生e0事件，那么就执行a0动作，
并将状态转移到s0态；
执行a0动作;
nxt_state = s0;
}
}
横着写(在事件中判断状态)C代码片段
//e0事件发生时，执行的函数
void e0_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //观察表1，在e0事件发生时，s1处为空
case s2:
执行a0动作;
*nxt_state = s0;
}
}
//e1事件发生时，执行的函数
void e1_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //观察表1，在e1事件发生时，s1和s2处为
空
执行a1动作;
*nxt_state = s1;
}
}
//e2事件发生时，执行的函数
void e2_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //观察表1，在e2事件发生时，s2处为空
case s1:
执行a2动作;
*nxt_state = s2;
}
}

4其它编辑

Moore状态机

其Moore 状态图如图1所示。
S0/0S1/1S3/0S2/100110011
其中S0/0所代表的意思为现在是状态S0且输出为0， 状态图最主要是将每个状态都给予一个编号，详细描述如下：
1） 在某状态时，列出所有的输出条件。
2） 在某状态时，当输入信号是什么则会跳至哪一个状态。
3） 在某状态时，当输入信号是什么则会维持原状态不变。
可以将图1的Moore状态机写成状态表如表1.
表1 Moore状态表
现态
次态
输出
输入
X=0
X=1 X=0 X=1
S0
S0
S1
0
0
S1
S1
S2
1
1
S2
S3
S0
0
0
S3
S0
S3
0
0
状态表主要描述它与 状态图的关系，再设计状态机电路是，需要先定义状态机的 变量，定义状态机的变量时使用枚举类型来定义，如下范例所示：
Type State is (S0,S1,S2,S3)
接下来，状态会被加以编码。其状态编码方式如下：
（1） 时序编码（Sequential）
将每个状态以二进制来做编码。
（2） 格雷码(Gray)
也是将四个State以二进制来编码，不过不同的是每次编码只会差一个位，其主要缺点是状态改变是要依序改变才可以，若状态不是依序是，则Gray编码不适用。
（3） 独热码（One hot）
独热码状态编码的特色为每一个状态均有自己的触发器，所以若有N个状态就也存在有N个触发器，在任一时刻只会有一组状态编码，缺点是会产生较大的电路，但是相对的使用独热码状态编码对帧错相当有帮助。
三种格式之状态编码如表2所示。
状态
时序编码
Gray编码
One hot编码
S0
00
00
0001
S1
01
01
0010
S2
10
11
0100
S3
11
10
1000
从状态编码表可以看出时序编码和Gray编码均是用二个位来做编码，而以独热码作为编码方式则编码位增加至四个位，所以电路比其他两种编码方式都大一些。
所以可以使用属性来定义编码方式，若要编码成独热码编码，则可加上：
Type State is (S0,S1,S2,S3);
Attribute encoding of state;
Type is “0001 0010 0100 1000”;
在设计状态机时，通常使用进程语句来描述状态机，其中进程语句又可以分为三种方式：
n 一个进程
利用一个进程来描述状态的转换及输出信号的定义。
n 两个进程
一个为时序电路主要负责状态变量的更新，此进程为同步电路，而另一个进程语句主要是描述下次态变量和输出的更新。
n 三个进程
第一个进程主要负责状态变量的更新，第二个进程语句负责描述次态变量，而最后一个则是负责输出信号的更新。
有了以上的初步观念，可以设计图1四个状态的Moore状态机。

范例

首先根据之前的状态表编写VHDL程序如下所示：
Library ieee;
Use ieee.std_logic_1164.all;
Use ieee.numeric_std.all;
Entity moore_fsm is
Port(
clk : in std_logic;
rstn : in std_logic;
x : in std_logic;
output : out std_logic
);
End moore_fsm;
Architecture rtl of moore_fsm is
Type state is (s0,s1,s2,s3); ---状态定义
Signal current_state : state; ---现态
Signal next_state : state; ---次态
Begin
Statefsm: process(rstn, x, current_state)
Begin
If rstn = ‘0’ then --异步reset
next_state <= s0;
output <= ‘0’;
else
case current_state is
when s0 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s1;
end if;
output <= ‘0’;
when s1 =>
if x =’0’ then
next_state <= s1;
else
next_state <= s2;
end if;
output <= ‘1’;
when s2 =>
if x =’0’ then
next_state <= s3;
else
next_state <= s0;
end if;
output <= ‘0’;
when s3 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s3;
end if;
output <= ‘0’;
end case;
end if;
end process statefsm;
stat: process(clk) --current_stateànext_state
begin
if rising_edge (clk) then
current_state <=next_state;
end if;
end process stat;
end rtl;
1) 编码方式预设为时序编码
2) 使用两个进程语句来设计状态机
其综合电路如图2 所示。
其 状态图如图3 所示。
Moore FSM 模拟波形如图4 所示。
模拟结果说明：
（1） 由于reset 为异步reset ，所以当reset在150ns~200ns为0时，则 状态图会从s1回到s0.
（2） 在50 ns时输入x为0且现态为1，在70 ns 时clk上升沿触发且x为1，则current_state会变成next_state s2;

Mealy状态机

接下来我们要介绍Mealy状态机，它和输入、输出、状态皆有关。它的 状态图、状态表与Moore状态机都有所不同，输出会随输入变化而变化。如图5 所示。
0/0
图5：
S0S1S3S20/11/10/10/01/11/0 1/0
若现态为s0输入为0时，则次态为s0且输出为0；若现态为s0输入为1时，则次态为s1且输出为1。
根据这个规则，列出Mealy状态机的状态表如表3。
现太
次态
　输出
输入
X=0
X=1
X=0
X=1
S0
S0
S1
0
1
S1
S2
S1
1
0
S2
S3
S0
0
1
S3
S0
S3
1
0
其Mealy状态机的VHDL如下所示：
Library ieee;
Use ieee.std_logic_1164.all;
Use ieee.numeric_std.all;
Entity melay_fsm is
Port(
clk: : in std_logic;
rstn : in std_logic;
x : in std_logic;
output : out std_logic
);
End moore_fsm;
Architecture rtl of moore_fsm is
Type state is (s0,s1,s2,s3); ---状态定义
Signal current_state : state; ---现态
Signal next_state : state; ---次态
Begin
Statefsm: process(rstn, x, current_state)
Begin
If rstn = ‘0’ then --异步reset
next_state <= s0;
output <= ‘0’;
else
case current_state is
when s0 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s1;
end if;
if x= ‘0’ then
output <= ‘0’;
else
output <= ‘1’;
end if;
when s1 =>
if x =’0’ then
next_state <= s2;
else
next_state <= s1;
end if;
if x= ‘0’ then
output <= ‘1’;
else
output <= ‘0’;
end if;
when s2 =>
if x =’0’ then
next_state <= s3;
else
next_state <= s0;
end if;
if x= ‘0’ then
output <= ‘0’;
else
output <= ‘1’;
end if;
when s3 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s3;
end if;
if x= ‘0’ then
output <= ‘1’;
else
output <= ‘0’;
end if;
end case;
end if;
end process statefsm;
stat: process(clk) --current_stateànext_state
begin
if prsing_edge (clk) then
current_state <=next_state;
end if;
end process stat;
end rtl;
Mealy状态机综合电路如图6 所示。

状态机FSM


联系
我们