一、有限状态机FSM（Finite State Machine）

组成元素：
        输入、状态、状态转移条件、输出。

 

可以分为两类：
        Mealy状态机：时序逻辑的输出不仅取决于当前状态，还与输入有关；

        Moore状态机：时序逻辑的输出只与当前状态有关。

 

描述方式：
        ① 状态转移图：设计分析时使用，工具自动翻译的代码效率不高，适合规模小的设计；对于大规模设计，HDL更好；

        ② 状态转移表；

        ③ HDL描述。

 

设计步骤：
        ① 逻辑抽象，得到状态转移图：确定输入、输出、状态变量、画状态转移图；

        ② 状态简化，得到最简的状态转移图：合并等价状态；

        ③ 状态编码：binary、gray、one-hot编码方式；

        ④ 用HDL描述。

 

二、Coding Style

一段式：
        只有一个always block，把所有的逻辑（输入、输出、状态）都在一个always block的时序逻辑中实现。这种写法看起来很简洁，但是不利于维护，如果状态复杂一些就很容易出错，不推荐这种方法。

        在简单的状态机可以使用。

 

二段式：
        有两个always block，把时序逻辑和组合逻辑分隔开来。时序逻辑里进行当前状态和下一状态的切换，组合逻辑实现各个输入、输出以及状态判断。这种写法不仅便于阅读、理解、维护，而且利于综合器优化代码，利于用户添加合适的时序约束条件，利于布局布线器实现设计。在两段式描述中，当前状态的输出用组合逻辑实现，可能存在竞争和冒险，产生毛刺。

        要求对状态机的输出用寄存器打一拍，但很多情况不允许插入寄存器节拍，此时使用三段式描述。其优势在于能够根据状态转移规律，在上一状态根据输入条件判断出当前状态的输出，从而不需要额外插入时钟节拍。

 

三段式：
        有三个always block，一个时序逻辑采用同步时序的方式描述状态转移，一个采用组合逻辑的方式判断状态转移条件、描述状态转移规律，第三个模块使用同步时序的方式描述每个状态的输出。代码容易维护，时序逻辑的输出解决了两段式组合逻辑的毛刺问题，但是从资源消耗的角度上看，三段式的资源消耗多一些。

        模板如下：

always @ ( posedge clk or negedge rst_n ) 
    begin  
        if ( !rst_n )  
            CS <= IDLE;  
        else  
            CS <= NS;  
    end  
  
always @*  
    begin  
        NS = 'bx;                   //初始化寄存器，避免生成latch  
        case (CS)                   //注意为CS  
            IDLE: begin  
                  end;  
            S1: begin  
                end;  
            default:  
                NS = 'bx;           //与硬件电路一致  
        endcase  
    end  
  
always @ (posedge clk or negedge rst_n) 
    begin  
        if ( !rst_n ) 
            begin  
            end  
        else 
            begin  
                ...                 //初始化一组值，避免latch  
                case (CS/NS)        //这里有2种写法，推荐NS写法（moore型写法） 
                    ...  
                    default: ;  
                endcase  
            end  
    end  

 

下面，举例说明：

        状态转换图如下所示：



 

一段式：
    //时序逻辑电路
	always @(posedge clk or negedge rst_n)
		begin
			if(!rst_n)
				begin
					cstate <= IDLE;
					cmd <= 3'b000;
				end
			else
				case(cstate)
					IDLE:
						if(wr_req)
							begin
								cstate <= WR_S1;
								cmd <= 3'b001;
							end
						else if(rd_req)
							begin
								cstate <= RD_S1;
								cmd <= 3'b011;
							end
						else
							begin
								cstate <= IDLE;
								cmd <= 3'b000;
							end
					WR_S1:	begin
								cstate <= WR_S2;
								cmd <= 3'b010;
							end
					WR_S2:	begin
								cstate <= IDLE;
								cmd <= 3'b000;
							end
					RD_S1:
						if(wr_req)
							begin
								cstate <= WR_S2;
								cmd <= 3'b010;
							end
						else
							begin
								cstate <= RD_S2;
								cmd <= 3'b100;
							end
					RD_S2:
						if(wr_req)
							begin
								cstate <= WR_S1;
								cmd <= 3'b001;
							end
						else
							begin
								cstate <= IDLE;
								cmd <= 3'b000;
							end
					default:	cstate <= IDLE;
				endcase
		end

testbench如下： 

`timescale 1 ns/ 100 ps

module fsm1_vlg_tst();

	reg clk;
	reg rd_req;
	reg rst_n;
	reg wr_req;                                             
	wire [2:0]  cmd;
	wire [2:0]  cstate;
                          
	fsm1 i1 (   
		.clk(clk),
		.cmd(cmd),
		.cstate(cstate),
		.rd_req(rd_req),
		.rst_n(rst_n),
		.wr_req(wr_req)
	);
	always #10 clk = ~clk;
	
	initial                                                
		begin
			clk = 0;rst_n = 1;
			wr_req = 0;rd_req = 0;
			#2 rst_n = 0;
			#10 rst_n = 1;
			repeat(100)
				begin
					#20 wr_req = {$random}%2;
						rd_req = {$random}%2;
				end
			#100 $stop;
		end                                                    
                                                    
endmodule

功能仿真波形图：



 

 三段式：

always block①：时序逻辑

//1st always block, sequential logic, store current state
always @(posedge clk or negedge rst_n)
		if(!rst_n)
			cstate <= IDLE;
		else
			cstate <= nstate;

 

always block②：组合逻辑 

//2nd always block, combinational logic, decide next state
always @(cstate or wr_req or rd_req)
		begin
			case(cstate)
				IDLE:	if(wr_req)
							nstate = WR_S1;
						else if(rd_req)
							nstate = RD_S1;
						else
							nstate = IDLE;
				WR_S1:		nstate = WR_S2;
				WR_S2:		nstate = IDLE;
				RD_S1:	if(wr_req)
							nstate = WR_S2;
						else
							nstate = RD_S2;
				RD_S2:	if(wr_req)
							nstate = WR_S1;
						else
							nstate = IDLE;
				default:	nstate = 3'bx;
			endcase
		end

 注意：
        always @（敏感电平信号）需要列举完全，可以用“@*”或者“@（*）”代替；

        case（表达式）中的表达式为“cstate”，即现态；

        阻塞赋值“=”；

        default项中“'bx”必须设置，与实际电路一致。

 

always block③：时序逻辑 

//3rd always block, FSM sequential output

Mealy型写法：
always @(posedge clk or negedge rst_n)
		if(!rst_n)
			cmd <= 3'b000;
		else
			case(cstate)
				IDLE:	if(wr_req)
							cmd <= 3'b001;
						else if(rd_req)
							cmd <= 3'b011;
						else
							cmd <= 3'b000;
				WR_S1:		cmd <= 3'b010;
				WR_S2:		cmd <= 3'b000;
				RD_S1:	if(wr_req)
							cmd <= 3'b010;
						else
							cmd <= 3'b100;
				RD_S2:	if(wr_req)
							cmd <= 3'b001;
						else
							cmd <= 3'b000;
				default:;
			endcase

注意：
        case（表达式）中的表达式为“cstate”，即现态；

        非阻塞赋值“<=”； 

        default项必须设置。

 

Moore型写法：
always @(posedge clk or negedge rst_n)
		if(!rst_n)
			cmd <= 3'b000;
		else
			case(nstate)
				IDLE:	cmd <= 3'b000;
				WR_S1:	cmd <= 3'b001;
				WR_S2:	cmd <= 3'b010;
				RD_S1:	cmd <= 3'b011;
				RD_S2:	cmd <= 3'b100;
				default:;
			endcase

endmodule

注意：
        case（表达式）中的表达式为“nstate”，即次态，这里使用nextstate和state的区别在于，当状态跳转时，基于nextstate的输   出是立刻变化的，而基于state输出会延迟一个周期，其他情况都一样，应该根据自己的时序要求，选择用nextstate还是state。

        非阻塞赋值“<=”； 

        default项必须设置。

 

 

参考状态机详解，以及三段式状态机的思维陷阱。

参考《大数据日知录》

2PC与3PC场景
这两者是常用解决分布式事物的方式，保证在分布式事物中要么都提交事物，要么都取消事物。
二段式提交（2PC）
主要有两个阶段：

准备阶段
提交阶段

主要步骤如下：

4. 步骤一，协调者询问参与者是否可以提交。

5. 步骤二，参与者告知提交者可以提交。

6. 步骤三，协调者让参与者发送提交请求。

7. 步骤四，参与者提交完毕后告知协调者已经提交完毕。


二段式提交的问题
在上面步骤三中，如果协调者发送提交请求给了一半的参与者之后就出了问题，那么就会出现有长时间阻塞的情况。
打个比方，上图中参与者2和3收到了提交请求，但是4和5没有收到提交请求，这时候4和5就会进入阻塞状态，等待协调者恢复后发送提交请求给它。
如果在很长时间后协调者还是没有发送提交请求给它，那么会认为协调者无法恢复，会重新选出一个协调者来进行事物提交。

在这种极端差的情况下，2和3已经提交的事物是需要回滚的。
三段式提交（3PC）
三段式提交是二段式提交的改进，主要就是为了解决二段式提交长时间阻塞的问题。

实现上，主要是加入了一个“预提交阶段”。
主要有三个阶段：

准备阶段
预提交阶段（下面的步骤三和步骤四）
提交阶段

主要步骤如下：

步骤一，协调者询问参与者是否可以提交。
步骤二，参与者告知提交者可以提交。
步骤三，如果所有参与者都可以提交，协调者会将这个信息告知参与者。
步骤四，单个参与者知道所有参与者都准备完毕可以提交，向协调者发送“预提交”请求。
步骤五，协调者让参与者发送提交请求。
步骤六，参与者提交完毕后告知协调者已经提交完毕。

在三段式提交情况下，如果在预提交阶段出现了协调者宕机的情况，是不需要回滚事物的。

如果是在提交阶段出现了协调者宕机的情况，可以通过时延来自动提交。（因为可以确定其他参与者也会提交，一致性就得以保证）
两者比较
3PC与2PC相比，主要是保证了在“协调者”单点故障情况下参与者的一致性。

但是并不能保证整个系统的一致性，如果是”参与者“故障还是会存在长时间阻塞的情况。
目前3PC在实际系统中很少使用，主要原因有如下两点：

2PC中由于”协调者“单点故障出现长时阻塞的情况很少出现。
由于3PC多引入了一个阶段，因此”协调者“与”参与者“之间多了一层通讯，效率与2PC相比太低。

上篇博文讲了：FPGA中有限状态机的状态编码采用格雷码还是独热码？

那篇博文讲了状态机的状态编码是用格雷码还是独热码的问题，以及两者之间的优劣。状态机的描述方式采用的是一段式描述方式，也就是将整个状态机全部写到一个always模块中去。

这篇博文仍用上篇博文的案例，说说状态机的描述方法。一段式的描述方法、二段式以及三段式，并比较三者之间的功能仿真情况，最后真心吐露这个案例的状态转移图的疑问？不能把有问题的地方回避，我想我不要做这样的人。

首先看看状态机的描述方法，和编码方式，这两段描述借鉴：基于Verilog HDL的有限状态机，人家说的不错，我也懒着码字了。

状态机的描述方法


状态机的描述方法多种多样，将整个状态机写到１个always 模块里，在该模块中既描述状态转移，又描述状态的输入和输出，这种写法一般被称为一段式FSM 描述方法；

还有一种写法是使用两个always模块，其中一个always 模块采用同步时序的方式描述状态转移，而另一个模块采用组合逻辑的方式判断状态转移条件，描述状态转移规律，这种写法被称为两段式FSM 描述方法；

还有一种写法是在两段式描述方法的基础上发展而来的，这种写法使用3 个always模块，一个always 模块采用同步时序的方式描述状态转移，一个采用组合逻辑的方式判断状态转移条件，描述状态转移规律，第三个always 模块使用同步时序电路描述每个状态的输出，这种写法称为三段式写法。

 


状态机的状态编码


二进制码（Binary）和格雷码（Gray）属于压缩状态编码，这种编码的优点是使用的状态向量最少，但是需要较多的逻辑资源用来状态译码。二进制码从一个状态转换到相邻状态时，可能有多个比特位发生变化，易产生中间状态转移问题，状态机的速度也要比采用其它编码方式慢。格雷码两个相邻的码值仅有一位就可区分，这将会减少电路中相邻物理信号线同时变化的情况，因而可以减少电路中的电噪声。Johnson码也有同样的特点，但是要用较多的位数。

独热码（One-hot）指对任意给定的状态，状态寄存器中只有l位为1，其余位都为0。n状态的有限状态机需要n个触发器，但这种有限状态机只需对寄存器中的一位进行译码，简化了译码逻辑电路，额外触发器占用的面积可用译码电路省下来的面积抵消。当设计中加入更多的状态时，译码逻辑没有变得更加复杂，有限状态机的速度仅取决于到某特定状态的转移数量，而其它类型有限状态机在状态增加时速度会明显下降。独热码还具有设计简单、修改灵活、易于综合和调试等优点。独热码相对于二进制码，速度快但占用面积大。


给出实际案例：

下面是一个状态转移图，我们接下来就这个状态转移图来用不同的描述方式来描述。



1）一段式描述方法：

`timescale 1ns / 1ps
//
// Company: 
// Engineer: 
// 
// Create Date:    21:27:04 09/02/2018 
// Design Name: 
// Module Name:    fsm 
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//
module fsm(
    input Clock,
    input rst_n,
    input A,
    output F,
    output G
    );
reg F, G;
reg [3:0] state;
	
parameter Idle = 4'b1000, Start = 4'b0100, Stop = 4'b0010, Clear = 4'b0001;
	
always @(posedge Clock) begin
 
if(!rst_n) begin
	state <= Idle;
    F <= 1'b0;
    G <= 1'b0;
end
else
	case(state)
	
	Idle: begin
	if(A) begin
		state <= Start;
		G <= 1'b0;
	end
	else
		state <= Idle;
	end
	
	Start: begin
	if(!A)
		state <= Stop;
	else
		state <= Start;
		
	end
	
	Stop: begin
	if(A) begin
		state <= Clear;
		F <= 1'b1;
	end
	else
		state <= Stop;
	
	end
	
	Clear: begin
	if(!A)begin
		state <= Idle;
		F <= 1'b0;
		G <= 1'b1;
	end
	else
		state <= Clear;
	
	end
	
	default: state <= Idle;
	
	endcase 
	
end	
	
 
endmodule


给出测试文件，测试文件在这个案例中通用：

`timescale 1ns / 1ps


// Company: 
// Engineer:
//
// Create Date:   23:39:28 09/02/2018
// Design Name:   fsm
// Module Name:   G:/modelsim_file/fsm01/fsm_tb.v
// Project Name:  fsm01
// Target Device:  
// Tool versions:  
// Description: 
//
// Verilog Test Fixture created by ISE for module: fsm
//
// Dependencies:
// 
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
// 


module fsm_tb;

	// Inputs
	reg Clock;
	reg rst_n;
	reg A;

	// Outputs
	wire F;
	wire G;

	// Instantiate the Unit Under Test (UUT)
	fsm uut (
		.Clock(Clock), 
		.rst_n(rst_n), 
		.A(A), 
		.F(F), 
		.G(G)
	);

	initial begin
		// Initialize Inputs	
		rst_n = 0;
		A = 0;
		
		#30 A = 1;
		rst_n = 1;
		#30 A = 0;
		#20 A = 1;
		#20 A = 0;
		

		// Wait 100 ns for global reset to finish
		#100;
	
	end
	initial begin
		Clock = 0;		
		forever #10 Clock = ~Clock;
	end
      
endmodule



功能仿真：



两段式描述方法：

`timescale 1ns / 1ps
//
// Company: 
// Engineer: 
// 
// Create Date:    21:27:04 09/02/2018 
// Design Name: 
// Module Name:    fsm 
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//
module fsm(
    input Clock,
    input rst_n,
    input A,
    output F,
    output G
    );
reg F, G;
reg [3:0] pre_state;
reg [3:0] next_state;

	
parameter Idle = 4'b1000, Start = 4'b0100, Stop = 4'b0010, Clear = 4'b0001;

//第一个过程，同步时序always块，描述状态转移方程	
always @(posedge Clock) begin

if(!rst_n)
	pre_state <= Idle;
else
	pre_state  <= next_state;

	
end
//第二个过程，组合逻辑always块，描述激励方程以及输出方程
always @(pre_state or A or rst_n) begin

case(pre_state)

Idle:begin
	if(!rst_n) begin
		next_state = Idle;
		F = 1'b0;
		G = 1'b0;
	end
	else if(A) begin
		next_state = Start;
		G = 1'b0;
	end
	else begin
		next_state = Idle;
	end		
end

Start: begin
	if(!rst_n) begin
		next_state = Idle;
		F = 1'b0;
		G = 1'b0;
	end
	else if(!A) begin
		next_state = Stop;
	end
	else begin
		next_state = Start;
	end
end

Stop: begin
	if(!rst_n) begin
		next_state = Idle;
		F = 1'b0;
		G = 1'b0;
	end
	else if(A) begin
		next_state = Clear;
		F = 1'b1;
	end
	else begin
		next_state = Stop;
	end
end
	
Clear: begin
	if(!rst_n) begin
		next_state = Idle;
		F = 1'b0;
		G = 1'b0;
	end
	else if(!A) begin
		next_state = Idle;
		F = 0;
		G = 1;
	end
	else begin
		next_state = Clear;
	end
end

default: begin
	next_state = Idle;
end

endcase


end


endmodule




三段式描述：

`timescale 1ns / 1ps
//
// Company: 
// Engineer: 
// 
// Create Date:    21:27:04 09/02/2018 
// Design Name: 
// Module Name:    fsm 
// Project Name: 
// Target Devices: 
// Tool versions: 
// Description: 
//
// Dependencies: 
//
// Revision: 
// Revision 0.01 - File Created
// Additional Comments: 
//
//
module fsm(
    input Clock,
    input rst_n,
    input A,
    output F,
    output G
    );
reg F, G;
reg [3:0] pre_state;
reg [3:0] next_state;

	
parameter Idle = 4'b1000, Start = 4'b0100, Stop = 4'b0010, Clear = 4'b0001;

//第一个过程，同步时序always块，描述状态转移方程	
always @(posedge Clock) begin

if(!rst_n)
	pre_state <= Idle;
else
	pre_state  <= next_state;

	
end
//第二个过程，组合逻辑always块，描述激励方程
always @(pre_state or A or rst_n) begin
case(pre_state)

Idle: begin
	if(!rst_n) next_state = Idle;
	else if(A) next_state = Start;
	else next_state = Idle;
end

Start: begin
	if(!rst_n) next_state = Idle;
	else if(!A) next_state = Stop;
	else next_state = Start;
end

Stop: begin
	if(!rst_n) next_state = Idle;
	else if(A) next_state = Clear;
	else next_state = Stop;
end

Clear: begin
	if(!rst_n) next_state = Idle;
	else if(!A) next_state = Idle;
	else next_state = Clear;
end

default: next_state = Idle;

endcase

end
//第三个always块，描述输出方程
always @(pre_state or A or rst_n) begin

case(pre_state)

Idle:begin
	if(!rst_n) begin
		F = 1'b0;
		G = 1'b0;
	end
	else if(A) begin
		G = 1'b0;
	end
	else begin
	;
	end		
end

Start: begin
	if(!rst_n) begin
		F = 1'b0;
		G = 1'b0;
	end
	else if(!A) begin
	;
	end
	else begin
	;
	end
end

Stop: begin
	if(!rst_n) begin
		F = 1'b0;
		G = 1'b0;
	end
	else if(A) begin
		F = 1'b1;
	end
	else begin
	;

	end
end
	
Clear: begin
	if(!rst_n) begin
		F = 1'b0;
		G = 1'b0;
	end
	else if(!A) begin
		F = 0;
		G = 1;
	end
	else begin
	;
	end
end

default: begin
	;
end

endcase

end

endmodule


功能仿真：



可见，三种描述方式的仿真图都是一样的，说明了完成同样的功能。

但是从代码的简洁度来看，就这个小状态转移图来说，无疑，一段式的描述方式是最为简单的。但是随着项目的复杂度增高，这种描述方式不便于维护和阅读。

所以呢？要综合来看，不能说哪一种一定好，哪一种一定坏，要根据实际情况而定。

最后我要提出的问题，就是Clear这个状态向Idle这个状态转移的条件：从状态图上看，注意图中的状态图的复位我用rst_n代替，这样更人性化！继续：从状态图上看，是！rst_n或！A有效时，向Idle状态转移，并且输出是F = 0 ，且 G =1；

但是从原作者的一段式代码中，我们可以看出，复位信号rst_n的优先级别要高，如果复位了，那么状态肯定转向Idle，且此时，输出F=0且G=0.这明显和状态转移图中的意思不一样啊，我们推测状态转移图写法有误，所以这里我个人默认复位信号有限，其次是输入A和当前状态决定输出。也就是说，如果复位信号无效时，当前状态为Clear且 ！A有效，那么输出就是F = 0 ，且 G =1，并且状态转向Idle.

 

 状态机描述时关键是要描述清楚几个状态机的要素，即如何进行状态转移，每个状态的输出是什么，状态转移的条件等。具体描述时方法各种各样，最常见的有三种描述方式：

     （1）一段式：整个状态机写到一个always模块里面，在该模块中既描述状态转移，又描述状态的输入和输出；

     （2）二段式：用两个always模块来描述状态机，其中一个always模块采用同步时序描述状态转移；另一个模块采用组合逻辑判断状态转移条件，描述状态转移规律以及输出；

     （3）三段式：在两个always模块描述方法基础上，使用三个always模块，一个always模块采用同步时序描述状态转移，一个always采用组合逻辑判断状态转移条件，描述状态转移规律，另一个always模块描述状态输出(可以用组合电路输出，也可以时序电路输出)。

三段式状态机示例模板：

//第一个进程，同步时序always模块，格式化描述次态寄存器迁移到现态寄存器

always @ (posedge clk or negedge rst_n)   //异步复位

if(!rst_n)

         current_state <= IDLE;

else

         current_state <= next_state; //注意，使用的是非阻塞赋值

//第二个进程，组合逻辑always模块，描述状态转移条件判断

always @ (current_state) //电平触发，现存状态为敏感信号

begin

        next_state = x; //要初始化，使得系统复位后能进入正确的状态

case(current_state)

        S1: if(...)

                next_state = S2; //阻塞赋值

        S2: if(...)

                next_state = S3; //阻塞赋值

...

endcase

end

//第三个进程，同步时序always模块，格式化描述次态寄存器输出

always @ (posedge clk or negedge rst_n)

begin

...//初始化

case(next_state)

       S1:

              out1 <= 1'b1; //注意是非阻塞逻辑

        S2:

              out2 <= 1'b1;

         default:... //default的作用是免除综合工具综合出锁存器

endcase

end