有限状态机理论

大家好，我是 John Valvano。 在本模块中，我们将讨论有限状态机。 事实证明，有限状态机 是一种强大的设计方法， 它不仅适用于本课程， 还适用于一般的嵌入式系统。 在此期间，您将提高 C 编程技能和调试技能。 尤其值得一提的是，我们将解决有限状态机的 多个相关问题，包括 研究用于构建循线机器人的可行方法。 好，让我们开始吧。 我们将其归类为抽象设计技术， 因为这种方法具有分解系统复杂性的功能， 换句话说，这是它的策略。 我们将在后面出现的状态图中 以图形方式编码或捕捉 这种复杂性。 我们会将系统的功能与其实际工作方式 区分开来。 其实，实施，或者说相应软件， 将会非常简单。 而与它的功能相关的实际 C 代码 则是输出、等待、输入、转到下一状态。 系统将会一遍又一遍地执行该过程。 因此，这种分解使您 能够解决非常复杂的问题， 而且能够展示或证明 它们确实能够在真实的系统中正常工作。 这种抽象设计方法 可让您通过一种非常快捷且可证明的方式 来解决复杂的问题。 而且，跟其他优秀的设计技术一样，这种技术还 为我们提供了一种支持将该系统演化为 更高级系统的方式。 这种有限状态设计方法 可帮助您做到这一点。 好，让我们开始吧。 那么，我们需要先了解状态的本质，对吧？ 因为就机器本身而言， 您会有输入，会有输出， 这就产生了所谓的状态。 因此，我们需要对希望记住的所有知识 进行编码。 所以，在定义状态时，我希望达到的效果是： 我既可以描述我认为真实的情况， 也就是说，当前的情况， 也可以描述我认为将会成真的情况。 例如，在这里这个简单的场景中， 您可以看到两个输入。 我们使用了线路传感器。 在这种情况下，这两个传感器均关闭，因为它们偏离了路线。 有时一个开则两个都开，有时一个开则两个都关。 如果您刚刚注意到了输入， 您会发现这两个状态的输入是相同的。 您看到了吗？ 一个偏左。 另一个则是偏右。 它们具有相同的输入，但是却是不同的 信息。 这两个输入 方向不同。 如果我们能够正确地处理这一点， 我们就能够记住或确定我们处于哪个状态， 这样，我们就能 区分这两个不同的状态。 因此，状态就是您认为是真实的情况。 然后，对于这些状态，接下来我们要做的是， 我们需要把它们连接起来。 这便是我们所说的状态转换图。 我们将通过另一张幻灯片了解其具体结构。 但从根本上来说，状态转换图就是 利用来自过去知识的输入来创建我们现在认为 将会成真的新知识。 在运行过程中，我们必须做点什么。 状态也会有输出，这将会影响系统。 在本例中，我们将会驱动 这个机器人沿路线移动。 重申一下，状态代表 您认为将会成真的情况。 状态转换图则是系统运行 过程中的状态的互联。 我们举个例子。 这是一个交通信号灯。 在这条路上， 会有向北行驶的汽车， 也会有向东行驶的汽车。 这个传感器将告诉您 北向和东向道路的交叉路口 是否有汽车。 这是两个输入。 我们有两个输入，也就是两个汽车传感器。 然后，我们会有六个输出-- 东向道路和北向道路的 红灯、黄灯和绿灯。 所以我们有两个输入和六个输出。 接下来，控制器的操作便是水到渠成了。 它将会查看输入、 做出决策并提供输出。 现在，我们要使用的一个特别的方法是， 我们将会输出、等待、输入、转到下一状态。 因此，过程中编码的软件序列 非常简单。 但是，如上所述，系统行为的复杂性， 将需要通过与系统有关的状态转换图 进行捕捉。 让我们来讨论一下这个转换图的具体结构。 由于我们有一个状态，而且我们有两个输入， 这意味着，每个状态 都将拥有代表所有可能性的 箭头。 我们可以用数字表示。 不妨设为 0、1、2 和 3。 每个状态都有四个箭头。 每个状态也都有一个名称，方便您 了解它的工作方式。 实际上，系统不会使用这种名称， 尤其是在输入-输出方面，但是对于人类来说，这样更为美观， 方便大家了解正在发生什么。 再重复一遍，我们有六个输出。 每个状态都会有输出-- 用于根据意愿来设置信号灯的二进制模式。 然后，由于这个问题因时间而异， 我们将会引入等待状态。 尤其是，如果我要 从北向的绿灯转换成东向的绿灯， 我将会等待五秒钟， 并在这期间使黄灯亮起，以避免系统出现 事故。 所以，有限状态机的结构如下：每个状态都有一个名称、 一个输出、一个等待以及四个次态-- 指向其他状态的箭头--具体依赖于四个可能的 输入值。 控制器主要是解析 该状态图，执行我所在的 这个状态的输出， 等待我所在的这个状态结束，查看我的输入， 然后创建一个指向另外一个状态的状态改变。 下面我们来讨论一下如何设计这样一个 状态图。 我们可以通过两种方法来做到这一点。 如果您愿意，您可以使用图形方式。 或者，您也可以使用表格的方式。 这两者之间实际上是一一对应的。 有些人喜欢图形方式， 而有些人则喜欢表格方式。 在这里，我将会用于读取表格的方式是， 我将会定义状态。 我不必在开始时就知道所有的 状态。 我可以猜测并添加可能的状态。 例如，我可能会先让向北行驶的 汽车通行。 然后，我们再让向东行驶的汽车通行。 我们要设置与该目标相关的信号灯模式。 然后，我可以进一步查看。如果有汽车正在朝北向行驶， 这个方向的信号灯为绿灯， 且路口没有汽车， 我该怎么办？ 我将会保持这种状态不变。 如果有汽车正在向北行驶， 且路口还有其他汽车，而且北向的信号灯为绿灯， 我该怎么办？ 您只需保持该状态即可。 因此，如果只有北向道路上有汽车， 我将会永远保持这个状态。 同样地，如果只有东向的汽车， 不管东向道路没有汽车， 还是只有东向上有汽车，我都将会保持该状态。 而最简单的便是下面这种情况： 如果两个方向上都有汽车，该怎么办？ 您可以看到，如果两个方向上都有汽车， 我将会进行循环。 比如在这里，我将会从 北向绿灯状态开始。 同样，我将会按照该列表向下执行。 下一步，我将会进入这个状态。 然后，在该状态下，假设两个方向上 仍然都有汽车，我将会进入这个状态。 然后，从这个进入这个。 从这个进入这个。 所以，不妨研究一下我们的状态图， 我们看到所有的 11-- 在这里，这种输入代表两个方向上都有汽车-- 不难发现，系统会遍历所有 这四个状态。 在设计状态图时，您要做的是 使用表格形式或图形形式进行设计。 这可以让人类通过直觉来判断， 如果发生这种情况，我知道什么？ 您想要做的是，我知道什么？ 我认为将会成真的情况是什么？ 有了新的输入后，我将会怎样做？ 我现在知道什么？ 只要把以上这几点弄清楚，您便可构建状态图。 图形和表格中的信息量是完全 相同的。 表格的好处是，我可以将表格 用于软件。 这便是我喜欢表格的原因， 因为状态转换表 和实际代码之间的映射 实际上非常直接， 我们可以看一下这个。 我要做的就是 进行编码--请看这里。 这是我的表格。 如果您仔细看，您会发现每行 都是一个状态。 这里是一个goN 状态。 那么，每个状态都有什么呢？ 每个状态都有输出模式。 现在，它恰好是十六进制的，而不是 二进制的。 每个状态都有时间。 而且，它不是以秒为单位，而是以毫秒为单位。 然后，每个状态都有四个次态箭头， 具体取决于输入模式。 相应的输入模式为00、01、10、11。 因此，该状态图的C 编码与该状态图 完全相等-- 我们称为一一对应， 不多也不少。 这是一个非常重要的概念。 因为在设计系统时，我是在这个级别-- 这个较高的级别--进行设计。 但是在运行时，却是映射至这个较低的级别。 而且我知道我没有丢失任何信息。 现在，在这个特殊的实施中， 状态被编码为数字-- 0, 1, 2, 3. 关于状态的信息-- 它的输出、它的时间以及它的四个次态箭头-- 则会编码在这里的这个结构中，通过 这个 typedef 创建。 如果系统有 100 个状态，除了这里 会有 100 行外，其他内容都相同。 同样，如果我有 1,000 个状态，所有这些都是相同的， 只是行数增加。 所以我们会看到，这个问题的复杂性 仅仅会在状态数量方面有所提高， 而不会表现在软件中。 因为软件--运行该状态图的 实际状态机-- 将会是完全相同的，无论您是有 4 个、400 个， 还是 4,000 个状态。 我们来实施一下。 我记得实际的状态是被实施为 0、1、2、3这几个数字。 我将会使用索引， 其中会包含我所在状态的 状态代码。 我将会读取输入。 很明显，我使用了 I/O，因此我需要将其初始化。 然后，我会设置我的初始状态。 这一步会将 cs设置为等于 0。 运行的过程是，我取得现态。 从现态获取输出模式。 然后，使用从前面章节中学到的 用户友好方式将其写出到输出。 每个状态都有且只有一个等待时间。 同样，我将会获取这个等待 状态结束的时间。 并且会实际执行，不管是等待 5 秒还是 30 秒。 第三步是进行输入。 我们已经在前面的章节中学习了如何进行输入。 如果您读取 输入端口的--在本例中是端口 5-- 整个 8 位模式， 我将会对其进行掩码计算，为最后面的两位， 它们分别在 P5.1 和 P5.0 内，选择 0、1、2、3。 这一行比较有趣，也比较复杂。 这是这个非常短的 程序中最复杂的一行代码。 它的作用是，在给出我所在的 现态并给出输入模式后， 得出次态的状态值。 所以，这些 都是变量。 这里只有一、二、三、四、五、六行 C 代码。 而且，无论是有 4 个还是 4,000 个状态， 这个有限状态机都会运行。 我们再来看一下另外一种实施方式。 在前面的例子中，状态被定义成了数字。 现在，我们将会发现它们变成了指针。 现在，我将要采用这个-- 如果您仔细看，您会发现这里是完全相同的-- 看起来和状态图完全一样的结构。 所以这是索引的一种变体。 它跟状态图之间也是一一对应的。 但是这里使用的不是索引，而是 通过指针指向次态。 const 将其放在 ROM 中。 同样，我的状态具有方便人类理解的名称。 而且，这个是 00、01、10、11。 我们会在这里看到什么呢？ 这里的唯一区别在于，不是 把次态编码成一个两位的数字或一个状态 编号，而是将其编码成一个完整的 32 位指针。 后者的运行速度会稍微快一点。 但是，您可以看到，二者的复杂程度是完全相同的。 每个状态都有且只有一行 代码。 我们具有一个输出模式、一个等待 时间和四个次态。 好的，那么-- 同样，运行该状态机的 C 代码 几乎与其他方式相同。 这里的现态被编码为指针， 并被初始化为指向第一个状态。 现在，我将使用指针方法 来读取状态图中的数据。 我将使用指针结构来读取 状态图中的时间。 我会读取掩码形式的输入。 然后，我会使用一个间接的 指针来获得我的次态。 同样，这里这个具有指针映射的 C 程序 与索引版本的速度差不多-- 比后者稍快。 所以，您在这里需要学习这两种方式， 然后使用您最喜欢的方式。 我们提到过--我们使用的是 Moore 状态机。 Moore 状态机是一种 每个状态都具有唯一输出值的状态机。 所以每个状态都有且只有一个输出。 输出的本质在于-- 输出是通过某种方式连接到某个状态。 所以输出便是相应的状态，或者输出会创建相应的状态。 同样，输出表示的是如何处于相应状态， 或者处于相应状态时应该做什么。 但是还有另外一类有限状态机，它们与前者 在数学上等效，但又有一点不同， 它们的输出值同时取决于 输入和现态。 也就是说，每个状态都有一个箭头。 然后，根据输入-- 根据状态和输入， 它会有一个唯一的输出模式。 每个输入与状态组合都拥有 唯一的输出模式。 在这种情况下，每当需要通过 输出来更改状态时， 我们都会使用Mealy 状态机。 如果我有一艘火箭 在太空中飞行， 如果我想要使其停止，那么我必须点击减速火箭。 如果我想要移动，我需要点击点火按钮。 但是，如果我想保持不变，不管是在停止状态还是移动状态下， 我都不提供任何输出。 因此，在需要使用输出来改变状态的情况下， 我们将使用Mealy 状态机。 如果输出意味着处于相应状态或者处于该状态时需要做什么， 我们则会使用Moore 状态机。 好的，总结一下，我们讨论了 被称为有限状态机的抽象设计 方法。 其中有输入， 有输出。 状态则代表知识。 但是这是一种抽象的方法，通过这种方法，您可以说 这是我的交通信号灯控制器。 这是它的功能。 在此图中，我们对其复杂性进行了编码， 虽然并没有很复杂，但这是我的状态机的复杂性。 我们已经看到，我们可以在这里添加 成百上千个状态。 而它的实际运行方式-- 实际的 C 代码，运行它的引擎-- 则总是会分解成非常非常简单的机制-- 在某些地方我们看到仅有还不到 10 行 C 代码。 在下一个视频中，我们将执行另外一个例子。 在本实验中，您将会自己执行一个例子。 好的，请您尽情享受。 这将帮助您构建自己的工具箱， 以便解决一大类问题-- 输入问题、知识问题-- 这里的知识是现态和前态的 函数-- 以及输出问题。 我们看到，还有 一种管理时间的机制。 希望您喜欢本次实验。