用户中心

资讯 > 技术文章

嵌入式开发工程师必备:有限状态机

来源:控制工程网2022.06.15阅读 2049


有限状态机示意图(Finite State Machines)
图片来源:flaviocopes.com

  有限状态机(FSM)的定义是:描述特定(逻辑)过程的一系列事件和动作的数学模型在工程实践中www.cechina.cn,你可以找到无数类似的过程,从简单的通过几个按钮控制电机的FSM控制工程网版权所有, 到可以监控非常复杂的生产制造过程或航天飞机的复杂FSM 系统。
  我曾经为广泛应用于光通信领域的掺铒光纤放大器(EDFA)设计过固件。一个固件部分必须处理E DFA 的安全问题,如果设计不当,EDFA 可能会使用对人体有害的强激光。这似乎是一个常规的FSM 代码设计,但其结果却是一个非常复杂的、难以遵循和维护的冗长过程。需要一种不同的方法来实施FSM,这可能会引起嵌入式代码设计者的兴趣。
  有限状态机理论
  根据有限状态机理论,你可能会想起两种类型的FSM 表示,一种是Mealy 有限状态机,另一种是Moore 有限状态机。这两类FSM 都处理三组变量,一组输入变量X(k), 一组内部状态U(k)和一组输出变量Y(k)。这两类FSM 使用相同的转换函数δ 来映射U x X →
  Mealy 和Moore FSM 的区别在于用于输出状态的第二个映射函数。Mealy 的输出状态映射函数λ 表示U x X → Y 映射,而Mooreλ 表示一个更简单的映射,从U → Y。从实现的角度来看,虽然Mo o re FSM 可能更简单,但Meal y FSM 也有其优势。例如, 与内部状态的数量相比,它可以有更多或不同的输出状态,而在Mo o re FSM 中,每个内部状态都与一个输出状态相关联。
  通用的Mealy FSM 可用下面的表格来表示:

  其中u k 列表示当前的内部状态,x k 行表示当前的输入状态。表格显示下一个内部状态(δ 映射)和相应的输出状态(λ 映射)。

图1 :单级EDFA 安全状态图。

  图1 显示了FSM 另一种更常见的表达形式,即状态图。你可以看到一个完整的单级EDFA 安全序列状态图。
  每个EDFA 使用一个或两个(更常见的两级EDFA)激光泵,将能量提供给EDFA 内的特殊光纤线圈。通过放大器,该能量从上一个节点传输到下一个节点的光信号(光子) 放大。当连接E D FA 和其它节点的光纤断开并且检测到信号丢失(LO S)时,就会出现问题。这种情况必须立即处理,激光功率必须降低或完全切断。其它情况也需要立即关注。整个安全序列是E D FA 固件实施的一部分。
  FSM 的基本实施 
  实现有限状态机(通常用于嵌入式控制软件),最好的编程语言是什么?答案可能是C 语言。还有许多其它更现代的、面向对象的编程语言,但C 语言就像嵌入式系统的“母语言”。一个经验丰富的嵌入式软件设计师, 如何在C 语言中实现这种FSM ?它很可能从这样一个函数开始:

  如果查看上面的代码,您可以看到条件(事件标志组合)如何在满足条件的情况下, 将c u r r State 变量从初始、禁用状态移动/ 更改为下一个状态。每次这样的内部状态变化,都会触发一个特定动作,在某些情况下, 输出状态会触发多个动作。
  到目前为止一切都还正常进行,但随着整个过程变得更加复杂,i f- e l s e 决策语句也变得更加复杂(而且嵌套更深)。然后,如果需要修改任何if-else 决策语句,它可能会影响诸多其它语句。接下来,整个处理功能将需要反复测试。两级E D FA 需要两个类似的FSM 功能,再加上另一个控制A D FA 放大器的FSM 功能,需要做很多工作。
  改进FSM的实现 
  还有另一种方法来表达有限状态机:通过状态转换表(STT) 来实现。STT 是Mealy FSM 描述的另一种形式。这样的表通常有四列,行数根据需要确定。每行描述从当前状态到下一状态的转换。转换由事件(一个或多个事件标志的组合)触发。该动作描述了与转换相关的所有动作。例如,如下是一个STT(只是它的片段),对应于图中所示的状态图。
  为什么这样的表示比状态图更好?因为它可易于实现。下面,来看看如何用C 语言来实现。
  一位经验丰富的软件设计师, 会将FSM 代码拆分成几个源文件, 并从FSM_ example.h 头文件开始,其中包含特殊类型的定义和所有函数的原型。下面是此类头文件的一个示例。


  对于经验不足的程序员来说,前两个定义可能值得解释。每个函数定义一个特定函数指针的名称。在C# 中, 这些定义与使用delegate 关键字的定义相同。它们是C 语言编程中非常强大的工具,使C 程序能够像使用C# 这样面向对象的编程语言,更方便地编写程序。除了最后一个函数外,其它所有函数都应该非常清楚。一类是F_FSM_EVENT_T 类型的函数,它们用于测试某些系统状态(标志),并返回true 或false。请注意IsLosON() 和IsLosOFF()等“成对”的函数。在这种特殊情况下,只需测试一个:通过硬件(H/W)报告的状态/ 标志, 来测试输入信号的丢失。如果检测到信号丢失,此函数将返回true,否则将返回false。第二个函数只是一种封装器,它调用第一个函数并返回一个否定的结果。
  这里定义的第二类函数是F_FSM_ACTION_T 类型。这是“动作”功能,它们控制(打开或关闭)微控制器所需的内部/ 外部设备或一些H /W 电路,整个嵌入式系统由这些电路组成。
  无论FSM 如何实现,都需要这两类功能,例如“状态图”过程或STT 实现。现在,FSM_sstKernel() 函数是一个新功能。它取代了实现函数FSM_stage1() 的“状态图”。它处理ST T 类型的数据。这些数据被定义为S_FSM_STT_T 类型,并作为FSM_sstKernel ()函数的参数。由于FSM_ s st Ke r n e l()需要修改至少一个数据项,因此必须将其作为指向S _ FSM_ STT_ 类型数据的引用/ 指针。

图2 :单级EDFA 安全状态图模拟。

  FSM_sstKernel()所做的事情非常简单。它在S _ FSM_ R OW_ T 类型的行(数组元素)中“循环”, 并查找presentState 与当前内部状态currentState 相同的行。如果找到这样的行,将调用其对应的事件测试函数,并将它们的返回值“a n d - e d”放在一起,以确定是否满足了移动到下一个内部状态的条件。但有个限制,只能将两个逻辑值“and-ed”加在一起。如果需要更多个,则需要通过另一个F _ FSM_ EVENT_T 类型的事件www.cechina.cn,来扩展S_FSM_ROW_T 数据结构。如果内部状态之间的转换,必须将条件/ 事件“or-ed”放在在一起,那又如何处理呢?每个事件(或它们“and-ed”的组合)必须在单独的、但在其它方面相同的行中提供。
  然后,FSM_sstKernel()继续(如果瞬态条件满足)启动在行数据中找到的动作。最后,它将行的nextState 复制到stt 的currentState。
  如果我想使用FS M _ s st Ke r n e l() 来处理更多ST T 行数截然不同的FSM,该怎么办?必须定义ROW_MAX 常量,以满足最长的STTCONTROL ENGINEERING China版权所有,但最好的解决方案是用行的链接列表替换行数组。然后,每个S_FSM_STT_T 型数据, 将使用一个最佳内存空间。然而,一些简单的嵌入式系统,不支持动态分配内存空间。
  现在,在FS M _ s st Ke r n e l()中取消对这两个p r i n tf()语句的注释,可以看到FSM 是如何从当前状态发展到下一个状态的。这显然不适用于嵌入式系统, 但整个代码可能会在P C 机上进行测试, 例如在Microsoft Visual S tudio 中。
  完成和编译 
  一旦FSM _ exa m p l e . h 和 FSM _ example.c 完成后(甚至可以编译它们并创建对应的.o b j 文件),就可以将它们添加到应用程序中。在另一个源文件中,需要创建STT 表。这意味着首先定义ST T 的每一行CONTROL ENGINEERING China版权所有,最后定义STT 本身。然后可以调用FS M _ s st Ke r n e l()函数。您很可能会在F/W 应用程序的main()函数中, 将其作为后台任务之一调用。您可以定义更多这样类似S_FSM_STT_T 变量,并调用FSM_sstKernel()来引用它们。
  为了更好地可视化, 请在MS V i s u a l Studio 下的PC 上编写以下源文件: 

  在编译和运行程序( 以及FSM_ example.h 和FSM_example.cpp)时,如果FSM_sstKernel()中的两个printf() 语句并未注释掉,您应该会看到如图2 所示的结果。(作者 | Peter Galan)
  关键概念: 
  ■检查有限状态机的基本实现。
  ■考察有限状态机实现的改进。 
  思考一下: 
  如果通过一种不同的方法来实施有限状态机?

版权声明:版权归控制工程网所有,转载请注明出处!

频道推荐

关于我们

控制工程网 & CONTROL ENGINEERING China 全球工业控制、自动化和仪器仪表领域的先锋媒体

CE全球

联系我们

商务及广告合作
任小姐(北京)                 夏小姐(上海)
电话:010-82053688      电话:18616877918
rendongxue@cechina.cn      xiashuxian@cechina.cn
新闻投稿:王小姐

关注我们的微信

关于我们 | 网站地图 | 联系我们
© 2003-2020    经营许可编号:京ICP证120335号
公安机关备案号:110102002318  服务热线:010-82053688