基于有限状态机的应用综述

胡文欣

（北方工业大学，北京 100144）

0 引言

有限状态机一类应用十分广泛的数学模型，它不仅能够高效地描述有限状态，还能把这些状态之间进行的行为清楚地描述出来。该数学模型被认为是一种描述与实现顺序控制的有效工具，能够高效地描述事件的逻辑顺序。随着现代信息科技的高速进步和发展，有限状态机的研究和应用范围不断拓宽，仅对有限状态机本身进行研究和开发已无法满足现代信息科技进步的需求。从现有研究成果的情况来看，有限状态机已经和多种不同领域的技术完美结合，广泛地应用于嵌入式编程、数字电路开发以及可见光通信等多个领域。面对社会的日益进步，如何让有限状态机更好地和其他领域结合，将其作用发挥到极致是值得攻克的一个挑战。

通过查阅文献，本文整理了有限状态机在断电区间数据快速提取、全自动烫印设备控制系统设计、基于FSM的可逆计数器电路和可逆有限状态机电路方面的应用。

1 FSM的断电区间数据快速提取

在供电系统方面，既要满足供电需求，又得保证供电安全[1]。于是，在发生故障时，断电区间快速判断则显得格外重要。利用基于Trie树结构的算法和基于字符串匹配的分词算法，并合理利用有限状态机匹配模型，实现断电区间数据的快速提取。

1.1 基于Trie树结构的算法

Trie树是一类有序树，用于自动处理与字符串匹配的数据结构，并且它通常能够快速地从一组字符串中自动寻找到某个字符串。可以通过对词图的扫描来获得所有可能的成词，更进一步地，可以得到DAG，便于下一步的操作。在实现的过程中，不仅能够将字典生成一个Trie树，还可以得到每个一个词出现的频率，并且能够找到一个基于单词频率的最佳切分。

1.2 基于字符串匹配的分词算法

基于字符串的精确匹配、基于词的理解以及基于统计学方面的分词算法是现存的三类主要分词算法[2]。使用者若想要成功匹配需要分析的汉字和词典中的词条串，基于字符串匹配的分词算法是最佳选择，若匹配成功，则表示准确识别出一个词。据资料分析，第一种分词算法在分词效率和简便性方面优于其它两类算法，更适合实际的操作。

1.3 有限状态机匹配模型

当需要对断电区间的相关数据加以利用和处理的时候，需要先对分词进行预处理，之后再合理提取数据。起始和终止位置、倍率系数是断电区间相关数据的三个重要元素。首先对断电区间数据分割，处理成1+2模式，然后进行信息匹配。当提取信息时，需要把各个匹配步骤转换成有限状态机对应的状态，令匹配过程等效为状态转移过程，而要想实现由一个状态转移至另一个状态，输入量则至关重要。

模型运行速度很快，可跳过前期训练或拟合，直接达到在短时间内提取出大量数据特征信息的需求。因此，经过上述算法和模型的运用，基于有限状态机的断电区间数据快速提取方法可以准确快速地完成断电区间特征信息提取任务，节约时间和成本。

1.4 实验结果分析

选取某段时间内某地区高速铁路供电故障数据，以结构化方式存储。紧接着，在Python架构的基础上具体实现上述FSM模型，并对此模型进行准确率及运行速度测试，然后采用典型评价指标评价结果。根据实验可得：利用有限状态机模型，得到断电区间起始和终止位置准确率分别达到92.0%和79.0%，提取准确率则为91.5%。

2 FSM的烫印设备控制系统设计

2.1 基于变量配置驱动的状态转换算法

基于变量配置驱动的状态转换算法可用于设计烫印动作的逻辑控制，具体分为以下步骤：首先是将全自动烫印机各烫印动作间的逻辑关系抽象为状态转换图，然后在T5L智能屏的用户数据存储空间规划用于存储烫印动作转换图信息的变量地址，之后就是配置邻接链表，存储状态转换图的信息。上述步骤一一实现之后，便可以进行对T5L智能触摸屏的处理，此时需要对其进行变量配置操作。

对T5L智能触摸屏进行变量配置，首先需要确定全自动烫印机的工作模式，定义全自动烫印机的状态信息，然后将用户数据空间中的地址分为系统变量和曲线变量地址，以及存储全自动烫印机的各项参数，之后在特定的条件下，确定烫印机实际运行时的状态转换过程。

2.2 基于Stateflow建立的全自动烫印机动作的逻辑时序控制模型

该模型共有3层，如图1所示，输入事件“E_on”、“E_off”分别模拟全自动烫印机控制系统的开机按键和关机按键；剩余的输入事件分别模拟全自动烫印机控制系统中T5L智能屏上的按键，用于控制第1层的5个状态的转换。第1层中的5个状态采用内部转换模式，不仅能够降低Stateflow框图的复杂程度和提高Stateflow的执行效率，还能够使生成的代码变简短。第2层含有6个功能模块，细化这6个功能模块的任务则由第3层来完成[3]。

图1 全自动烫印机动作的逻辑时序控制模型

在设置全自动烫印机的5个工作模式的参数值均为1的基础上，利用基于Stateflow搭建的烫印动作逻辑时序控制模型进行仿真分析，得到的输出时序图如图2所示。

图2 输出时序图

根据图2的仿真结果可知，气缸与伺服电机时序是正确的，并提高控制系统的可靠性。

综上，基于FSM的全自动烫印设备控制系统设计方法不仅能提高开发效率，还能提高控制系统的稳定性。它在提高配置和开发效率的同时，能够实现系统级变量配置，拥有巨大的应用发挥空间。

3 可逆有限状态机电路

3.1 可逆逻辑综合算法

对于FSM行为得到的真值表，若要将其对应的逻辑功能用可逆电路实现，可以选择已有的可逆逻辑综合算法。首先需要改写功能函数，分布式改写需要综合的信息，然后根据所有改写完的表达式和变量顺序来生成节点，再对其进行组合，形成整个功能函数图像。之后，在充分维持其函数的功能和其可逆电路性质特征的必要前提下，最大程度地化简图像，最后将所有获得节点的可逆电路进行级联，使其都能够同时实现相应的函数功能。

利用此类算法来达到目的，可以有效避免根据原状态机来求解逆状态机的步骤，简化综合的过程。

3.2 基于可逆FSM的可逆时序电路综合模型

首先借助现有的综合工具对FSM进行状态最小化和分配，把FSM的行为描述成输入为{输入，现态}，输出为{输出，次态}的真值表模式。具体对应的逻辑功能则需要在可逆组合电路的基础上实现，结合现有的可逆逻辑综合算法，完成电路与逻辑功能的匹配对应。以三位右移电路的设计为例，首先根据移位寄存器的规则列出移位寄存电路的真值表，根据真值表得到次态方程和输出方程，结合可逆FSM的结构即可得到符合要求的可逆时序电路。由此例可得，基于可逆 FSM 的可逆时序电路综合模型能够更加优化整个设计过程。在此综合模型的整体架构的基础上，得到的可逆FSM电路结构如图3所示。由图中反馈的信息可知，虚线框中的电路能够实现第i个状态编码Si的采样和锁存。若可逆FSM系统有u位状态编码，则有u个虚线框中的电路结构。

图3 可逆FSM电路结构图

若M=0，C=0，则输出如公式（2）所示：

利用可逆FSM电路结构实现可逆时序电路的综合方法，可避免求解原状态机的逆状态机这个繁琐的环节，使得整个综合过程更为简便优化。

4 基于FSM的可逆计数器电路

4.1 VHDL硬件描述语言

VHDL语言是应用于电子设计领域中的常用语言，它不受具体地硬件和软件控制平台的影响，支持多种设计模式，如：自顶向下、自底向上等。其中自顶向下的设计方法不仅能够让系统在早期设计时，便可以检测功能是否可行，还能随时仿真模拟。利用VHDL语言，设计者根据状态转移图，则能够直接描述状态机，避免繁杂的过程，而且用VHDL语言编写的程序层次分明，条理清楚。

4.2 基于有限状态机的可逆电路设计模型

此类可逆电路设计模型能够高效地用于同步模4的可逆计数器的设置。从状态迁移的特点中可以看出，实现何种计数功能与外部输入的大小有关。当输入值为0时，在时钟脉冲的基础上能够实现加法计数；同样地，减法计数功能则在输入值为1地基础上实现[6-7]。在有限状态机的原理和功能实现基础上，设计出的状态机的工作结构如图4所示。当时钟的有效脉冲信号到来时，Process REG，也就是时序进程能够将次态信号的内容传递给现态信号，而次态的内容则由其他进程的操作和运行结果决定。现态信号的状态值，则能够决定主控组合的进程，也就是Process COM，依靠这个量进入对应的状态，相应的状态值由外部控制信号赋予次态信号[4]。而且，外部控制信号功能很强大，相应的输出信号值也是由其控制的。锁存器进程Process LATCH在时钟的有效跳变到来的基础上也能被启动，它能够锁存主控组合进程产生的次态信号，使得计数器的输出始终保持稳定。

图4 状态机结构工作示意图

根据可逆计数器的一些设计基本原理[5]，再结合VHDL语言，首先设计一个对应的程序，之后在MAX+plusII软件中进行多次仿真，得到仿真结果，也就是对应的波形。

根据以上分析，可以得到：VHDL语言能够从根本上改变电路的设计模式，由传统的硬件设计转变为软件方向的设计。这种思路上的改变可以使得电路更为简便，便于电路的后期修改。同时，有限状态机的运用能够很好地实现高效率高可靠性的逻辑控制，使得可逆计数器电路的性能得到大大提升。可逆式计数器电路在利用有限状态机设计的基础上可以有效地消除在计数器中频繁出现的时序性毛刺。

5 结论

如表1所示，此处对比了可逆有限状态机电路和基于FSM的可逆计数器电路的优点，并总结了共同点和不同点，前者侧重于构造一个行为可逆的FSM，而后者侧重于利用VHDL语言实现对应的逻辑功能[8]。虽然两者在设计过程中使用的方法有所不同，但是都简化了电路，也优化了整个过程，为以后的可逆电路设计以及有限状态机的应用拓宽了思路，开辟了新的途径。

表1 基于有限状态机的两种电路设计方案对比