有限状态机模型（共7篇）
有限状态机模型 篇1
摘要：在群体动画的智能角色的行为决策和选择中, 有限状态机 (FSM) 作为一种反应式建模的有力工具, 常用于反应型智能角色的行为选择机制的实现和行为建模。针对实践中发现的基于结构化方法的FSM实现繁杂、代码难以重用、维护复杂、扩展性差的问题, 结合State设计模式, 提出了一个基于面向对象技术的FSM的实现方法。仿真试验结果表明, 此方法有效地解决了基于结构化方法FSM的缺陷, 实现了智能角色在复杂虚拟环境中的行为决策。
关键词：有限状态机,人工智能,面向对象,行为决策
0引言
群体动画创作一直是计算机动画界的一个难题。采用传统的关键帧技术创作生动逼真的人群或动物群体动画, 动画师需要付出繁重的劳动, 因为在群体动画创作过程中, 不仅要求群体的运动协调一致, 而且要求各角色分别具有独特的运动轨迹。因此, 目前群体动画的制作基本都采用计算机动画的人工生命方法:这种方法将每个群体动画角色作为一个独立智能体, 每个智能体都有自主性、社会性、反应性、移动性、意识性这五大特征, 并且赋予其生物外观形态和动作表现能力。然后再创建动画角色的生存环境, 通过智能体相互之间, 智能体与环境之间发生的相互作用, 自动地生成动画, 这样动画师只需要拍摄群体角色的运动, 就能得到丰富而逼真的群体动画效果。
对于每个独立的智能体而言, 行为决策能力的高低决定了其智能水平的高低。本文采用一种面向对象的FSM模型来实现智能体的行为决策功能, 成功模拟了一个简易粒子鱼群的行为。结果表明, 通过FSM来控制智能体的简单行为选择是一个可行性强的技术方案。
1有限状态机
有限状态机 (FSM) 一般由一个可能的输入状态表, 一个可能的输出状态表, 以及一些状态转移参数和一个起始状态组成[1]。一个有限状态机可以这样来完整地描述:“有限状态机”是一个有限的状态组成的, 其中的一个状态是“当前状态”。“有限状态机”可以接收一个“输入”, 这个“输入”的结果将导致一个“状态转换”的发生 (即从“当前状态”转换到“输出”状态) 。这个“状态转换”是基于“状态转换函数”的。状态转换完成之后, “输出状态”即变成了“当前状态”。
一个有限状态机必须有一个“输入”, 这个“输入”可以影响其“状态转换”。有限状态机应该有一个简单 (或复杂) 的状态转换函数, 这个函数可以决定什么状态可以变成“当前状态”。
图1是一个简单的有限状态机模型。在这个简单的FSM中, 初始状态为1, 当输入为0, 输出为1, 或者输入为1, 输出为2的时候, 下一个状态还保持1;当输入为2, 输出为0时, 转入状态2。此时在状态2下, 如果输入为0, 输出为2, 或者输入为1, 输出为0, 那么下一个状态还继续保持状态2;当输入为2, 输出为1的时候, 则下一状态重新转为状态1。
因此, 这个FSM的状态转移表如表1所示。
2FSM在群体动画中的应用
在群体动画中, 智能角色的行为决策和选择是最为重要的部分。由于FSM具有结构清晰简单、逻辑关系明确、系统实现起来相对容易等突出优点, 用FSM的方法可以高效地实现智能角色的行为选择机制, 特别适用于典型的反应型的智能角色行为建模。
2.1公园里的鸽子
在Reynolds制作的群体动画“pigeons in the park”[2]中, 鸽子的行为选择就是一个典型的基于FSM的系统, 首先建立每一只鸽子的状态模型, 通过输入相应的外界环境信息, 鸽子模型中的智能体就对信息进行判断、处理, 最终决定鸽子应该做出何种行为。图2是一个比较完整的鸽子状态行为转移图。
可以看到鸽子的状态可以大致分为:饥饿、觅食、饱食、飞行、跑开、闲逛、躲避天敌、死亡等八个状态。影响鸽子状态转移的精神状态参数有2个:饥饿值H和恐惧值F。在每一个状态, 鸽子的智能系统都会对2个参数不停地进行查询, 一旦发现参数满足转移条件, 立即根据状态转移图, 由当前状态转入下一状态, 同时对这一状态下的参数重新进行查询, 如此往复。例如:当鸽子处于闲逛状态时, 系统不断地对饥饿值和恐惧值进行判断, 如果发现饥饿值H首先大于a, 那么就转入饥饿状态, 如果发现恐惧值大于c, 就转入到跑开状态, 由于系统的查询是有间隔的, 所以当恐惧值突然加大到大于d的时候, 鸽子就将转入飞行状态。
2.2人工鱼
目前在群体动画方面研究最深入的当属人工鱼领域[3,5]。根据自然鱼的2个基本特性, 人工鱼应该具有以下特性: (1) 它们是时变的; (2) 它们应依赖于内部冲动或者依赖外部刺激, 或两者都依赖。为此设计实现了3个精神状态变量:饥饿感H, 性欲L, 恐惧感F。这3个变量值在闭区间[0, 1]中变化, 当取值较高时, 依次表明有较强的愿望去进食、求偶、躲避捕食者。H和L由内部冲动和外部刺激决定, 而F则单独由外部刺激引起。
饥饿感H和恐惧感F的设计:
饥饿感H:
At each time step
F1=d*1*F1;
If (foodEaten)
F1=truncate (F1+f, a) ;
hungerValue=1.0-F1/a;
其中:d是鱼的消化率0<d<1;
a是鱼的饱和食欲;
t是时间增量;
f是鱼吃的事物量;
F1是鱼此时胃中的事物量。
在此模型中, 通过刻画鱼的消化率d和鱼的饱和食欲a来仿真不同类型的鱼。
恐惧感F:
Fear=min{conmfortZone/preDistance (i) , 1}
其中, preDistance (i) 是此时距离捕食i的距离;
comfortZone是鱼的威胁感知距离。
进一步, 设计一个基于意图有限级的意图发生器。据此, 行为决策模型在鱼的仿真回路中连续地运行, 在每一个仿真周期里, 人工鱼通过感知系统获取周围环境信息, 意图产生机制根据鱼的习性、精神状态和传入的感知信息产生一个恰当的意图, 然后通过行为选择机制产生一系列行为以实现意图, 完整地实现了人工鱼的大脑仿真。
由于鱼的精神状态是连续的、时变的, 故可以采用FSM来建立鱼的行为选择机制。将人工鱼的每一个运动行为对应一个意图, 根据人工鱼当前意图的变化或者动画师指定新的意图触发智能角色意图的变迁, 激活相应的行为, 例如:当人工鱼的饥饿感H超过一定的阈值, 则进入觅食状态, 直到体内食物到达一定的量, H值重新小于一个阈值的时候, 转入闲逛状态。
虽然FSM可以比较简单地实现智能角色的行为选择机制, 但是也有明显的不足之处。主要表现为以下两点:
(1) 当角色具有较多状态, 处理的事件比较多, 状态转换频繁时, 其代码实现复杂, 难以维护且扩展性差。可以通过面向对象的FSM来有效地解决这个问题。
(2) 当角色具有学习功能或具有理性思维的时候, 此时构建的行为选择机制对实现此类的行为选择往往无能为力, 必须与其他的建模方法结合起来, 例如基于认知模型的方法[4]。
3面向对象的FSM设计
3.1系统状态的定义
在面向对象的设计中, 系统的状态可以定义为一种由事件集合至变迁到的状态集合的映射。比如, 状态A可以定义为:
{ (EventA, StateB) , (EventB, StateC) , (EventC, StateA) }
系统的状态由一个单一的对象来表示, 这个对象叫作当前状态对象。
3.2面向对象的FSM示意图
图3显示了事件处理程序是如何把所有事件都直接发给当前状态对象去处理的过程。
3.3类设计
由于事件处理程序不应该知道有关当前状态的任何细节 (即当前状态对象究竟是哪一种对象) , 因而所有的状态对象都应该共享同样的接口, 这样, 所有的状态对象类都应该从一个公共的基类中派生出来, 由这个基类提供接口。另外, 如果每一个状态都由一个不同的对象来表示, 那么就可以很容易地把一个FSM转化成为状态类的层次关系图。图4为FSM范例中所需要的状态类层次结构。
基类stateRoot需要三个成员函数来分别处理三种可能的事件。FSM中的3种状态分别由三个从stateRoot中派生出来的子类来代表, 这三个子类分别重新定义了他们需要提供各自特定功能的成员函数。
当事件发生时, 当前状态对象的成员函数被调用, 这个函数具有把自己转变成一个新的状态对象的能力。
3.4类声明及其相关的函数
子类中的成员函数重定义。
在基类中, 所有事件处理程序都返回指针this, 也就是当前的对象;而在重定义的事件处理程序中, 返回的是指向其他类型的状态对象的指针。
这是整个程序的事件处理函数。针对一个当前状态对象, 在初始化的时候设置成stateA的实例。当接收到事件时, 事件处理程序去调用当前状态对象对应的成员函数, 当前状态对象的指针被赋成从这个成员函数中返回的值。显然, 当前状态对象的改变取决于成员函数返回什么类型的对象的指针。
4仿真结果
本文基于面向对象的FSM, 采用OpenGL作为动画工具, 编写了VC++应用程序, 对鱼群粒子模型进行了仿真实验。实验结果 (如图5所示) 。图中不同颜色的粒子代表不同的人工鱼, 它们在一个立体的水箱里不停地运动, 根据FSM提供的行为选择机制不停地改变状态, 控制着自己的行为。
5结论
群体动画中智能角色的行为决策模型是智能角色的“大脑”, 它对应实现智能角色的行为决策功能, 其设计水平直接决定着智能角色的智能高低。本文通过设计实现一个有限状态机, 来完成一个简单的智能角色的决策模型。这个模型能比较好地满足当前动画创作的需要。本文采用了一种基于面向对象技术的FSM实现了一个简单鱼群粒子模型的构建, 有效地解决了基于结构化方法FSM的缺陷, 逼真模拟了智能鱼群的基本行为。
参考文献
[1]Kumar Chellapilla, David Czarnecki.A preliminary investigation into e-volving modular Finite State Machines, 1999.
[2]Reynolds C W.Interaction with Groups of Autonomous Characters[J].in the proceedings of Game Developers Conference2000, CMP Game Media Group, San Francisco, California, 2000.
[3]涂晓媛.人工鱼[M].清华大学出版社, 2001.
[4]Funge J.AI for Games, Animation:A Cognitive Modeling Approach[M].A.K.Peters, Ltd.Massachusetts, USA, 1999.
[5]Tu X D Terzopoulos.Artificial Fishes:Physics, Locomotion, Perception, Behavior[C].In:ACM computer Graphics Proceedings, Annual Con-ference Series, Proceeding of SIGGRAPH’94, Orlando, Florida, 1994, 7:43-50.
有限状态机模型 篇2
1 FSM在UML模型一致性检测中的基本理论
有限状态机是一个数学模型, 用来表示有限个状态以及在有限个状态之间转移的动作和行为。其形式化术语可以表示为一个五元组 (J, K, T, S, F) , J是一个有穷的非空状态集;K是一个有穷的非空输入集;T是一个从 (J-F) ×K到J的转换函数;S∈J, 是一个初始状态;FJ, 是终态集。有限状态机多用于UML中顺序图与状态图的一致性检测。顺序图和状态图都反映了系统的动态特征, 顺序图中每个对象上的事件都可以引起对象状态的改变, 这种状态的改变就可以反映到状态图中, 从语义角度来说他们互相表达, 但是在建模的时候常常有命名冲突、丢失事件、结构矛盾等不一致的问题出现。而有限状态机可以通过形式化的说明技术表达系统的动态行为。顺序图与状态图通过有限状态机联系起来, 即将顺序图和状态图都用有限状态机的形式进行定义和表示, 构建一个形式化的模型。
2 实现策略比较
2.1 利用Promela检验UML模型一致性
该策略采用SPIN作为模型检验工具, SPIN是一个基于计算机科学的“形式化方法”, 将先进的理论验证方法应用于大型复杂的软件系统当中的模型检测工具。其用于UML模型检测时要把顺序图描述成一组形式化的逻辑语义, 即设一个顺序图包含n条语义踪迹『SD』=<S1, S2, …, Sn>, Si=<msg1, msg2, …, msgk>, 1≤i≤n, 每个语义踪迹转换成一个proctype进程。利用有限状态机将复杂多层结构的UML状态图进行分解, 从而得到多个子状态机, 即多个状态图能组成m条语义踪迹『St Ds』=<t1, t2, …, tm>, 将每个子自动机转换成一个proctype进程, 父自动机与子自动机的关系变为父进程创建子进程。然后将得到的顺序图的形式化描述和由状态图得到形式化描述都转换为SPIN的输入语言——Promela代码。每个顺序图语义进程单独与多个状态图进行一致性检验, 如果满足『SD』中每条踪迹都和『St Ds』中的一条踪迹相符合, 即Si∈『St Ds』 (1≤i≤n) , 那么这个顺序图与所关联的状态图一致。该方法能处理有alt, opt, loop片段的多逻辑语义的顺序图和相关状态图的一致性检验。
2.2 利用LTSA检验UML模型的一致性
标签检查分析器LTSA (Labeled Transition System Analyzer) 是一个一致性系统检查工具。它可以机械的检查满足行为属性的一致性系统的说明, LTSA对于系统的交互式行为能够进行很好的监控和跟踪。有限状态进程 (FSP) 是LST的描述形式, 一个有限标签转换系统P的结构是 (S, L, p, q) , S是一系列的状态;L=∞ (P) ∪{τ}是一系列的标签, ∞ (P) 表示P的字母, τ表示通过LTS环境不能被观察到的内在的动作;p属于 (S·S) , q∈S是初始状态。
要将顺序图与状态图分别用FSP描述出来。首先利用LTSA的一致性检测技术首先将顺序图与状态图通过UML建模工具建立模型, 要求该UML建模工具必须支持XML语言, 即将图保存为XML文档。然后通过编码将XML文档转化为支持FSP的文档。最后通过LTSA将顺序图与状态图的FSP文档输入, 比较两种模型的一致性。该方法利用LTSA得到分析结果, 从存在性和顺序性两个角度对UML模型加以验证。
3 常见的UML模型一致性检测工具
基于有限状态机的模型检测工具主要有许多, 比如美国卡卡耐基梅隆大学开发的SMV, 用来检验一个有限状态机系统是否满足CTL公式;美国贝尔实验室开发的SPIN, 用以检测进程模型是否满足给定的性质;标签转换分析器, 用来机械的检查满足行为属性的一致性系统的说明。这些工具一般都具有以下特点: (1) 图形化的界面, 界面简洁、友好。 (2) 支持有限状态机的形式化建模方法, 达到UML中顺序图与状态图的一致性验证。 (3) 不能够直接进行UML模型间的验证, 必须要将UML模型进行形式化表示, 并编写相应代码后才能进行一致性验证。
4 结束语
综上所述, 由于UML状态图有着比较明显的状态变化, 状态图与顺序图之间又有着密切的联系, 而有限状态机的理论为这种类型的模型之间的相互转换提供了一种比较方便的模型转换实施方案, 同时对其它模型转换方法也有一定的参考价值。依据现有是研究成果, 未来在基于状态机理论基础上的UML一致性检测方面比较有意义的研究领域是:
(1) 完善基于有限状态机UML模型检测的理论研究。
(2) 开发UML模型一致性检测的自动化工具, 检测UML中顺序图、状态图、类图等主要模型的一致性。
(3) 将UML模型一致性检测方法应用与一个系统分析建模的整个过程中, 同时建立符合此类系统的模型检测体系。有限状态机理论已经为UML顺序图与状态图的一致性检测方面提供了充分的依据。但目前还没有一个能够完整的进行系统模型一致性验证的方法和工具, 这需要继续深入的研究。
摘要：UML模型从不同侧面对系统加以描述, 不同间互相印证, 但又存在着信息冗余, 造成模型的不一致。本文对用有限状态机进行一致性验证的理论和方法加以综述, 讨论了两种以有限状态机理论为指导的UML一致性检查的方法、工具, 对以该理论为基础的UML模型一致性检测提出了几个有意义的研究方向。
关键词：有限状态机,一致性检测,SPIN
参考文献
[1]张海藩.软件工程导论 (第6版) [M].北京:清华大学出版社, 2014 (04) .
[2]陈卉, 窦万峰.顺序图与状态图的一致性检测[J].计算机工程, 2008 (09) .
[3]Patrick Goderfroid, Model Checking Software:12th International SPIN Workshop模型检验软件/会议录[M].北京:北京燕山出版社, 2005 (09) .
[4]王洪媛.UML行为模型之间模型转换的研究[D].吉林大学 (博士论文) , 2007.
[5]G J Holzmann.The model checker SPIN[J].IEEE Transactioins on Software Engineering, 1997, 23 (5) :279-295.
有限状态机模型 篇3
1 有限状态机结构
有限状态主要由两部分构成, 包括组合逻辑电路和状态寄存器, 是数字系统中的控制单元, 用来控制有限个状态之间进行相互动作和转移控制中心。有限状态机主要分为Mealy型和Moore型两类。其中, Mealy型有限状态机的输出信号不仅与当前状态有关, 还会受输入变量的影响;而Moore型有限状态机的输出信号只与当前状态有关, 与输入信号没有关系。
由模块图 (a) 及模块图 (b) 可以看出, 无论是Mealy型有限状态机还是Moore型有限状态机都包括了三个部分:次态逻辑、状态寄存器、输出逻辑。其中状态寄存器 (CS) 是维持现有状态不变。当时钟信号变动出现时, 该变动会对状态寄存器进行赋值, 状态寄存器的输入信号就是次态逻辑组合电路的输出信号, 状态寄存器的输出信号就是输出逻辑电路和次态逻辑电路的输入信号。其中, Mealy型有限状态机中, 因为其输出函数是输入信号和当前状态的共同结果, 所以当改变输入信号和状态时钟信号出现变动时, 都会影响信号的输出结果。Moore型有限状态机中, 其输出函数只受当前状态的影响, 因此只有当状态时钟信号出现变动时, 输出结果才会变化。
2 有限状态机VHDL设计方法研究
VHDL作为一种语言, 具备说明数字系统的各种设计的功能。在基于VHDL设计的有限状态机中, 其设计均由VHDL文件来进行描述。VHDL文件包括结构体、参数以及实体三个部分。运用VHDL设计有限状态机的需要遵循一定的程序:首先, 明确系统要求, 建立出符合要求状态转移图;其次, 根据建立的转移图, 进行VHDL设计程序的编写工作;最后, 运用EDA工具对设计程序进行仿真及验证。而传统的有限状态机的设计方法更为繁琐, 需要先制作出状态控制器的设计图, 然后绘制出状态表, 将其中的等价状态项合并在一起, 通过运算得出方程, 最后画出原理图。与传统数字系统设计方法相比较, 运用VHDL设计方法, 可以能够极大的简化整个设计过程, 运用EDA来进行逻辑功能的测试、制作状态表及绘制设计原理图等工作, 提高了工作效率。
基于VHDL设计的Mealy型状态机在现实中也有众多运用, 如自动售卖机等。假设自动售货机内的薯片价格是每袋3元, 一次只能投进一枚0.50元或1.00元的硬币。当投入2.50元后, 如果再投进去1枚1.00元的硬币, 就会找回0.50元并给出一袋薯片;如果再投进去1枚0.50元的硬币, 就只会给出一袋薯片。这就是一个Mealy型有限状态机的问题, 投进硬币的信号就是输入变量, 共有两个;投币时, 自动售货机内已经有的硬币面值就是当前状态, 共有六个;投币完成后自动售货机给出的东西就是输出结果, 共有两个。
基于VHDL设计的Moore型的有限状态机, 要能够清楚分辨出时序逻辑电路与组合逻辑电路。对于组合逻辑电路和状态寄存器, 要分别用不同的PROCESS语句进行描述。其中, 对于时序逻辑电路 (状态寄存器) 的描述, 需要运用IF CP’EVENT AND CP=’1’THEN语句, 同时还要在敏感信号列表中引入时钟信号。此外, 由于Moore型有限状态机的输出与输入变量没有关系, 只与现存状态有关, 因此在对组合逻辑进行描述时, 在判断有限状态机的状态方式上需要选择运用CASE语句, 避免将输出函数变量的赋值语句放在IF-ELSE-END语句中, 而应该将它放在IF-ELSE-END的语句后面。
3 结论
通过本文对有限状态机VHDL设计方法的研究可以看出, 相较于传统有限状态机的设计方法, 运用VHDL设计方法大大简化了设计程序, 降低了设计难度。运用从上至下的VHDL设计方法, 在保证符合系统总体要求的前提下, 一步步的细分设计有限状态机的内容, 然后完成整个设计。
运用VHDL设计有限状态机时, VHDL语言相对独立于设计描述的特性, 不用在意设计电路的内部制造工艺, 也不用思考如何处理电路内部的逻辑关系或结构, 适用于设计逻辑复杂的电路。运用VHDL语言设计有限状态机, 不仅能完美的适应有限状态机复杂的电路, 还极大的提高了有限状态机的性能、效率以及可靠性, 还降低了成本, 缩短了设计所耗费的时间。
参考文献
[1]侯伯亨, 顾新.硬件描述语言与数字逻辑电路设计[M].西安:西安电子科技大学出版社, 1999:173-216.
[2]亲铭, 高明伦.工业控制芯片中状态机的描述方法.合肥:第三届全球智能与自动化大会, 2000:40-67.
[3]邬杨波, 王曙光.有限状态机的VHDL设计及优化[J].信息技术, 2004 (1) :75-78.
有限状态机模型 篇4
OA(Office Automation)办公自动化是采用Internet/Intranet技术,基于工作流的概念,以计算机为基础,各办公人员信息资源共享的高效协同工作方式。办公自动化系统在提高工作效率和强化工作管理上起着非常重要的作用。随着技术的发展,OA系统发展成具有信息发布平台、文档管理自动化、工作流程自动化、业务流程和知识管理于一体的系统。
工作流技术是实现办公流程自动化的主要技术,在OA系统的开发中扮演着非常重要的角色。工作流设计的好坏直接决定着整个OA系统成功或失败。工作流建模目前一般有两种方式:顺序建模,基于状态机的建模。
二、工作流技术
根据工作流管理联盟(Work Flow Management Coalition WFMC)的定义,工作流(Workflow)就是自动运作的业务过程部分或整体,表现为业务参与者对业务相关资源按照规定的章程采取行动,并令相关资源在各参与者之间传递。也就是说,工作流就是一系列相互衔接、自动进行的业务活动或任务,即工作流是业务处理过程的建模。
一个工作流包括一组活动及它们的相互顺序关系,以及每个活动激活或者结束的条件,还包括了对每个活动的描述。工作流通过计算机描述了日常工作中的每个工作流程以及步骤。工作流技术重点研究内容包括:工作流引擎、工作流管理集成机制、建模工具、协同工作机制、流程设计器和流程监控工具等。
目前OA系统设计中用到的主流工作流引擎有:Java领域的JBPM,OSworkflow,还有微软的WF(Workflow Foundation)框架,等等。工作流引擎的使用的原理基本一致,文章中的例子是用微软的WF引擎设计实现。
三、基于状态机模型的工作流
1、状态机概念
状态机是一个有向图形,由一组节点(每个节点称为一个状态)和一组相应的转移函数组成。状态机通过响应一系列的事件来实现各状态间的流转。每个事件都会使状态机从当前节点跳转到“下一个”(也有可能是同一个)节点。这些节点中至少有一个必须是终态。当到达终态,状态机停止。图1所示为一个简单的状态机:
状态机分为两大类:有限状态机和无限状态机。有限状态机的节点数量是有限的,无限状态机则有无限个状态节点。由于工作流程的状态都是有限的,所以这里提到的状态机一般为有限状态机。
基于状态机理念建立的工作流模型称为状态机工作流。
2、状态机工作流建模步骤
状态机工作流建模主要是用状态描述业务动作,用事件驱动方式来连接这些状态,建模的基本步骤如下:
(1)抽象状态。分析业务处理过程中要经历的步骤,把工作分解成多个步骤,最后把这些步骤抽象成状态机的状态。
(2)确定各个状态间转移的事件。由于工作步骤抽象成了工作流的状态,那么现实中使工作业务流转的人物活动或者操作就可以模拟成相应状态机工作流中各个状态相互转移的驱动事件。
(3)完善每个状态所要进行的行为。状态机工作流在每个节点中都要进行相应的自动操作,比如更新数据库、自动发送邮件通知员工、记录系统日记等等,这些功能必须在状态节点上进行描述并实现。
四、基于状态机模型的假期申请审批流程
按照2.2章节的建模步骤,以假期申请审批流程实例来详细说明状态工作流的建模过程。(建模工具使用的是微软的Workflow Foundation工作流设计引擎)。
1、抽象流程状态
建模的第一个步骤就是要把日常工作中“请假”这个活动用计算机语言描述出来,并抽象出这个流程的几个必要状态。
假期申请流程能抽象出什么状态呢?实际生活中,一般请假由个人提出申请,部门经理同意后把申请提交给上级领导,最后等待领导的审批通过后才算请假成功。不难看出,假期申请流程可以抽象出:申请状态、部门经理审批状态、上级领导审批状态、结束状态。各状态如图2所示:
2、假期申请流转触发事件
抽象出假期申请流程各个状态后,下一步就是确定触发各状态间相互流转的事件了。定义“申请状态”为假期申请流程的启示状态,“结束状态”为整个假期申请流程的完成状态。
(1)申请状态响应的事件:申请是由本人提出的,所以处在“申请状态”需要响应“提交申请”事件而使流程转到“部门经理审批状态”。
(2)部门经理审批状态响应的事件:在此状态下,如果“部门经理审批通过”则流程进入“上级领导审批状态”,否则“部门经理拒绝”则流程将返回“申请状态”。
(3)上级领导审批状态响应的事件:“上级领导审批状态”下的事件与“部门经理审批状”基本一致。响应“上级领导审批通过”则流程转到“结束状态”整个工作流结束。响应“上级领导拒绝”则流程将返回“申请状态”。
(4)取消申请事件:在“部门经理审批状态”和“上级领导审批状态”期间申请者可以随时通过“取消申请”事件来结束整个工作流程,所以在这两个状态中需要响应“取消申请”事件使工作流转到“结束状态”。
根据上面4点的分析描述,即可构造出整个假期申请审批流程的有限状态机图。图3所示为假期申请工作流的状态机图,图中的“审核状态”是辅助状态,因为“部门经理审批状态”和“上级领导审批状态”都要响应“申请人取消申请”事件,为了避免事件荣誉,WF工作流引擎可以建立一个辅助状态使得流程在两个状态下都能响应同一个事件。
3、完善各状态的行为
当建立好整个工作流状态模型时,假期申请审批流程的建模也接近完成。最后就是在每个状态下添加相应的行为动作,完善整个工作流的设计。
假期申请审批工作流在每一个状态下都应该有相应的操作。如用户提交申请后应该把申请内容记录进数据库;部门经理和上级领导的审批后也要及时把审批结果保存进数据库;在结束状态时应该把申请的结果及时通知用户,可以通过发送E-MAIL、短信等方式。
根据实际业务需求,给每个状态加入相应操作后,整个假期申请审批工作流状态机建模就完成了。
五、结束语
论文对有限状态机的基本原理进行了阐述,分析了状态机工作流的建模思想和方法,并通过对假期申请审批流程的建模,很好的说明了有限状态机原理在OA系统中的运用。
参考文献
[1]侯培文,刘军利.轻型工作流引擎在工作流管理系统中的应用[J].电脑开发与应用,2010,23(2):37-50.
[2]叶立新,陈阂中,郑航.基于工作流技术的OA系统模型[J].计算机工程与应用,2006(6).
[3]朱征宇,朱庆生.有限状态机的矩阵模型描述[J].计算机科学,2001,28(4):46-47.
[4]刘阳,曹宝香.基于扩展有限状态机的工作流引擎设计与实现[J].计算机工程与应用,2006,42(32):93-96.
有限状态机模型 篇5
按照规定的顺序依次完成各种操作的控制系统称为顺序控制,顺序控制常采用按时间顺序或逻辑顺序进行控制的开环控制方式。顺序控制器一般用于生产过程的开关量控制,如动力设备的启动和停止、加热或制冷设备的接通和断开、信号灯的亮与灭等。
有限状态机主要用于顺序控制当中,即它能采取某种操作来响应一个外部事件。具体采取的操作不仅能取决于接收到的事件,还能取决于各个事件的相对发生顺序。它是一种算法思想,简单而言,有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。其中依据有限状态机的状态转移关系和转移条件,可以把一个非常复杂的程序变成一个依据条件编码内容进行转移的多分支的结构,并很容易用C语言来实现。当我们进行单片机开发时,把有限状态机作为一种思想导入到程序中去,就会找到解决问题的一条有效捷径。
2 基于51单片机用有限状态机算法实现顺序控制
用C语言描述有限状态机的格式如下:
3 具体应用实例
设计一个开关灯装置,该装置在按键k(P3.0引脚)第一次按下时,3盏灯a、b和c同时点亮;当k再次按下时,a灯立刻熄灭,b灯15 s后熄灭,在b灯熄灭18 s后,c灯熄灭。
根据上述要求,设计出的89S51单片机接线图如图1所示,其中,P3.0引脚连接按键k;P2.0、P2.1、P2.2引脚分别连接a灯、b灯、c灯。
根据a灯、b灯、c灯的亮和灭,画出如图2所示的状态转移图。通过图2可以很清楚地看到灯的具体动作。其中,LED0、LED1、LED2分别对应a、b、c灯,“1”和“0”分别代表“亮”和“灭”,而S0、、S1、、S2、、S3分别代表开关灯装置工作的四种状态,key代表按键k。
其源程序如下:
4 结论
在基于51单片机用有限状态机算法实现顺序控制的过程中,顺序控制的程序设计是有规律可循的,可使设计更加简便,降低了开发工业顺序控制器的成本;更可以使开发者思路清晰,为开发者设计出更好、更优质的工业顺序控制器提供一种很有效的方法。
参考文献
[1]DRUMEA A,POPESCU C.Finite state machines and theirapplications in software for industrial control[C]//27thInternationd Sping Seminar.[s.l.]:NSTL,2004,1:25-30.
[2]黄新林,王钢,刘春刚.有限状态机在单片机编程中的应用[J].哈尔滨理工大学学报,2008(4):7-9.
[3]黎文导,卢瑜.有限状态机_FSM_的实现[J].青海师范大学学报(自然科学版),2001(4):18-21.
[4]夏路易.单片机技术基础教程与实践[M].北京:电子工业出版社,2008.
[5]陈勇.有限状态机的建模与优化设计[J].重庆理工大学学报(自然科学版),2007(5):55-58.
[6]徐小良,汪乐宇,周泓.有限状态机的一种实现框架[J].工程设计学报,2003(5):251-255.
[7]张国庆,霍国义.有限状态机设计与实现方法[J].电脑编程技巧与维护,2001(12):42-44.
[8]王家村,罗中明,费战波.用有限状态机法实现单片机系统的加密[J].电测与仪表,2002(4):37-39.
有限状态机模型 篇6
区域稳定控制是确保电力系统安全稳定运行的重要手段[1,2]。控制决策的实现方式一般分为3类:①离线预决策,实时匹配;②在线预决策,实时匹配;③实时计算,实时控制。无论何种方式,控制策略表都是控制的基本依据,稳定控制装置是策略实施的主体,运行方式的识别、扰动状态的判别以及策略搜索、匹配和实施是稳定控制装置的核心内容。
整个稳定控制工程中,控制策略是相对易变的部分。运行部门要经常根据电网运行方式和结构的变化进行稳定分析计算和策略表的更新,稳定控制装置的策略搜索软件也要进行相应的二次开发,稳定控制系统能否按照既定策略正确实施控制,其关键是稳定控制装置中的策略搜索匹配软件流程是否正确、逻辑是否严密,这通常都会涉及大量的编程、测试和验证工作,系统越复杂,问题就越突出[3]。
区域电网安全稳定控装置部署完成后,二次开发工作主要集中在以下2个方面:①策略表的制定。利用电力系统专业工具对电网进行仿真和稳定分析计算,预想多种可能的故障场景,包括运行方式、断面潮流和故障状态等,反复验证稳定控制措施如切机、切负荷或解列等对维护电网稳定的效果,并得到最终的控制策略表。②策略表搜索匹配软件的编制和测试。策略表搜索匹配是根据既定的策略表编写稳定控制装置软件,该软件通过对故障场景的识别,对照策略表的相应条目进行搜索和匹配,获得对应的控制措施并实施,软件编制完成后,研发、工程和用户要进行一系列测试,发现软件中的漏洞并进行修改,现场投运前还要按照策略表进行最后测试。稳定控制工程实施过程中,策略表若需修改或调整,上述过程就要重新进行,而策略表的修订在整个工程中时有发生,随着电力系统规模的扩大、策略复杂性的提高以及投运装置数量的增加,稳定控制工程的二次开发工作面临巨大的挑战。
文献[4,5]针对上述问题进行了有益的探讨。文献[4]提出一种以树状结构形式存放控制策略表的方法,该方法将安全稳定控制策略表分解为接线方式、潮流方式、故障信息、保护动作信息和控制策略5种基本策略元素,每一种策略元素均用一条逻辑表达式表述,并将各策略元素间的关系用树表示,实现了一种有代表性的策略表存储格式。文献[5]提出一种在稳定控制装置中进行策略搜索的方法,将运行方式的确定、策略表的搜索、控制措施的出口3个部分统一考虑,将各种稳定控制系统的不同要求用流程和表格的形式表达,分别使用流程指令和表格结构描述,使其转化成统一的格式,实现了一种控制策略的标准化搜索方案。
研究表明,稳定控制策略表的内容虽然千变万化,但其表述有固定的模式,其核心内容可以抽象为一系列状态、事件、状态迁移、动作等元素的集合,非常适合用有限状态机(FSM)相关理论进行处理,将策略表的存储和搜索用统一的数学模型表达。
本文通过对稳定控制策略实现特征的分析,提出一种以FSM原理为基础的控制策略搜索模型,形成策略表与策略搜索匹配过程统一的数学表达式,实现策略表与搜索匹配软件的解耦,从而可以极大地提高稳定控制工程实施的整体效率。
1 控制策略分析
如前所述,稳定控制策略内容的表述有固定的模式,可以尝试从FSM模型出发,研究稳定控制策略与FSM之间的对应关系,梳理策略实施流程,寻求稳定控制策略的FSM模型表达。
FSM一般可归纳为现态、事件、动作、次态4个要素。这样的归纳,主要是出于对FSM的内在因果关系的考虑。现态和事件是因,动作和次态是果。现态是指当前所处的状态。 事件又称为条件,当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。 动作是指条件满足后执行的动作,动作执行完毕后,可以迁移到新的状态,也可以仍保持原状态,动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态,次态是指条件满足后要迁往的新状态。次态是相对于现态而言的,次态一旦被激活,就转变成为新的现态。
传统上,稳定控制策略一般包括系统运行方式、故障场景、控制策略3项基本要素。稳定控制装置在具体编程过程中要实现策略的搜索、匹配和实施,从FSM模型的角度观察,稳定控制策略的实现过程可以看做是由一系列现态、事件、动作和次态组成。运行方式、断面潮流、开关位置等系统运行状态可以归类为现态,某个故障场景例如短路、跳闸等可以表示为事件,策略的执行例如切机、切负荷可以表示为动作,故障或策略执行导致的系统运行方式变化可以表示为次态。可以看出,稳定控制策略的基本内容与FSM的基本要素有内在关联,可以尝试通过FSM模型得到稳定控制策略统一的数学表达,第3节将给出详细、严格的对应关系。
2FSM
FSM又称有限状态自动机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。FSM是一种概念性机器,能采取某种操作来响应一个外部事件。具体采取的操作不仅取决于接收到的事件,还取决于各个事件相对发生的顺序。之所以能做到这一点,是因为FSM能跟踪一个内部状态,会在收到事件后进行更新。为某一个事件而响应的动作不仅取决于事件本身,还取决于FSM的内部状态。另外,采取的动作还会决定并更新FSM的状态。这样,任何逻辑都可以建模成一系列事件和状态的组合。因此,FSM被广泛应用于计算机、通信、数字逻辑设计、软件工程等领域。
在实际应用中,FSM根据是否使用输入信号分为Moore型和Mealy型2类。Moore型FSM的输出信号仅与当前状态有关,即可以把Moore型FSM的输出看成是当前状态的函数。Mealy型FSM的输出信号不仅与当前状态有关,而且与所有的输入信号有关,即可以把Mealy型FSM的输出看成是当前状态和所有输入信号的函数[6,7]。
Mealy 型FSM是一个6元组,用M表示为:
式中:S为状态有限集合,S={s0,s1,…,sn},s0为初始状态;Σ为输入符号的有限集合,Σ={σ0,σ1,…,σn};Λ为输出符号的有限集合,Λ={λ0,λ1,…,λn};T 为转移函数,SΣ→S;G为输出函数,SΣ→Λ。
上述6元组包含了一组状态集、一个初始状态、一组输入符号集、一组输出符号集、一个映射输入符号和当前状态到下一状态的转移函数的计算模型和输出函数的计算模型。
T的每个元素可以表示为一个5元组,即
式中:t1为T的初始状态;t2为目标状态;t3为来自Σ的输入事件(可以为空);t4为监护条件和输入时间参数等约束;t5为转换执行的动作。
G也可以做类似的表述。当输入符号串后,模型随即进入初始状态,要改变到新的状态,依赖于转移函数。在FSM中,会有许多变量、多重初始状态、基于没有输入符号的转换,或者指定符号和状态的多个转换,指派给接收状态(识别者)的一个或多个状态等很多与事件、转换或状态关联的动作。
显然,稳定控制策略的实现过程也是由一系列现态、事件、动作和次态组成,可以在FSM模型中找到一一对应的映射关系。事实上,任何具有确定因果律的控制系统,其逻辑关系都可以用FSM来描述。
3 映射关系的建立和模型的实现
3.1 映射关系的建立
传统的稳定控制策略搜索软件的流程基本上遵循事先设定的一系列逻辑关系和标准流程,从头到尾顺序执行,文献[4,5]提出的实现方法就是这种面向流程的传统应用程序的典型例子。
本文提出的按照FSM原理建立的策略搜索软件模型是由事件驱动的,在特定状态下采取特定的动作,转换至新的状态或回归初始状态。该方法将策略表和搜索软件用统一的数学模型表达,这种模型与实际系统的动态过程更接近,物理概念更清晰,特别适合用面向对象的编程方法实现。建立映射关系的步骤如下。
1)分析稳定控制策略表的相关内容,将其按照FSM模型元素进行分类。
2)建立稳定控制策略表与式(1)表述的Mealy型FSM模型之间的映射关系,如表1所示。
3)形成策略表与搜索匹配过程的Mealy型FSM模型,其表达式如下:
式中:m1为运行状态集;m2为当前运行状态集;m3为扰动事件集;m4为控制措施集; m5为状态迁移函数;m6为策略搜索函数。
3.2 模型的实现
式(3)模型中表述的策略表内容可以归为3类:①运行状态,表示FSM的各种状态;②扰动事件和控制措施,是FSM的输入、输出;③状态迁移和策略搜索,是策略匹配的过程和FSM的动作。
下面以一条典型的控制策略为例加以说明。某电压等级联络线甲、乙双回运行(S),发生故障(f)单回线跳开导致另外一回线过载(s),需切除丙厂机组x台,丁站负荷y MW。上述策略表内容代入式(3)得:
运行状态、扰动事件和控制措施{S,s},{s},{f},{x,y}是静态内容,策略表形成后就相对固定,表达和处理较为简单,而搜索控制措施的匹配过程{sf→S}, {sf →{x,y}}是动态内容,需要根据扰动输入结合当前运行方式给出控制措施,这部分处理较为复杂,是工作量大且容易出错的环节。
通过FSM模型的表述可以看出,{S,s},{s},{f},{x,y}成为{sf→S}和{sf→{x,y}}输入、输出,实现了策略内容与搜索匹配的解耦。在实际软件编制过程中,采用面向对象技术,将{S,s},{s},{f},{x,y}等内容以抽象类的形式表达,各种同类异构的策略表条目都可通过对象的实例化完成。{sf→S},{sf →{x,y}}的实现原来是一项复杂的工作,传统方式下,这部分编码由人工完成,任务繁重且易出错,逻辑测试和代码寻查非常繁琐。但是,由于FSM的广泛应用,已经形成完整的理论体系和一系列强大的设计工具,可以通过可视化界面完成FSM设计,有的商用设计工具可以直接生成优化的C代码,并可自动完成各种复杂逻辑的测试和校验工作,确保形成的代码不仅逻辑严密而且执行高效。将生成的代码封装成函数形式移植到稳定控制装置的程序中,就完成了软件开发工作。上述设计工具也可专门定制开发,针对性会更好。
采用FSM工具设计策略时,首先创建一个名为System的工程,然后创建名为Table1的策略项,再根据策略表内容设计出各种状态、事件和动作,以及相应的参数、输入和输出,如图1所示。图中:状态1表示甲乙双回线运行;状态2表示一回线故障跳闸,另一回线运行;状态3表示单回线过载运行。单回线故障导致系统状态从状态1迁移到状态2,单回运行过载后系统状态2迁移到状态3;采取切机切负荷动作后,系统从状态3迁移到状态2;故障后若有重合,则系统状态会返回到状态1。
运行Project选项中的Validator功能可以完成FSM的验证,运行Code Generate功能可以生成C代码和头文件,对代码稍加整理,再嵌入到稳定控制主程序中进行调整,就完成了代码开发,可进入实际装置的策略验证和测试环节。
4 效果验证
用传统编程方式处理上述策略,需要先绘制流程图或逻辑框图,然后编写代码并进行调试,整个过程一般需要2.5 h,而采用FSM设计工具,整个过程仅需要0.5 h。此外,还有一个更大的好处,就是将文字描述的策略变成简洁直观的图形表达,策略过程一目了然,完成了状态图便完成了核心代码的编写。特别是在策略调整和修改过程中,FSM设计更具优势。传统方式下,首先要修改逻辑框图,讨论和检查后再进行编码,有时即使框图的逻辑设计正确,但编码环节仍会产生错误;而采用FSM开发的核心逻辑,只要状态图设计正确并通过自动验证,就能保证代码逻辑的正确性。FSM设计工具还提供了完善的归档和管理功能,便于工程维护。显然,用FSM设计工具完成策略搜索和匹配,无论是编程效率还是代码的管理都有质的提升,从而提升了整个稳定控制工程的实施效率和质量。
5 结语
以FSM原理为基础形成的标准化稳定控制装置的策略搜索匹配状态机模型,物理概念清晰,逻辑关系明确,表达形式简洁,与实际系统的动态过程十分吻合,实现了策略表与搜索匹配的解耦,便于软件的编制和测试,减少了稳定控制工程的二次开发工作量,从而极大地提高工程实施的整体效率。
此外,专门开发的根据FSM模型实现稳定控制策略搜索匹配的可视化软件或列写状态方程直接生成代码的工具与基于故障场景的稳定控制测试系统一起,逐步形成完整的稳定控制工程开发和测试的工具链,同时也为稳定控制装置的标准化设计研究提供了理论依据和技术支撑。
参考文献
[1]孙光辉.区域稳定控制中若干技术问题[J].电力系统自动化,1999,23(3):4-7.SUN Guanghui.Techniques in regional stability control[J].Automation of Electric Power Systems,1999,23(3):4-7.
[2]孙光辉.电力系统稳定控制装置的模块化结构[C]//第六届全国继电保护学术研讨会论文集,1996年11月29日-12月2日,深圳.
[3]王亮,王新宝,高亮,等.基于故障场景的区域电网安全稳定控制系统测试方法[J].电力系统自动化,2007,31(18):39-42.WANG Liang,WANG Xinbao,GAO Liang,et al.A faultscenario based method for the regional power grid security andstability control system test[J].Automation of Electric PowerSystems,2007,31(18):39-42.
[4]张岩,王建全,何奔腾.一种新的电力系统稳定控制策略表表述及存储方式[J].继电器,2003,31(12):55-57.ZHANG Yan,WANG Jianquan,HE Benteng.A new method ofexpression and storage on decision table for the stability controlof power systems[J].Relay,2003,31(12):55-57.
[5]孙玉军,邵俊松,方勇杰,等.稳定控制装置的标准化策略搜索技术[J].电力系统自动化,2006,30(22):53-56.SUN Yujun,SHAO Junsong,FANG Yongjie,et al.Standardized decision-searching technique of stability controldevices[J].Automation of Electric Power Systems,2006,30(22):53-56.
[6]MEALY G H.A method to synthesizing sequential circuits[J].Bell System Technical Journal,1955,34(5):1045-1079.
有限状态机模型 篇7
关键词：有限状态机,串行通信总线协议,数控系统
1 引言
随着数字伺服装置的发展,如何实现控制单元与数字伺服装置之间的数据通信成为一个关键问题[1],高速串行通信总线(FSCB,Fast Serial Communication Bus)的通信协议正是为了解决底层设备间通信的高实时性、高可靠性要求,为了掌握自主知识产权而成立的。FSCB通信协议和现有的通用的串行通信协议比较,在某些应用场合具有不可比拟的优势,尤其是在CNC控制器的应用中,用于CNC控制器主机单元和各个功能模块单元之间的通信接口[2]。
有限状态机(Finite State Machine,FSM)是描述和验证网络协议的重要方法之一,是分析协议状态转换的有力工具,本文重点介绍有限状态机在FSCB协议中的应用,尤其是具有相对独立功能的物理层和数据链路层的收发模块。
2 有限状态机
状态机(State Machine)可以说是一个广义时序电路,触发器、计数器、移位寄存器等都算是它的特殊功能的一种。一个状态机由输入激励(转移条件)、当前状态、转移路径(下一状态)和约束条件等几个部分组成。实际时序电路的状态数是有限的,因此又叫做有限状态机(FSM,Finite State Machine)[3]。
由于协议规范的描述通常是复杂和晦涩难懂的,于是产生了用形式化的数学方法来描述协议规范,有限状态机是其中的一种。有限状态机通常用有向图来表示。有向图的节点代表了协议机(发送方或接收方)在每一时刻的状态,有向图的方向弧表示在一定的条件下协议机由一个状态转移到另一个状态。已知协议机的完整描述和信道的特性,把协议机的所有可能状态和相应的转换条件都列出,就可以画出有限状态机的有向图。
FSCB协议规定了有限个状态,并结合输入激励、输出响应等构成了完整的状态机模型,有限状态机大大增强了协议的直观性,尤其是对具有相对独立功能的协议子部分,可以较快的理清协议的流程。同时,有向图还可作为绘制程序流程图的依据。
3 有限状态机在高速串行通信总线协议中的应用
3.1 协议整体模块划分
在IC设计中,目前比较流行的设计方法是自顶向下的设计模式,即先根据整体要实现的功能进行功能划分,划分各个功能模块,定义各个模块的接口,及各个模块的关系。并采用分层的思想,把每一层封装成一个大模块,供上一层调用。FSCB协议的FPGA实现中,也是采用自顶向下的设计模式,采用分层设计的思想来实现。在分层模块设计上,基本上按照FSCB的协议结构,物理层,数据链路层,网络层的脉络。上层模块调用下层模块并加上该层所要实现的功能。在物理层,主要封装成两个模块Inmodule和Outmodule,这两者共同完成FSCB协议中所设计的物理层的工作。前者负责数据接收及相关模块的工作,后者负责数据发送及其相关模块的工作;在数据链路层,用一个Inoutmodule模块来封装,它调用了Inmodule和Outmodule再加上链路层的其他功能;在网路层,主站用Main Protocol,从站用Vice Protocol来封装,它们都调用了数据链路层的Inoutmodule模块,然后再加上网络控制功能[4]。
根据上述FSM的特点,要设计出一个能够实现FSCB协议的FSM,需要找出FSCB协议规定的所有状态,以及各状态之间变化的规则。下面以FSM在物理层的Inmodule、Outmodule模块以及数据链路层的Inoutmodule模块的应用加以说明。
3.2 协议物理层模块
FSCB协议物理层的核心模块是Outmodule,其外围接口如图1所示和模块Inmodule,其外围接口如图2所示。
本模块里包含Idle、SendSync、SendTyte、SendData、Send Ack Y、SendAckN状态,采用有限状态机机制设计,主要功能是检测senddata、sendack_y、sendack_n管脚的跳变。如果senddata有跳变,则调用相关编码模块对outputa[27..0]编码,最后调用并串转换模块按位从data_out端口发送出去。如果sendack_y有跳变,则在会在data_out发送一串特殊的数据帧,sendack_n类似。data_out中发出的数据帧格式如下:
为了节省资源,提高传输效率,握手帧设计得很短,格式如下:
接收模块Inmodule接收到类型位时,只需要判断类型位就可以知道是数据帧,还是接收正确的握手帧,还是接收出错的握手帧。
引脚说明:
outporta[27..0]:输入引脚,要发送的28位数据。
Senddata:输入引脚,发送数据信号,当给它一个跳变时,outport中数据将进行CRC、4b/5b编码,然后从data_out中串行发送。
Sendack_y:输入引脚,发送接收数据正确的握手信号。当给它一个跳变时(正负跳变都可,这样定义主要是为了方便VHDL编程),将有一串特殊的表示数据接收正确的握手帧从data_out中串行发送。
Sendack_n:输入引脚,发送接收数据出错的握手信号。当给它一个跳变时,将有一串特殊的表示数据接收错误的握手帧从data_out中串行发送。
Sendingdata:输出引脚,当正在发送data时,该管脚为高电平,否则为低电平。
Sendingack:输出引脚,当正在发送握手信号时,该管脚为高电平,否则为低电平。
data_out:输出引脚,串行数据输出。
clk:输入引脚,时钟信号。
reset:输入引脚,复位信号,高电平复位。
下面介绍Inmodule模块,它跟Outmodule一起组成物理层的核心模块,共同完成FSCB协议中所规定的物理层的功能。
该模块里面包含Idle、ReceiveSync、ReceiveTyte、Receive Data、ReceiveAckY、ReceiveAckN状态,也采用状态机的方法设计,这些状态跟发送模块是对应的,由于异步模式下缺乏发送端的相位信息,难以保证采样点位于数据的中间位置,即通信“眼图”的中部,该处的数据有足够的保持时间,是最佳判决点,因此该模块主要功能是时刻对data_in端采用5倍频的过采样方法,将介质上传输的数据进行0、1判决,生成接收端数据。当接收到同步信号后,接着对接收到的帧类型进行判断,以确定是数据帧,还是握手帧,如果是接收正确的握手帧,则ack_y的状态会跳变,如果是接收出错的握手帧,则ack_n的状态会发生跳变。如果是数据帧,则对接收到后面的数据调用CRC解码模块进行CRC解码,如果出错,则data_err的状态会发生跳变,如果CRC校验正确,则把调用串并转换模块进行串并转换后的并行数据进行4B/5B解码,然后再inporta端口输出,同时data_ok的状态发生跳变。
3.3 协议数据链路层模块
在数据链路层,封装起来的表示整个数据链路层的模块是Inoutmodule,其外围接口图3所示。
该模块除了把Inmodule、Outmodule封装起来外,还要实现差错控制功能,比如,握手机制的实现,出错重发机制,超时重发机制,经过这些控制后,使得在网络层看来,整个链路是透明的,且是不出错的。
发送的帧的类型有:数据帧、握手帧(接收正确的握手帧和接收错误的握手帧),所以在该模块中必须要解决好它们的互斥和优先级的问题。在本模块中是用状态机的机制来实现的:给数据帧、接收正确握手帧、接收错误握手帧分别给个标志位:sign_data、sign_ack_y、sign_ack_n。当有数据帧要发送时,sign_data置1。当发送完数据帧时,sign_data复位为0,握手帧也一样,模块的状态为:idle、SendingAck_y、SendingAck_n、Sending Data,它们的状态跳转关系如图4所示。
把两个这样的模块连起来,仿真结果如图5所示。从仿真结果可以得出,应用状态机机制设计的Inmodule、Outmodule模块以及Inoutmodule模块的功能全部实现。仿真结果达到预期设计目标。
4 高速串行通信总线在HL—B0408数控系统中的应用
HL-B0408数控系统是本实验室数控团队开发的一款高性能,高精度的数控系统,是基于RTLinux的标准化开放式通用CNC软件系统和基于PC104/FPGA为核心的硬件系统组成。为了检测FSCB协议的有效性,我们将FSCB应用在HL—B0408数控系统中。先进行了单独的FSCB环行网络测试,然后将FSCB应用在数控中。无论是单纯的协议测试还是运行加工代码测试,均在均在两节点通信距离小于20米、以10Mbps的位速率进行通信的条件下,每个测试帧长度均为25字节,在GB/T 13926.4-923级严酷环境下,重复进行协议的通信实时性和可靠性测试,位出错率小于1×10-8,前帧出错率小于1.15×10-7,后帧出错率小于1.15×10-8(等效于在1ms插补周期下、1个子节点时连续运行24小时不出错)。位出错率和帧出错率的测试样本数足够,保证了测试的真实性。结果表明,该协议及总线能够稳定运行,总线的可靠性及可用性得到证明。
5 结束语
高速串行通信总线(FSCB)已经向国家知识产权局申请发明专利,其通信协议按照模块化划分,其中基于有限状态机的Inmodule和Outmodul模块已经经过实际的大量测试,可以做为软IP核在以后的设计中直接使用。FSCB应用到传统CNC系统HL-B0408中,并进行调试,稳定的测试结果表明,FSCB协议是可行的,基于FSCB设计出来的环形通信总线是能实现预先设定的通信指标的。该总线底层通信的成功测试,为下一步的总线接口设计打下了坚实的基础。
参考文献
[1]郇极.CNC系统数字伺服接口协议SERCOS[J].制造业自动化,1997(2):33-35.
[2]陈卫福,杨建武.开放式数控系统及SERCOS接口应用技术[M].北京:机械工业出版社,2003.
[3]李霞,王永章,梁宏斌等.有限状态机在开放式数控系统中的应用[J].计算机集成制造系统,2005(3):428-432.