原创 FSM的几种“口味”

    FSM是什么？FSM就是Finite（有限） State（状态） 机（Machine）的缩写。（之所以中英文混写，是为了强调学懂FSM的原理是根本，刻意去采用“几段式”的写法并不重要） riple

    FSM的“口味”，说的是FSM的种类和编辑方式，以及由此带来的不同的代码风格。下面就列举几种不同的“口味”，并且给出进一步学习的参考。 riple

    1. “经典分类”——基于状态的Moore型和基于迁移的Mealy型。对于同一个模型，Moore型描述可能会比Mealy型描述需要更多的状态。而且，即使通过添加状态的方法得到了与Mealy型等价的描述，Moore型在对输入的响应速度上也要滞后一个周期。尽管如此，Moore型状态机也有其优势，即状态机输出对输入信号噪声的免疫能力，这一点在小林芳直的《数字逻辑电路的ASIC设计》有明确的论述，甚至建议在ASIC设计中避免使用Mealy型，只使用Moore型描述。在FPGA应用中，往往并不刻意区分两种类型，经常采用两种类型混合后的描述方式。在Quartus II的语言模板里有很好的代码示例和详细说明。 riple

    2. “代码结构”——一段式，两段式和三段式、四段式代码风格。在许多书里，推荐采用两段式或三段式的代码书写风格，不采用一段式的原因是“可能会导致综合工具优化困难”。其实，对于同一个电路，采用上述三种方式都可以描述，只要描述得正确，当今的综合工具都能理解，不会造成优化的困难。所谓的“优化困难”，更多的是由于描述过程中的错误表达方式造成的。相对于两段式和三段式描述方法，一段式描述更简洁，也就更容易表达不清楚，造成综合工具的“优化困难”。 riple

    3. “状态编码”——User-Encoded、One-Hot、Minimal Bits、Gray、Johnson、Sequential方式对状态值进行编码。在Quartus II的Help中查找State Machine Processing logic option条目，可以看到各种编码方式的解释和优缺点。在代码书写中，不需要刻意地按照某种方式编码，只需要在编译选项中加以选择即可。其中，Gray和Johnson方式比较相似。此外，比较少见的还有One-Cold和Two-Hot型。值得一提的是，在《数字逻辑电路的ASIC设计》一书中，作者强调了“江逊编码”方式的优点，其中的“江逊”二字，就是从英文的Johnson翻译成日文，再翻译成中文的结果。 riple

    4. “自动化”——手工编写和图形化输入。据我所知，支持图形化输入状态机，并自动生成代码的EDA工具有三种：Aldec的Active HDL中的State Diagrams输入功能、Xilinx的ISE中的StateCAD、Altera Quartus II 7.2版中最新添加的State Machine File输入功能。此外，Matlab的StateFlow工具也支持HDL代码的生成。这里，强烈推荐使用StateCAD，其优点我以后会给出说明。 riple

    5. “优化”——资源优化和速度优化的实现方式。这里的速度优化，并不是指状态机的输出逻辑延迟（三段式描述中，简单地采用时序逻辑描述Moore型输出电路会导致一个时钟周期的输出逻辑延迟，精心设计的三段式描述可以避免该延迟，这是编写代码是否尽心尽力的问题，是另外一回事），而是指电路的最高运行频率。资源和速度是一对矛盾，简单来说，输出采用时序逻辑会带来速度的提升和资源的增加；反之，输出采用组合逻辑节省资源，但是降低速度。 riple

    6. “安全”——安全和不安全的状态机实现方式。也就是状态机能否从非法状态自动恢复。在《数字逻辑电路的ASIC设计》一书中，自动恢复电路称为“捕弊束缚”电路，是英文booby trap的翻译。在Mentor的一篇关于Precision RTL编译选项的白皮书中，清楚地讲明了一点，安全不安全不取决于编码方式和风格（加入default并不能使电路更安全），而取决于综合工具的选项。在Quartus II的Help中查找Safe State Machine logic option，就可以看到简单的说明。简单来说，实现Safe State Machine会带来资源的增长和速度的下降，但是可靠性会提高一些。还需要说明一点：即使采用了自动恢复电路，状态机从非法状态跳转回了合法状态，从电路运行这个微观角度来说是“安全”的，从状态机的行为这个宏观角度来说，由于状态机进入非法状态和从非法状态返回，以及接下来的运行状态（回到了合法状态并不等于状态机就可以继续正常运行）造成的不正常行为并不是“安全”的。 riple

    7. “输出方式”——同步输出和异步输出方式。其实就是采用资源优化还是速度优化的问题。异步输出表面上看会提高电路响应速度，看似既节省了资源还提高了速度，其实不然（对FPGA结构来说，节省寄存器不等同于节省LE；对同步设计方法来说，异步输出速度上的优势是可以忽略的）；同步输出虽有种种好处，但是用的不得法也仅仅是“形似”而已（比如采用next_state作为同步输出的驱动信号，虽然避免了Moore型输出同步引入的一个时钟周期的滞后，但是状态机内部的组合逻辑反而复杂了）。由于上述原因，所以单列出来，引起注意。 riple

    8. “转移方式”——线性和非线性。这是我新添加的一种分类，分类的依据是状态转移的复杂程度。线性状态机通常是一条线走到底，转移条件仅仅是CLK，这种类型最常见于面向DSP的应用中，用于管理多级流水结构的数据处理过程，通常采用计数器或移位寄存器实现状态寄存器；非线性状态机的状态转移图结构比较复杂，转移条件是众多的输入信号，这种类型最常见于面向控制的应用中，用于应对复杂的外部输入和控制实现复杂的协议，通常很难用简单的计数器来实现，最好采用StateCAD这样的状态图输入工具来设计，既提高了设计效率也有利于创建文档和交流设计意图。 riple

   9. “实现方式”——硬连线（hardwired）和微编码（microcoded）。二者的区别在于次态生成逻辑的实现方式，前者采用基本组合逻辑器件，后者采用ROM或RAM器件。从次态逻辑的真值表看来，二者完全等价，这是由于ROM或RAM可以以查找表的工作方式在功能上模拟组合逻辑，实现任意的布尔等式。采用硬连线实现方式可以有效地利用LE中包含的LUT组合逻辑，非常适合FPGA的底层结构，而且FSM的跳转逻辑可以用行为级HDL进行描述，综合工具对行为级HDL描述的FSM可以很好地识别和优化；微编码方式的FSM如果采用RAM实现，就可以动态修改FSM的功能，以一当十，而且由于复杂的组合逻辑可以采用一片或几片存储芯片实现，简化了电路，适合采用离散器件实现。StateCAD生成的都是硬连线方式的FSM，Altera参考设计中提供的Avalon State Sequencer属于微编码的FSM，虽然它采用了组合逻辑与RAM的混合实现方式。采用微编码方式实现的状态机，通常被称为Microsequencer。由于这一类状态机的功能可以重新编程，相当于简单的MCU，所以可以以LSI芯片的形式大批量生产并用于不同的产品中。AMD曾经生产这种芯片，型号是2910。

    背景资料：Maximizing Performance and Reliability of FSMs with Precision Synthesis riple