技术交流-如何使用-有什么中文资料面包板社区

1 概念和术语有限状态自动机 (FSM：Finite State Machine)，简称状态机，是表示有限多个状态以及在这些状态之间转移和动作的数学模型。状态存储关于过去的信息，它反映从系统开始到现在时刻输入的变化；转移指示状态变更，用必须满足来确使转移发生的条件来描述它；动作是在给定时刻要进行的活动描述。有多种类型的动作： 1）进入动作（entry action）：在进入状态时进行； 2）退出动作：在退出状态时进行； 3）输入动作：依赖于当前状态和输入条件进行； 4）转移动作：在特定转移时进行。 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 电路模型根据定义，很容易得到两种状态机的电路模型，如下图所示，给出了两种状态机的电路模型：图 2Moore型状态机电路简图图 3Mealy型状态机电路简图 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机状态图。图 4Mealy型机转换为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 参考文献维基百科. http://en.wikipedia.org/wiki/Finite-state_machine#Concepts_and_vocabulary . 维基百科. http://zh.wikipedia.org/wiki/Mealy%E6%9C%BA 维基百科 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 . http://www.edaboard.com/thread70331-2.html 李岚.Mealy和Moore型电路比较.测控技术. Mealy, G.H.. A Method for Synthesizing Sequential Circuits. Bell System Tech. J.. September 1955, 34: 1045–1079. Moore, Edward F. Gedanken-experiments on Sequential Machines. Automata Studies,Annals of Mathematical Studies. Princeton, N.J.: Princeton University Press. 1956 (34): 129–153

标签: 技术交流