有限状态机(finite state machine)是一个数学概念，如果把它运用于程序中，可以发挥很大的作用。它是一种协议，用于有限数量的子程序("状态")的发展变化。每个子程序进行一些处理并选择下一种状态(通常取决于下一段输入)。
有限状态机(FSM)可以用作程序的控制结构。FSM对于那些基于输入的在几个不同的可选动作中进行循环的程序尤其合适。投币售货机就是FSM的一个好例子。另外一个你可以想到的复杂的例子就是你正在用的东西，想到了吗？没错，就是操作系统。在投币售货机的例子中，输入是硬币，输出是待售商品，售货机有"接受硬币"，"选择商品"，"发送商品"和"找零钱"等几种状态。
它的基本思路是用一张表保存所有可能的状态，并列出进入每个状态时可能执行的所有动作，其中最后一个动作就是计算(通常在当前状态和下一次输入字符的基础上，另外再经过一次表查询)下一个应该进入的状态。你从一个"初始状态"开始。在这一过程中，翻译表可能告诉你进入了一个错误状态，直到到达结束状态。
在C语言中，有好几种方法可以用来表达FSM，但它们绝大多数都是基于函数指针数组。一个函数指针数组可以像下面这样声明：
void (*state[MAX_STATES]) ();
如果知道了函数名，就可以像下面这样对数组进行初始化。
extern int a(),b(),c(),d();
int (*state[]) ()={a,b,c,c};
可以通过数组中的指针来调用函数：
(*state[i]) ();
所有函数必须接受同样的参数，并返回同种类型的返回值(除非你把数组元素做成一个联合)。函数指针是很有趣的。注意，我们可以去掉指针形式，把上面的调用写成：
state[i] ();
甚至
(******state[i]) ();
这是一个在ANSI C中流行的不良方法：调用函数和通过指针调用函数(或任意层次的指针间接引用)可以使用同一种语法。
如果你想干得漂亮一点，可以让状态函数返回一个指向通用后续函数的指针，并把它转换为适当的类型。这样，就不需要全局变量了。如果你不想搞得太花哨，可以使用一个switch语句作为一种简朴的状态机，方法是赋值给控制变量并把switch语句放在循环内部。关于FSM还有最后一点需要说明：如果你的状态函数看上去需要多个不同的参数，可以考虑使用一个参数计数器和一个字符串指针数组，就像main函数的参数一样。我们熟悉的int argc,char *argv[]机制是非常普遍的，可以成功地应用在你所定义的函数中。
1。状态机的编码 如果寄存器比较多，触发器比较少，采用one-hot编码。这样的话，判断速度与状态无关。采用其他高密度编码方式有可能使用较少的触发器，但是逻辑复杂。 2。对于状态比较多的状态机（例如我在写的deblocking模块，初步估计有300多个clk做完），可以将所有状态分为几个大状态，然后再使用小状态，可以减少状态译码的时间。 3。状态机编写的格式（转自cpchen79 的blog）： always @(posedge clk or negedge rst_n) ... current_state <= next_state; ... always @ (current_state ...) ... case(current_state) ... s1: if ... next_state = s2; ... ... always @(posedge clk or negedge rst_n) ... else a <= 1'b0; c <= 1'b0; c <= 1'b0; //赋默认值 case(current_state) s1: a <= 1'b0; //由于上面赋了默认值，这里就不用再对b 、c赋值了(b、c在该状态为0，不会产生锁存器，下同) s2: b <= 1'b1; s3: c <= 1'b1; default: ... ... 我编写的时候常常把第一个和第三个并为一个，这也是推荐的方式。 4。对于流水线使用 reg->input-->combination logic->reg->output (clk) (clk) 如果组合逻辑比较多的时候，可以采用选通器加反馈的方式，可以减少register的使用。 a.状态机的编码。Biary、gray-code编码使用最少的触发器，较多的组合逻辑。而one-hot编码反之。由于CPLD更多的提供组合逻辑资源，而FPGA更多的提供触发器资源，所以CPLD多使用gray-code，而FPGA多使用one-hot编码。另一方面，对于小型设计使用gray-code和binary编码更有效，而大型状态机使用one-hot更高效。 b.在代码中添加综合器的综合约束属性或者在图形界面下设置综合约束属性可以比较方便的改变状态的编码。如VHDL的示例： Synplicity: attribute syn_encoding : string; attribute syn_encoding of : type is "value "; -- The syn_encoding attribute has 4 values : sequential, onehot, gray and safe. Exemplar: -- Declare TYPE_ENCODING_STYLE. attribute -- Not needed if the exemplar_1164 package is used type encoding_style. is (BINARY, ONEHOT, GRAY, RANDOM, AUTO); attribute TYPE_ENCODING_STYLE. encoding_style; ... attribute TYPE_ENCODING_STYLE. of : type is ONEHOT; Verilog示例： Synplicity: Reg[2:0] state; /* synthesis syn_encoding = "value" */; // The syn_encoding attribute has 4 values : sequential, onehot, gray and safe. Exemplar: Parameter /* exemplar enum */ s0 = 0, s1 = 1, s2 = 2, s3 = 3, S4 = 4; Reg [2:0] /* exemplar enum */ present_state, next_state ; 状态机的编码风格 a.关于FSM的编码方法。FSM分两大类：米勒型和摩尔型。组成要素有输入（包括复位），状态（包括当前状态的操作），状态转移条件，状态的输出条件。 设计FSM的方法和技巧多种多样，但是总结起来有两大类：第一种，将状态转移和状态的操作和判断等写到一个模块（process、block）中。另一种是将状态转移单独写成一个模块，将状态的操作和判断等写到另一个模块中（在Verilog代码中，相当于使用两个“always” block）。其中较好的方式是后者。其原因如下。 首先FSM和其他设计一样，最好使用同步时序方式设计，好处不再累述。而状态机实现后，状态转移是用寄存器实现的，是同步时序部分。状态的转移条件的判断是通过组合逻辑判断实现的，之所以第二种比第一种编码方式合理，就在于第二种编码将同步时序和组合逻辑分别放到不同的程序块（process，block）中实现。这样做的好处不仅仅是便于阅读、理解、维护，更重要的是利于综合器优化代码，利于用户添加合适的时序约束条件，利于布局布线器实现设计。 b.初始化状态和默认状态。 一个完备的状态机（健壮性强）应该具备初始化状态和默认状态。当芯片加电或者复位后，状态机应该能够自动将所有判断条件复位，并进入初始化状态。需要注明的一点是，大多数FPGA有GSR（Global Set/Reset）信号，当FPGA加电后，GSR信号拉高，对所有的寄存器，RAM等单元复位/置位，这是配置于FPGA的逻辑并未生效，所以不能保证正确的进入初始化状态。所以使用GSR企图进入FPGA的初始化状态，常常会产生种种不必一定的麻烦。一般的方法是采用异步复位信号，当然也可以使用同步复位，但是要注意同步复位的逻辑设计。解决这个问题的另一种方法是将默认的初始状态的编码设为全零，这样GSR复位后，状态机自动进入初始状态。 令一方面状态机也应该有一个默认（default）状态，当转移条件不满足，或者状态发生了突变时，要能保证逻辑不会陷入“死循环”。这是对状态机健壮性的一个重要要求，也就是常说的要具备“自恢复”功能。对应于编码就是对case，if－else语句要特别注意，要写完备的条件判断语句。VHDL中，当使用CASE语句的时候，要使用“When Others”建立默认状态。使用“IF...THEN...ELSE”语句的时候，要用在“ELSE”指定默认状态。Verilog中，使用“case”语句的时候要用“default”建立默认状态，使用“if...else”语句的注意事项相似。 另外提一个技巧：大多数综合器都支持Verilog编码状态机的完备状态属性－－“full case”。这个属性用于指定将状态机综合成完备的状态，如Synplicity的综合工具（Synplify/Synplify Pro,Amplify，etc）支持的命令格式如下： case (current_state) // synthesis full_case 2’b00 : next_state <= 2’b01; 2’b01 : next_state <= 2’b11; 2’b11 : next_state <= 2’b00; //这两段代码等效 case (current_state) 2’b00 : next_state <= 2’b01; 2’b01 : next_state <= 2’b11; 2’b11 : next_state <= 2’b00; default : next_state <= 2bx; Synplicity还有一个关于状态机的综合属性，叫“// synthesis parallel_case”其功能是检查所有的状态是“并行的”（parallel），也就是说在同一时间只有一个状态能够成立。 c.使用完备的“if...else”还有一个重要的好处，就是可以避免生成非目的性的“锁存器”（Latch）。详见westor的一篇文章“为什么XST与Synplify的综合结果不一样？” d.状态机的定义可以用parameter定义，但是不推荐使用`define宏定义的方式，因为‘define宏定义在编译时自动替换整个设计中所定义的宏，而parameter仅仅定义模块内部的参数，定义的参数不会与模块外的其他状态机混淆
