Article Outline
TOC
Collection Outline
有限状态机
创建日期： 2021-08-07
#电子电路/数字电路
有限状态机的概念
有限状态机(Finite State Machine，FSM)，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
状态机通过控制各个状态的跳转来控制流程，使得整个代码看上去更加清晰易懂。在控制复杂流程的时候，状态机优势明显。状态机不仅是一种电路的描述工具，而且也是一种思想方法，在电路设计的系统级和 RTL 级有着广泛的应用。
根据状态机的输出是否与输入条件相关，可将状态机分为两大类，即摩尔(Moore)型和米勒(Mealy)型。
（1）摩尔(Moore) 型状态机：组合逻辑的输出只取决于当前状态。Moore机属于异步输出状态机，它的输出仅为当前状态的函数，与当前输入信号状态无关。输入信号通常要到下一时钟周期才会体现在输出信号上。
（2）米勒(Mealy)型状态机：组合逻辑的输出不仅取决于当前状态，还取决于输入状态。Mealy机属于同步输出状态机，它的输出是当前状态和所有输入的函数，其输出会在输入变化后立即发生，不依赖于时钟的同步。
设计FSM的基本步骤
（1）画出状态转移图
（2）确定状态编码和编码方式
（3）给出状态方程和输出方程
（4）编写Verilog代码
三段式状态机
根据状态机的实际写法，状态机还可以分为一段式、二段式和三段式状态机。最常用的是三段式状态机。
三段式状态机使用三个always模块：
- 一个
always模块采用同步时序描述状态转移； - 另二个
always模块采用组合逻辑判断状态转移条件，描述状态转移规律（次态逻辑）； - 最后一个
always模块描述状态输出，可以是组合电路输出，也可以是时序电路输出（输出逻辑）。
为了避免不必要的锁存器生成，需要穷举所有状态对应的输出动作，或者使用 default 来定义未定义状态动作；在定义状态时，推荐使用本地化参数定义 localparam（或parameter），这样可以在编写时状态更清晰且不容易出错，也方便修改；在复位或者跑飞能回到初始态或者预定态；要有异步或者同步复位来确保状态机上电有个初始态。
下面以一个简单的 Moore 型状态机来演示一下， 题目来自 Fsm1 - HDLBits：
这是一个摩尔状态机，有两个状态，一个输入，一个输出。实现这个状态机。请注意，重置状态为 B。
module top_module(
input clk,
input areset, // Asynchronous reset to state B
input in,
output out);//
// Binary Coding 二进制编码
parameter A=0, B=1;
reg state, next_state;
// State transition logic 状态转移逻辑
always @(*) begin // This is a combinational always block
case (state)
A: next_state <= in? A : B;
B: next_state <= in? B : A;
endcase
end
// State flip-flops 状态触发器
always @(posedge clk, posedge areset) begin // This is a sequential always block
if (areset)
state <= B;
else
state <= next_state;
end
// Output logic 输出逻辑
assign out = (state == B);
endmodule
编码方式
用Verilog HDL设计实现有限状态机的关键是状态编码，状态机的状态编码规则对设计实现的状态机性能具有很大影响。常用的编码方式有三种：
（1）顺序码：也称二进制编码(Binary Coding)，就是使用二进制数来表示状态 ,这是一个简单而常用的状态编码方式。
（2）枚举类型状态编码：根据所需要的状态，定义新的枚举类型，并使用枚举类型定义状态变量。
（3）独热编码(One-hot Coding)：也称一位有效编码，就是使每个状态占用状态寄存器的一位。( One-hot)
枚举类型状态编码与顺序编码基本相同，所不同的是书写格式不同，用枚举变量来表示状态具有更好的可读性，多用于小型数字系统设计。
使用独热码看起来好像很浪费资源，但这种编码方法可以简化各组合逻辑电路之间的内部连接，产生较小的且更快的有限状态机。这对于时序逻辑资源比组合逻辑资源更丰富的可编程逻辑器件来说 , 是比较有效的编码方式。所以强烈推荐独热码。
下面是同一个问题，使用二进制编码和独热编码写出来的状态机。问题来源：Exams/2013 q2afsm - HDLBits。
考虑使用更简单的问题，以及另外使用一篇文章单独记载
实现下面显示的状态图描述的 FSM：
module top_module (
input clk,
input resetn, // active-low synchronous reset
input [3:1] r, // request
output [3:1] g // grant
);
/* ============= Binary Code ==================
parameter A=0,B=1,C=2,D=3;
reg [1:0] state,nxt_state;
// state transition table
always @(*) begin
case(state)
A: nxt_state <= r[1]? B:(r[2]? C:(r[3]? D:A));
B: nxt_state <= r[1]? B:A;
C: nxt_state <= r[2]? C:A;
D: nxt_state <= r[3]? D:A;
endcase
end
// state flip-flop
always @(posedge clk) begin
if(~resetn)
state <= A;
else
state <= nxt_state;
end
// output
assign g = {(state==D),(state==C),(state==B)};
================================================ */
// One-hot code
parameter A = 4'b0001;
parameter B = 4'b0010;
parameter C = 4'b0100;
parameter D = 4'b1000;
reg [3:0] state,nxt_state;
//initial state=A;
// state transition table
always @(*) begin
nxt_state[0] <= (state[1]&~r[1]) | (state[2]&~r[2]) | (state[3]&~r[3]) |
(state[0] & ~r[1] & ~r[2] & ~r[3]);
nxt_state[1] <= (state[0] & r[1]) | (state[1]&r[1]);
nxt_state[2] <= (state[0] & (~r[1]) & r[2]) | (state[2] & r[2]);
nxt_state[3] <= (state[0] & (~r[1]) & (~r[2]) & r[3]) | (state[3] & r[3]);
end
// state flip-flop
always @(posedge clk) begin
if(~resetn)
state <= A;
else
state <= nxt_state;
end
assign g[3:1] = state[3:1];
endmodule