概述
原文地址：http://blog.163.com/enjoy_yourself_ok/blog/static/1645812142012227102738745/
1 概念和术语
有限状态自动机 (FSM：Finite State Machine)，简称状态机，是表示有限多个状态以及在这些状态之间转移和动作的数学模型。状态存储关于过去的信息，它反映从系统开始到现在时刻输入的变化；转移指示状态变更，用必须满足来确使转移发生的条件来描述它；动作是在给定时刻要进行的活动描述。有多种类型的动作：
- 进入动作（entry action）：在进入状态时进行；
- 退出动作：在退出状态时进行；
- 输入动作：依赖于当前状态和输入条件进行；
- 转移动作：在特定转移时进行。
2 FSM分类
有两种不同类型的状态机：接收器/识别器（Acceptors/Recognizers）和变换器（Transducers）。
2.1 接受器或识别器
接受器/识别器（又称序列检测器）产生一个二元输出，要么“是”要么“否”来回答输入是否被机器接受。接收器/识别器只有两个状态—接受或不接受，在所有的输入都被处理了的时候，如果当前的状态是接受状态，则输入被接受，否则被拒绝。如下图 1展示了接受单词“nice”的有限状态自动机，在这个FSM中唯一的接受状态是状态7。
图1 一个接受器例子
在接受器中，有两个重要的状态：开始状态和接受状态。一个接受器只有一个开始状态和接受状态，可以具有多个中间状态。
开始状态：通常用“没有起点的箭头”来指向它，表示接受器开始工作的状态。
接受状态：指机器成功地进行了它的程序之后的状态。
2.2 变换器
变换器使用动作基于给定的输入和/或状态生成输出。它们用于控制应用，常分为两种类型—Moore机和Mealy机。输出只有当前状态的成为Moore机，输出不但与当前状态有关，还和输入有关的机器成为Mealy机。后文将详细描述这两类机器的特点和区别。
3 FSM数学模型
不管是接受器还是变换器，FSM的下一状态是输入和当前状态的函数。根据类型不同，有多种定义，下面给出接受器和变换器的一种常见数学定义。
4 Moore和Mealy FSM
4.1 定义
Moore状态机的输出只与当前的状态有关，即：输出=f(当前状态)；Mealy状态机的输出与当前状态和输入有关，即：输出=f(当前状态，输入)。不管是Moore机还是Mealy机，两者的下一状态都与当前状态和输入有关，即：下一状态=f(当前状态，输入)，这是两种状态机模型的共性。
4.2 电路模型
根据定义，很容易得到两种状态机的电路模型，如下图所示，给出了两种状态机的电路模型：
图2 Moore型状态机电路简图
图 3 Mealy型状态机电路简图
4.3 性质比较
通过归纳比较，两种状态机具有如下性质特点。
1） Mealy机比Moore机“响应”速度快。Mealy机的输出与当前状态和输入有关，而Moore机输出仅与当前状态有关。Mealy机的输入立即反应在当前周期；Moore机的输入影响下一状态，通过下一状态影响输出。为此Mealy机比Moore机输出序列超前一个周期，即“响应速度”较快。Mealy机的输出在当前周期，具有较长的路径（组合逻辑）；Moore机的输出具有一个周期的延时，容易利用时钟同步，Moore机具有较好的时序。
2） Mealy机状态少，Moore机结构简单。由于Moore机的输出只有当前的状态有关，一个状态对应一个输出，Moore机具有更多的状态。Mealy和Moore机之间可以相互转化，对于每个Mealy机，都有一个等价的Moore机，Moore机状态的上限为所对应的Mealy机状态的数量和输出数量的乘积（后面的例子可以看出Mealy机比Moore机状态少）。、
3）状态机的状态通过触发器的数量来反应，Mealy机具有较少的状态，为此具有较少的触发器。
4.4 电路转换
对于给定的时序逻辑功能，可以用Mealy机实现，也可以用Moore机实现。根据Moore机比Mealy机输出落后一个周期的特性，可以实现两种状态机之间的转换。把Moore机转换为Mealy机的办法为，把次态的输出修改为对应现态的输出，同时合并一些具有等价性能的状态。把Mealy机转换为Moore机的办法是，把当前态的输出修改为对应次态的输出，同时添加一些状态。如下图所示，为把Mealy机状态图转化为Moore机状态图。
图 4 Mealy型机转换为Moore型机
如上图所示，把Mealy型机转换为Moore型机，只要把现时输出改变为下一时刻输出。对于状态A，有4个箭头指向它，表示在当前状态下有4个状态可以转换为下一状态的A；同时当前输出均为0，可以把0移入状态A内部，表示在Moore机中状态A的输出为0。同理，可以把0分别移位B/C状态。但对于状态D，有两个箭头指向且具有不同的输出值，需要把状态D分解成两个状态D1和D2（每个状态对应一个输出，当输出不同需要利用不同的状态表示，这即是Moore机具有更多状态的原因），得到完整的Moore机状态模型。
同理，若把上图的Moore机转换为Mealy机，只要把Moore机中下一状态的输出改变成Mealy机中当前状态的输出，由于D1/D2两状态处于A/C两状态之间，且相当于A/C节点之间的一个等效节点，可以把D1/D2两状态合并为一个状态。
4.5 总结
Mealy机和Moore机实现的电路是同步时序逻辑电路的两种不同形式，它们之间不存在功能上的差异，并可以相互转换。Moore型电路有稳定的输出序列，而Mealy型电路的输出序列早Moore型电路一个时钟周期产生。在时序设计时，根据实际需要，结合两种电路的特性选择。
对于时序电路中常见的计数器，因计数器状态已经固定不变，无论采用Mealy型还是Moore型电路，复杂度一样。
在时序电路设计中Mealy型和Moore型电路的选择原则是：当要求输出对输入快速响应及希望电路尽量简单时，选择Mealy型电路。当要求时序输出稳定，能接受输出序列晚一个周期，及选择Moore型电路不增加电路复杂性时，适宜选择Moore型电路。
5 参考文献
[1]维基百科. http://en.wikipedia.org/wiki/Finite-state_machine#Concepts_and_vocabulary.
[2]维基百科. http://zh.wikipedia.org/wiki/Mealy%E6%9C%BA
[3]维基百科
http://zh.wikipedia.org/wiki/%E6%91%A9%E5%B0%94%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA.
[4] http://www.edaboard.com/thread70331-2.html
[5] 李岚 .Mealy 和 Moore 型电路比较 . 测控技术 .最后
以上就是满意海燕为你收集整理的有限状态机（FSM）学习总结1 概念和术语2 FSM分类3 FSM数学模型4 Moore和Mealy FSM5 参考文献的全部内容，希望文章能够帮你解决有限状态机（FSM）学习总结1 概念和术语2 FSM分类3 FSM数学模型4 Moore和Mealy FSM5 参考文献所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复