FPGA设计中状态机安全性研究

杨宏亮，金炎胜，王刚毅

（1.穆棱卷烟厂，黑龙江穆棱157500; 2.哈尔滨工业大学电子与信息工程学院，黑龙江哈尔滨150001）

随着EDA技术的不断发展，FPGA在各个领域都得到了广泛的应用，而在这些FPGA应用中，绝大部分都使用到状态机的方法，状态机对于每个各自的设计都起着至关重要的作用，一旦状态机出现卡死，也就是出现了通常说的“状态机跑飞”现象，整个设计将无法继续工作。鉴于状态机的设计的重要性，有必要对状态机的安全性进行深入的研究。

本文的研究内容如下：首先，从状态机编码讨论状态机出现卡死的可能性；然后，详细分析状态机“跑飞”现象的原因，并提供几种解决状态机“跑飞”问题的方法；最后，深入研究了EDA工具软件Quartus II中“Safe State Machine”选项选中后对状态机电路带来的影响。

1 导致状态机“跑飞”现象的原因分析

1.1 状态机编码问题

在对状态机进行编码的时候，总是不可避免地会出现大量的剩余状态[1]，即未被定义的编码组合，这些编码组合由于在状态机正常运行时是不需要出现的，所以通常被称为非法状态。

正是由于非法状态的存在，为状态机跑飞现象提供了可能性。

1.2 恶劣工作环境的影响

这个原因比较容易理解，如果最后的产品工作环境比较恶劣，比如工作在太空中，众所周知，太空中存在着各种粒子，受辐射程度很高，FPGA中的存储单元就有可能因为受到各种粒子的撞击而改变其中存储的值[1]。如果状态机中的状态存储器中的一位突然改变了，那么状态机就有可能进入到非法状态。例如：一个3个工作状态采用One-hot编码的状态机，其合法编码组合为“001”，“010”，“100”。如果在状态“001”时，突然其中一位受到影响而翻转了，变成了“101”，现在显然就进入了非法状态，如果没有相应的补救措施，这个状态机就会卡死。

1.3 状态机中有异步输入

也就是说状态机如何跳转不仅仅受当前状态的影响，还受异步输入的控制。为方便分析，举一个带异步输入实例，其状态转换图如图1所示。

图1 一个简单的状态转换图Fig.1 A simple state transition diagram

根据这个转换图，很容易用状态机来实现，下面是一个简单的VHDL程序状态机实现部分：

在上述代码中，sidle，srun，send表示 ST1，ST2，ST3三个工作状态，‘a’为异步输入。用Quartus II对上面代码进行综合，可以得到状态机部分电路如图2所示。

图2 综合的状态机电路图Fig.2 Quartus II integrated circuit of state machine

从状态转换方程中可以看出有两个触发器次态跟异步输入‘a’有关，分别为D1和D3。当a发生变化时，D1和D3的值也会随之发生相应的改变。在时钟clk上升沿到来时，如果输入a稳定保持不变，则D1，D2，D3这三个触发器输出也会稳定，状态机保持正常运行；但是如果a的值也刚好正在变化，情况就变得不可预测了。因为各个触发器D端组合逻辑不尽相同，所以各个组合逻辑产生的延迟也不同。这样，如果在同一时刻，a正在变化，由于延迟不同的缘故，各个触发器所采集到的a的值也会有所不同，可能有的是‘1’，有的是‘0’，还有可能因触发器建立保持时间不够出现亚稳态。假设D1触发器采集到的a为1，而D3触发器采集到的a为‘0’，那么D1和D3这两个触发器的输出就肯定有一个是错误的，从而就有可能导致状态机出现非法状态而卡死。

2 解决的办法

分析完导致状态机跑飞现象的几种原因，针对不同的原因我们可以提出不同的解决方案。问题的解决方案，总是有两种类型：事先预防和事后补救。同样，解决状态机跑飞问题也是如此。

2.1 预防措施

事故的最好解决办法一定是“防患于未然”，事故一旦发生，无论补救措施多么的及时，或多或少都会造成一些损失。状态机跑飞现象也是如此，如果能预防状态机进入非法状态，或者减少状态机进入非法状态的可能性，无疑是一个好办法。

2.1.1 选用合适的编码方式

既然由于大量非法状态的存在，为状态机跑飞提供了可能性，那么减少这种可能性就是一个好的努力方向。对同一个状态机来说，不用的编码方式，其剩余状态可能会不同。Binary编码和One-hot编码是最常用的两种编码方式。

对于Binary编码来说，如果状态数N正好是2的幂次，则不会出现非法状态。然而刚好符合这种情况的时候很少。更一般的情形，如果用到的合法状态数量为N，触发器的数量n=[log2N]，由此非法状态的数量M=2n-N。对于One-hot编码来说，出现非法状态是必然的结果。如果使用到的合法状态数量为N，则设计状态机所需的触发器数量也为N，由此非法状态的数量M=2n-N。假设同样是6个状态，用Binary编码只有两个非法状态，而用One-hot进行编码却有58个非法状态。正因为非法状态的存在，为状态机跑飞提供了可能，而非法状态越多，可能性就越大，单就这一点可以得出：One-hot编码的状态机比Binary编码的状态机更容易跑飞，而且状态机状态数越多，这种趋势越明显。

然而，选用什么样的编码方式对状态机进行编码是一个综合考虑的问题，而并不是说Binary编码剩余状态少就一定要用它对状态机进行编码。事实上，Quartus II的默认编码方式是One-hot编码。

2.1.2 异步输入同步化

这是针对状态机有异步输入的情况。异步输入同步化是一个跨时钟域的问题。对于1.3节中的状态机，因为只是单比特的异步信号，可以通过“双跳”技术来对其进行同步。

图3 双跳以及双跳重新同步Fig.3 Double jump and double jump to re-sync

在图3中b是第一个触发器的输出，a是第二个触发器的输出。理论上说，可以输出准稳态信号，但是实际上准稳态信号会很快稳定下来，不能一直维持其准稳态的状态。所以第二个触发器可用来防止其他电路发现这个准稳态信号。可以看到引入了双跳技术会对输入a延迟1～2个时钟周期，但是一般情况下一个外部事件触发引起FPGA内部一个动作的一个比特位可能发生的频率很小，通常附加几个纳秒对逻辑将不构成影响[2]。

2.2 事后容错机制

有时候，虽然做了足够的预防措施，但是也无法做到能消除一切隐患。事故发生了，就需要及时地采取行动进行补救以减少损失。比如由于恶劣的环境影响，状态机已经进入了非法状态，这件事已经发生了，要能在出现更大损失之前纠正状态机的状态，使其能够自动地回到正常工作状态。所谓“事后”是指状态机进入了非法状态后，而不是出现跑飞之后。

2.2.1 非法状态的处理

正是由于大量非法状态的存在，为状态机跑飞现象提供了可能性，所以理论上如果对所有的非法状态都进行逻辑控制，使能回来正常工作状态上来，就能杜绝状态机跑飞现象。

（1）方法一

假设一个状态机正常用到的状态为“st0”、“st1”、“st2”等3个，用的编码方式是Binary,那么还剩余1个编码组合，也就是说还剩下1个非法状态。这1个非法状态在正常状态机运转的时候用不到，但是现在在枚举状态时，也把这些列上：“undefined”。用VHDL语言表示如下：

定义部分：

实现部分：

这样，即使状态机进入了非法状态“undefined”，由于加入对这个状态的处理，状态机也会重新回到正常工作状态。

这种方法对Binary编码方式来说还可能有效，但是对于One-hot编码来说，因为One-hot编码的非法状态太多了，编写起来过于繁琐，同样是上面的例子，用One-hot来进行编码，就会出现5个非法状态。

（2）方法二

VHDL语法提供了另一种简便的方法，如2.2节所述，利用others语句对未提到的状态进行统一处理。参照2.2节中有关部分重新改写如下：

在others时，state不一定必须指到st0，也可以指到别的状态或者是特定的处理模块。语法上这种方法很有效果，但是实际上会有所不同，例如Quartus、Synplify等EDA工具在综合以上的代码时，会自动忽视others这一行，并不生成相应的电路。这种忽视是有意的，是对状态机进行优化的结果。在绝大多数情况下，状态机不会进入到非法状态，即使在极少数情况下状态机进到非法状态了，用以上的采用冗余方法综合出来的电路所费得资源太多，所以许多EDA工具采取忽视这条语句的做法，而提供了另一条更有效的方法：“安全状态机”。

如果想others这一句不被综合掉，可以选择自己手动对状态机进行编码而不采用声明为状态机的语法。这种编写方法Quartus II无法识别出状态机，自然也就无法对其进行优化，others这一行就能综合处正常的电路来。

图4 一种自动恢复电路模式Fig.4 An automatic recovery circuit mode

一般情况下，这种恢复电路是通过加入组合逻辑来实现的。如图4所示，为了能使状态机恢复正常，在触发器的D端原组合逻辑的基础上，增加了一些新的组合逻辑。这种电路虽然实现了自动恢复的功能，但是也增加了延迟。可能带来一些负面的影响，如可允许的最大时钟频率减小或者达不到触发器建立保持时间等。可以考虑另一种方法：利用D触发器的异步清零端来恢复。当状态机出现异常时，将每个触发器的状态清零。这种方式克服了前一种方法的增加延迟的缺点，但对状态机的编码有一定的要求。对所有的触发器进行清零后，状态机回到了全零状态，所以全零状态必须是一个合法的工作状态。这就要求在对状态机编码时，注意必须要有一个状态是全零。D触发器除了有一个清零端外，还有一个置位端，为什么这里用清零而不用置位呢？这是因为许多FPGA中D触发器没有置位端，只有清零端，要实现置位，必须要加入其他逻辑，所以使用清零端是最高效的方法。

2.2.2 加入检测模块

采用检测模块来检测状态机是否进入非法状态，如果检测到了，就进行一个特殊操作使状态机转入一个特定的状态。以One-hot编码为例：One-hot编码方式有自己的特点,正常状态只可能有一个触发器的状态为“1”,其余触发器的状态皆为“0”,即任何多于1个触发器为“1”的状态均为非法状态。因此,可通过判断是否在同一时刻有多个寄存器为“1”,若有,则启动相关操作来恢复状态机。

2.2.3 选用安全状态机

采用EDA工具中安全状态机。现在EDA工具都提供这一功能。以Quartus II 8.1为例，进入界面后，选择“Assignments-＞settings-＞Analysis&Synthesis settings-＞more settings”，找到“Safe State Machine”，将其设置为“ON”即可。

3 结论

（1）有剩余状态的存在，为状态机跑飞想象的出现提供了可能。剩余状态的多少与编码方式有关系，所以可以通过选择合适的编码方式来尽量减少这种可能性；

（2）在编写程序阶段，设计者对恶劣环境因素的影响是无能为力的。幸好经常遇到的状态机跑飞问题都是由异步输入引起的，利用双跳技术将异步输入同步化即可消除这个因素；

（3）因为不可能彻底消除状态机跑飞的可能性，所以事后容错机制是必不可少的。本文列出了一些容错方法，其中最简单有效的就是选用安全状态机；

（4）要想设计安全健壮，就必须努力减少状态机进入非法状态的可能。安全状态机所谓的“安全”，并不是真正的安全，实际上只是容错机制的一种。

[1]潘松,黄继业.EDA技术实用教程:VHDL版(第4版)[M].北京：科学出版社,2010.

[2]ALTERA CORPORATION.Quartus II Handbook,Version 1:Design and Synthesis[M].2009.

[3]克里兹,孟宪元.高级FPGA设计:结构、实现也优化[M].北京：机械工业出版社,2009.