简述有限状态机（Finite State Machine）的基本概念，描述方法，编码方式和可综合性。

1.基本概念

        有限状态机(Finite State Machine,FSM)在数字系统设计中应用十分广泛。根据状态机的输出是否与输入有关,可将状态机分为两大类：摩尔(Moore)型状态机和米莉(Mealy)型状态机。Moore型状态机的输出仅与现态有关;Mealy型状态机的输出不仅与现态有关,而且和输入也有关。

         FSM一般包括三个部分,其中组合逻辑部分包括状态译码器和输出译码器,状态译码器确定状态机的下一个

状态, 输出译码器确定状态机的输出,状态寄存器属于时序逻辑部分,用来存储状态机的内部状态。

1.1FSM设计基本原则

①安全性。指FSM不会进入死循环或非设计状态。所以在设计中要考虑到尽可能多的情况，比如毛刺等异常扰动，使在状态转移的过程中不会跳转到非设计状态或在跳转到非设计状态后能跳回正常状态。为了设计的安全性，会经常使用“full case”的编码方式，即将所有的状态变量在FSM均有相应的处理。而不同的编码对设计的功耗，频率，稳定性，面积均有影响，所以需要根据设计要求仔细权衡。

②面积与速度。设计满足面积与速度的要求。“面积”指设计所占用的逻辑资源数量。“速度”指设计在芯片上所能达到的最高工作频率。二者互相对立，所以一般的设计目标应是在满足时序要求的基础上，尽量减少使用面积。

③易维护。在描述状态机时要尽量清楚简洁，尤其是几个关键信息，状态变量，状态的输出，状态转移条件。

1.2FSM描述方法

FSM描述的关键在于几个关键的状态要素，如何进行状态转移，每个状态的输出，状态跳转的条件。状态机的实现方式主要有以下三种：

①一段式状态机：指整个状态机的设计写在一个模块当中，在该模块中即描述状态的转移，又描述状态的输入输出。即所谓单进程状态机。一段式状态机只涉及时序逻辑，没有竞争的风险，同时消耗逻辑较少，适用于简单的逻辑设计。当设计较大的状态机时，一段式的状态机就会非常的臃肿，不利于理解和维护，同时也会影响综合器的综合；

②两段式状态机：指整个状态机写到两个模块当中，一个模块用同步时序逻辑描述状态转移，另一个模块用组合逻辑描述状态的转移条件，状态转移规律以及状态的输出。与一段式状态机相比，两段式的好处不仅是有助于阅读和维护，更有助于综合器的优化，有利于约束条件的添加，利于布局布线器的实现。但使用两段式状态机时就需要考虑组合逻辑所产生的竞争冒险，毛刺等不稳定因素。而且组合逻辑不利于约束，不利于综合器和布局布线器的高性能设计。也可以考虑用两个时序逻辑来组成两段式状态机，以增加其稳定性，但在时序上会延时一个周期。

③三段式状态机：三段式状态机是在二段式状态机的设计方法的基础上，使用三个模块来描述状态机。一个模块采用同步时序逻辑描述状态转移。一个模块采用组合逻辑判断状态转移条件，描述状态转移规律。一个模块描述状态的输出，可以用组合逻辑也可以用时序逻辑。虽然三段式状态机设计结构非常复杂，但是带了很多好处：使FSM做到同步寄存器输出，消除了组合逻辑输出的不稳定与毛刺隐患，更利于时序路径分组，有助于综合与布局布线。三段式状态机的关键在于根据状态转移规律，在上一状态根据输入条件判断出当前状态的输出，因而在不插入额外时钟的前提下实现寄存器输出。

1.3FSM的编码

状态编码又称状态分配，在设计当中，不同的编码方式直接影响设计的稳定性，最高工作频率，逻辑资源的使用，可综合性。状态编码一般分为以下几种：

①压缩状态编码：如格雷码(Gray-code)，二进制码(Binary)，随机码（random-code）等等。这类编码方式比较紧凑，需要的寄存器较少，但需要较多的逻辑资源进行编码和解码。如二进制编码，它所需要的触发器数目为，n为实际状态数。因此这类编码方式适用于逻辑资源较多的器件，如CPLD。

②完全一位热编码：如独热码(One-hot)，这种编码方式采用n个触发器来编码n个状态，任意状态只有一位为1，其他位均为0。和压缩状态编码相比虽多用了触发器，但它在状态比较时仅仅需要比较一个位，可有效地节省和简化组合逻辑电路，减少了毛刺产生的概率。对于逻辑资源相对缺乏的FPGA而言，采用完全一位热编码能有效的提高电路的速度和可靠性，也有利于提高器件资源的利用率。因而在大部分FPGA综合器中，默认综合出来的都是独热码。但完全一位热编码在一些特定的场合还是存在着一些缺陷，因而演化出简化一位热编码和零空闲一位热编码。

③简化一位热编码：这种编码方式是用十进制数来指向状态寄存器中的某一状态。状态寄存器中任一时刻只有一位为1，其他全为0，1的位置不同对应的状态也不同。假若判断是否处在状态2，则只需判断state[2]是否等于1，而不是像完全一位热编码一样判断state是否等于4’b0100，即该编码指向的是状态寄存器，而非状态编码。因此这样编码的状态机会比较快。

④零空闲一位热编码：这种编码对应状态之间存在复杂关系的设计可以产生高效的状态机，特别是多个状态跳转到某一特定状态的情况。用这种方式编码时，普通状态的编码是简化一位热编码，而特殊状态用状态寄存器全0来表示。

2.FSM设计的一般步骤

①逻辑抽象，画状态转移图：将实际需求的逻辑关系转化为设计实现的时序逻辑关系，可以用状态转移表或状态转移图。这就需要分析给定的逻辑需求，确定输入、输出和电路状态数。定义输入、输出逻辑状态的含义，确定电路逻辑状态的顺序。按照设计规范的需求画出状态转移图或状态转移表。

②状态化简：如果在状态转移图中出现这样两个状态，它们在相同的输入转换到同一状态，并得到同样的输出，则称它们为等价状态。将等价重复的状态合并到一起，减少电路的状态数，电路的状态数越少，存储电路就越简单。状态化简的目的就是讲等价的状态尽可能的合并，以得到最简的状态转移图。

③状态分配：状态分配即是状态编码，上文已经说明过了。

④选定触发器类型并求出状态方程、驱动方程和输出方程。

⑤按照求出的方程得出逻辑图。

3.FSM的可综合性

FPGA的触发器资源非常的多，而独热码状态机所需的逻辑资源又相对较少，所以一般设计采用FPGA实现的状态机时，综合器会默认综合出独热码状态机。虽然在不添加约束的前提下，综合器不会因为我们的编码而改变其默认的设计，但我们对状态机的描述仍然会极大的影响综合器的综合和布局布线器，影响电路的性能。

一般采用case、casex或casez来建立状态机模型，因为这样的语句清晰明了，可以方便地从当前状态分支转向下一状态并设置输出。同时在写每一个case的时候都不要忘记最后的default，定义未设计状态的指向，使状态跳转至不确定状态或多余状态的时候能在下一时刻跳转回正常工作状态，避免死锁，同时也告诉综合器case语句已经指定了所有的状态，这样综合器就能删除多余的译码电路，使电路简洁且与设计一致。

状态机都应该有一个同步或异步的复位端，以便在上电时将电路复位至有效状态。

如果用if else写出的状态机是有优先级的，而用case语句直接综合出来的状态机同样是有优先级的，所以需要根据设计需求使用full_case和parallel_case综合命令移除设计中的优先编码。

目前大多数综合器都不支持一个always当中由多个事件触发的状态机（即隐式状态机，implicit state machines），为了能综合出有效的电路，用Verilog描述的状态机应明确地由唯一时钟触发。目前大多数综合器不能综合采用Verilog描述的异步状态机。异步状态机时没有确定时钟的状态机，它的状态转移不是由唯一时钟跳变沿触发。所有千万不要用综合工具来设计异步状态机，其综合出来的电路完全不同于所需求设计，如果一定要设计异步状态机，一般采用电路图输入方法而不是Verilog描述。