FPGA之道（52）状态机的概念

前言

本文摘选自《FPGA之道》&＃xff0c;对于状态机&＃xff0c;作者花了大篇幅来叙述&＃xff0c;对于状态机的深刻理解&＃xff0c;让人佩服&＃xff0c;以至于平日里认识到的状态机&＃xff0c;以为就是真理&＃xff0c;可见真理还需要不断的认识。这里为了不让博文篇幅过长&＃xff0c;选择多篇博客来记录状态机这一大知识点。

状态机的概念

状态机简介

简单的说&＃xff0c;状态机就是一幅描绘着状态变迁的状态转移图&＃xff0c;它体现着系统对外界事件的反应和行为。
假设现在是周五的晚上&＃xff0c;经过一周的劳累&＃xff0c;你此刻正躺在床上思考着周六的假日安排&＃xff1a;好久没运动了&＃xff0c;也许明天可以叫上小明一起去踢足球&＃xff0c;听说足球场附近新开了家冷饮店&＃xff0c;运动后再喝杯冷饮那感觉肯定不错。糟糕&＃xff01;天气预报好像说明天有雨&＃xff0c;虽说天气预报的准确性为50%&＃xff0c;但是万一真下雨就没法踢球了&＃xff0c;这样吧&＃xff0c;最近好像刚刚上映了一部大片&＃xff0c;如果下雨的话就约上小强去附近的电影院看电影吧&＃xff0c;顺便吃一顿馋了很久的涮火锅。可是不知道他们两个明天有没有空呢&＃xff1f;现在时间已经不早了&＃xff0c;恐怕他们都睡了&＃xff0c;还是不要打电话过去打扰比较好&＃xff0c;这样吧&＃xff0c;如果下雨或小明没空我就联系小强看电影&＃xff0c;如果他们都没空的话我就自己在家打游戏好了。
至此&＃xff0c;在你的脑海中其实已经完成了一个状态机的设计&＃xff0c;而你在周六一天的行为则可以用如下状态转移图来预见和描述&＃xff1a;

上述便是一个关于状态机的简单例子&＃xff0c;由此可见状态机几乎存在于科研与生活中的各个方面&＃xff0c;而FPGA中的状态机其实跟你脑海中的状态机是很类似的&＃xff0c;因此完全可以主动的采用状态机的思想来帮助我们进行FPGA设计&＃xff0c;以及明确FPGA的行为。
上例中的状态机其实更为准确的称谓应该是有限状态机。事实上&＃xff0c;为了使状态机的实现成为可能&＃xff0c;状态转移图中的内容不可能为无限多&＃xff0c;例如自然数序列——1、2、3、4、5、……&＃xff0c;如果将每一个自然数看做一个状态节点的话&＃xff0c;那么其状态转移图是没有尽头的&＃xff0c;由于状态数目无限&＃xff0c;也就无法被存储&＃xff0c;从而无法被实现。也许你会说&＃xff0c;自然数序列可以看做一个只有两个状态的状态机&＃xff1a;初始状态——输出n&＃61;1、自增状态——输出n&＃61;n&＃43;1&＃xff0c;这样状态便可以存储&＃xff0c;状态机也就可以实现了。很遗憾&＃xff0c;这样的状态机仍然是不可能实现的&＃xff0c;因为此时输出的n值是没有上限的&＃xff0c;我们都知道&＃xff0c;数值越大&＃xff0c;需要占用的存储位宽就越大&＃xff0c;如果n的值没有界限&＃xff0c;那么其最终也是无法被存储的&＃xff0c;从而整个状态机也是无法被实现的。同理可得&＃xff0c;如果状态机的输入没有界限的话&＃xff0c;状态机也是无法被实现的。
综上所述&＃xff0c;有限状态机——Finite State Machine&＃xff0c;简称FSM&＃xff0c;是指状态节点数和输入、输出范围皆有限的状态机&＃xff0c;在本书的其余部分&＃xff0c;如无特别说明&＃xff0c;提到的状态机皆为有限状态机。
最后&＃xff0c;需要明确的一点是&＃xff0c;虽然有限状态机的状态节点和输入、输出皆为有限的&＃xff0c;但这并不意味着它仅能进行有限次的处理&＃xff0c;这是因为有限状态机可以形成闭环系统&＃xff0c;所以可以用有限个状态处理无限的事件&＃xff0c;从而达到化有限为无穷的境界。例如&＃xff0c;宇宙中物质的三个最基本状态——固态、液态、气态——的状态转移图如下&＃xff1a;

从上例可以看出&＃xff0c;虽然该状态机仅有三个状态&＃xff0c;输入&＃xff08;六个触发条件&＃xff09;、输出&＃xff08;状态本身即为输出&＃xff09;也是有限的&＃xff0c;但是它却永远不会结束&＃xff0c;因为宇宙中的物质状态转换永远也不会停止……好吧&＃xff0c;至少几十亿年不会停止。

状态机的组成六要素

简单的了解了状态机之后&＃xff0c;我们来介绍一下组成状态机的六大要素&＃xff1a;

状态集合

状态集合是组成状态机的必备要素&＃xff0c;该集合里包含了状态机所能达到的所有状态。状态集合不能为空&＃xff0c;必须包含至少一个状态节点&＃xff0c;不过通常我们所讨论的状态机都具有至少两个状态节点&＃xff0c;因为如果仅有一个状态节点的话&＃xff0c;状态机便不存在状态跳转现象&＃xff0c;因此它的性质和特点也就得不到体现。例如&＃xff0c;【状态机简介】小节中两个示例的状态集合分别为&＃xff1a;
{起床、找小明、找小强、踢足球、喝冷饮、看电影、吃火锅、打游戏、睡觉}&＃xff1b;
{气态、液态、固态}。

初态

初态是状态机的第二个必备要素&＃xff0c;它是整个状态机开始工作的起点。虽然“先有蛋还是先有鸡”的问题一直没有得到很好的解决&＃xff0c;但是现实中的状态机&＃xff0c;一定要有一个固定的初始状态&＃xff0c;否则你根本无法确定状态机后续的一系列行为。因此&＃xff0c;初态是相对的、而不是绝对的&＃xff0c;它为状态机的其他状态提供了参考坐标&＃xff0c;从而让整个状态机的行为变得可预测、可表述&＃xff0c;这就好比我们平时讨论日期、温度、海拔等等概念一样&＃xff0c;如果没有公元纪元、绝对零度、海平面&＃xff0c;上述所有的一切都变得没有任何意义。
例如&＃xff0c;我们很容易看出【状态机简介】小节中第一个示例的初始状态为——起床。不过对于第二个示例&＃xff0c;初态似乎很难确定&＃xff0c;这时&＃xff0c;请谨记——初态是一个相对的参考态&＃xff0c;因此&＃xff0c;第二个示例中的任何一个状态都可能是初态&＃xff0c;那么到底应该选哪个做为初态呢&＃xff1f;就从你开始观察的那一刻算起吧&＃xff0c;如果你观测的那一刻是固态&＃xff0c;那么初态就是固态。

终态

终态是状态机的结束状态&＃xff0c;即若状态机到达终态&＃xff0c;它的使命也将完成&＃xff0c;从此不再工作。终态与初态不同&＃xff0c;因为它并不是组成状态机的一个必备要素&＃xff0c;事实上&＃xff0c;大部分运行在FPGA上的状态机是没有终态的&＃xff0c;因为它们都需要用有限的状态来处理无限的事件。
例如&＃xff0c;我们很容易看出【状态机简介】小节中的第一个示例的结束状态为——睡觉。不第二个示例中并没有终态&＃xff0c;……好吧&＃xff0c;状态机将会运行至“山无棱、天地合”的那一刻&＃xff01;

输入符号集

输入符号集是驱动状态机进行状态转换的主要因素&＃xff0c;不过状态机的状态转换其实并不一定需要外界的事件触发&＃xff0c;因此输入符号集也不是组成状态机的必备要素&＃xff0c;但是大部分运行在FPGA上的状态机还是需要输入符号集的&＃xff0c;至少大多数情况下&＃xff0c;它们都需要一个复位信号来让状态机进入初态。
例如&＃xff0c;【状态机简介】小节中的两个示例的输入符号集分别为&＃xff1a;
{天气情况、小明空闲情况、小强空闲情况}&＃xff1b;
{气化、液化、凝固、融化、升华、凝华}。

输出符号集

输出符号集是状态机传递给外界的反馈&＃xff0c;不过与输入符号集不同&＃xff0c;输出符号集是组成状态机的一个必备要素&＃xff0c;因为一个对外界毫无影响、或者在外界看来毫无变化的状态机&＃xff0c;其本身就是一件没有任何意义的事情&＃xff0c;因此没有必要存在。
例如&＃xff0c;【状态机简介】小节中两个示例的输出符号集其实非常丰富&＃xff0c;分别概括为&＃xff1a;
{吃了什么&＃xff1f;、喝了什么&＃xff1f;、玩了什么&＃xff1f;……}&＃xff1b;
{温度变化、体积变化、状态变化……}。

状态转移函数

状态转移函数决定了状态机的行为&＃xff0c;它是状态机的必备因素之一&＃xff0c;也是状态机中最重要一个组成因素。状态转移函数的表现形式可以有很多种&＃xff0c;例如带有说明的有向箭头、状态转移表格等等。
例如&＃xff0c;【状态机简介】小节中两个示例的状态转移图形中的有向箭头及附在箭头上的说明。

状态机的工作四要素

状态机在工作的时候&＃xff0c;出于对状态机内在因果关系的考虑&＃xff0c;将状态机的工作状态划分为四个要素——现态、输入、输出、次态。其中&＃xff0c;“现态”和“输入”是因&＃xff0c;“输出”和“次态”是果&＃xff0c;分别介绍如下&＃xff1a;

现态

现态&＃xff0c;是指状态机当前所处的状态。

输入

输入&＃xff0c;一般指外部事件&＃xff0c;当一个外部事件发生后&＃xff0c;状态机便会根据状态转移函数发生相应的状态跳转&＃xff0c;或者状态机将会更新自己的输出情况。通常在FPGA中&＃xff0c;根据输入信号是异步的还是同步的又可将状态机分为异步状态机和同步状态机&＃xff0c;不过鉴于稳定性的考虑&＃xff0c;以后提到和FPGA相关的状态机全部为同步状态机&＃xff0c;而对于异步输入信号&＃xff0c;可以参考【本篇->编程思路->时钟及时钟域->跨时钟域问题】章节中的相关处理方法&＃xff0c;同步化后再送至状态机。

输出

输出&＃xff0c;是由现态或者现态和输入共同决定&＃xff0c;如果这两者都没有变化&＃xff0c;那么输出也不应该有变化。输出符号集是必须的&＃xff0c;但具体到某一状态或者某一输入触发事件&＃xff0c;输出并不是必需的&＃xff0c;有时候带来的仅仅是状态迁移而已。

次态

次态&＃xff0c;是根据现态、输入及状态转移函数所得出的&＃xff0c;状态机将要跳转至的新状态。次态是相对于现态而言的&＃xff0c;一旦状态迁移完成&＃xff0c;次态便成为了新的现态。