状态机的设计

状态机的设计

真正的状态

真正的状态，就是由时序逻辑状态机中状态寄存器所反映出的状态。如果状态寄存器由N个触发器组成，那么状态机就具有$Z^N$个真正的状态。

Summary：状态机的真正状态由状态寄存器决定，状态的数量取决于触发器的数量。

抽象的状态与中间变量

在真正的状态中看到，如此简单地一个时序逻辑，竟然就具有上千个真正的状态，那么稍微复杂一些的时序逻辑，其状态个数岂不是早就已经超出人类处理的极限？看到这里，不知你是否心已凉了半截，对基于状态机的设计思路有些望而却步了呢？千万别慌，因为真正的状态从来都不是FPGA设计者所需要关注的，让我们继续分析上例：

如果说FPGA看到的是时序逻辑中蕴含的真正的状态，那么FPGA设计者看到的就是时序逻辑中蕴含的抽象的状态。如果说人类的大脑具有从复杂事务中提取出简单规律的能力，那么编译器则具有将简单规律还原为复杂事实的能力，这便是现今人类与编译器在FPGA设计环节中所承担的不同角色。因此，当我们设计状态机时，设计的并不是其真正的状态，而是其抽象的状态，事实上，绝大多数情况下，在时序逻辑没有完成最终的布局布线前，我们是无法知道状态机到底有多少个真正的状态的。

Summary：FPGA设计者关注的是抽象的状态而非真正的状态，编译器帮助处理复杂的状态细节。

抽象状态的设计方法

抽象状态与中间变量的权衡

时序逻辑中，真正的状态的状态集合非常之大，且划分得太细，不利于HDL的描述，因此我们通常都是利用抽象的状态来创建状态机。在上一小节中，给出如下等式：

真正的状态＝抽象的状态＋中间变量

上式其实还反映出一个事实，那就是抽象的状态与中间变量之间是可以相互转化的。比如说，如果希望状态机从某一时刻开始，等待N+1个时钟周期后，才开始下一步的工作，那么可以有三种设计方法：

方法一：完全抽象状态法

通过在状态机中插入N个抽象状态——St1～StN，从该时刻开始，状态机进入St1状态，然后后续的每个时钟周期依次进入St2、St3、…、StN状态，最后再从StN跳转到下一步的工作状态即可。

方法二：完全中间变量法

通过创建一个中间变量计数器，从某一时刻开始，状态机对该中间变量进行累加，若计数器的输出等于N，则令次态为下一步的工作状态，否则令次态等于现态。

方法三：折中法

即在状态机中插入M个抽象状态——St1～StM,M<N。同时创建M个计数器作为中间变量，分别为C1～CM。从该时刻开始，状态机进入St1状态同时C1开始计数，当C1输出为N1时，跳转至St2状态同时C2开始计数，如此往复，直到处于StM状态，且CM输出等于NM时，跳转到下一步的工作状态。上述变换只需令N1+N2+…+NM=N即可。

Summary：设计状态机时可以通过抽象状态法、中间变量法和折中法来处理等待时钟周期的问题。

基本状态介绍

初始态

结束态

中继态

状态机中，除了初始态和结束态以外，其余的状态都可以称之为中继态。中继态在状态机的工作中起着承上启下的作用，正是它们组成了从初始态到结束态（如果有）的通路。

分支态

如果一个状态的次态可以有多种不同的可能，那么该状态就是一个分支态。

复位态

空闲态

多余态

例如，若采用one-hot编码方式，状态机必然存在非常多的不可达态，具体原因可参考状态的编码方式。因此，从HDL代码的角度来判断状态机中是否存在着不可达态是很难的，所以一个比较实用且非常推荐的方法就是对每一个状态机都添加一个多余态，从而达到“有则改之无则加勉”的效果。

Summary：状态机中除了初始态和结束态外，还包括中继态、分支态、复位态、空闲态和多余态，多余态用于处理不可达态问题。

状态的一些基本抽象原则

基本原则一：按流程抽象

流程中的每一个事务就可以作为一个状态。

基本原则二：按功能抽象

“你看，咱这个手机不光可以听音乐、看视频、收广播，还可以上网、拍照、玩游戏，倍有面子”等等。这种按照功能来划分出多个事务的思想在人类日常的生活和生产中也经常可以看到，因此，在进行状态机状态的抽象时，如果能够将时序电路所应具有的特征按照功能的思想分解开来，那么功能集合中的每一个事务就可以作为一个状态。

基本原则三：按复杂度抽象

如果发现某些状态过于复杂，那么将再次按照基于流程或者基于功能的思想继续对其进行分解；反之，如果发现某些相邻的状态均过于简单，也可以对它们进行合并。例如，你本来计划晚上花一个小时做语文作业、一个小时做数学作业、一个小时做英语作业，可是今天数学老师发了两套真题作为作业，而语文老师和英语老师都仅留了几道简单的问答题作为作业，那么你显然需要调整计划，调整后的情况大致如下——花一个小时的时间做完语文和英语的作业，花一个小时的时间做完数学真题A套，再花一个小时的时间做完数学真题B套。

由此可见，按照复杂度的状态抽象是对前两种状态抽象思路很好的补充。复杂程度抽象是方法（划分流程），功能是具体方法的实现（功能可以重复使用），流程是骨干用于指引。

Summary：状态抽象时可以按流程、功能或复杂度来进行，目的是使状态机更简洁和高效。

状态的化简

通常来说，我们所设计的状态机的状态数量不会超过十几个，当FPGA芯片内部的资源不是特别紧张时，只要在抽象状态时能够注意保证合理性和逻辑性，其实可以不必太过在意状态集合中是否存在着冗余，因为：首先，此时存在冗余的可能性较小；其次，存在冗余的状态机对于时序逻辑的性能并没有直接影响；再次，状态优化本身也不是一件轻松的工作；最后，还有编译器帮我们进行优化。不过，当状态数量较多，或者状态之间的跳转情况较为繁杂的时候，或者对于一些比较关键的时序逻辑，多花些时间来做状态优化还是十分必要的，因为：首先，编译器的优化能力还是很有限的；其次，较少的状态能够让状态机的描述和实现都更为简洁，从而更容易达到较高性能；最后，状态的化简能够帮助我们理解问题的本质。

什么是状态机的冗余

状态关系表化简法的目的就是要找出状态机中的冗余并剔除它，那到底什么才是状态机中的冗余呢？我们到底该去寻找什么呢？答案是等价状态。对于状态机来说，冗余的实质就是状态集合中存在着等价状态，即若状态A与状态B可以任意替换而不影响状态机的功能行为，那么它们即为等价状态。换句话说，状态A与状态B等价也即状态A与状态B的功能完全一模一样，因此它们两个就没有同时存在的必要了。

这里有一点需要注意，那就是必须是等价的状态才算是状态机中的冗余，如果状态A完成的功能仅是状态B完成功能的一个真子集，那么用状态B来代替状态A是不行的，因为它会扩大状态A的功能；而用状态A来代替状态B也是不行的，因为它会削减状态B的功能。由此可见，为了不影响状态机的功能，能够互相替换的两个状态必须是等价状态才行，因此，只有找到等价状态才算是找到了状态集合中的冗余，进而才可以完成状态的化简工作。

Summary：状态机中的冗余指的是等价状态，通过化简可以减少不必要的状态，提高性能和理解能力。