状态机的介绍(面试高频考点)
状态机（Finite State Machine，简称FSM）又称同步有限状态机，通常简称为状态机。"同步"指状态跳转都由时钟信号控制，"有限"则表示状态数量是有限的。根据输出决定因素，状态机分为Moore型和Mealy型两类：二者状态跳转都仅取决于输入信号，区别在于输出方式——Moore型输出仅与当前状态相关，而Mealy型输出同时取决于当前状态和输入信号。状态机是时序逻辑电路中非常重要的一个应用，常在大型复杂的系统中使用较多。
状态机的每一个状态代表一个事件，从执行当前事件到执行另一事件我们称之为状态的跳转或状态的转移，我们需要做的就是执行该事件然后跳转到一下时间，这样我们的系统就“活”了，可以正常的运转起来了。有研究显示状态机可以描述除相对论和量子力学以外的任何事情，但特别适合描述那些发生有先后顺序或时序规律的事情，在数 字电路系统中小到计数器大到微处理器都可以用状态机来进行描述。
一个完整的状态转移图需要知道以下三个要素：
1、输入：根据输入可以确定是否需要进行状态跳转以及输出，是影响状态机系统执行过程的重要驱动力；
2、输出：根据当前时刻的状态以及输入，是状态机系统最终要执行的动作；
3、状态：根据输入和上一状态决定当前时刻所处的状态，是状态机系统执行的一个稳定的过程。
状态转移图
状态转移图是状态机的一种表达方式。状态转移图中最重要的因素是状态和状态跳转的条件，有了这些，我们才能清楚状态机要表达的东西，那么根据实际需求设计抽象出符合要求的状态机就是非常有必要的。
以序列检测为例，对如何从实际问题中抽象出状态转移图以及如何规范的绘制状态转移图以及如何根据状态转移图来设计代码做详细的讲解。该模块功能为检测连续的数据流，如果数据流中有连续的10010数据，则将输出信号拉高，要求循环检测10010。
每个框表示一个状态，各个状态之间有一个指向的箭头，表示的是状态跳转的过程，箭头上有标注的数字，表达的是在当前状态的输入，结构非常的简单，各状态之间的功能、跳转的条件、输入都能够在状态转移图中非常清楚的表达出来。
状态编码
在Verilog中最常用的编码方式有二进制编码(Binary)、格雷码(Gray-code)编码、独热码(One-hot)编码等。
二进制码和格雷码是压缩状态编码。若使用格雷编码，则相邻状态转换时只有一个状态位发生翻转，这样不仅能消除状态转换时由多条状态信号线的传输延迟所造成的毛刺，又可以降低功耗。
二进制编码也可称连续编码，也就是码元值的大小是连续变化的。如S0 = 3’d0, S1 = 3’d1, S2 = 3’d2, S3 = 3’d3…
格雷码的相邻码元值间只有一位是不同的，如S0 = 3’b000, S1 = 3’b001, S2 = 3’b011, S3 = 3’b010…
独热编码即 One-Hot 编码，又称一位有效编码，其方法是使用N位状态寄存器来对N个状态进行编码，每个状态都有独立的寄存器位，并且在任意时候，其中只有一位有效。虽然使用较多的触发器，但由于状态译码简单，可减少组合逻辑且速度较快，这种编码方式还易于修改，增加状态或改变状态转换条件都可以在不影响状态机的其它部分的情况下很方便地实现。另外，它的速度独立于状态数量。与之相比，压缩状态编码在状态增加时速度会明显下降。
独热码的每个码元值只有一位是’1’，其他位都是’0’，如S0 = 3’b001, S1 = 3’b010, S2 = 3’b100…
二进制编码、格雷码编码使用较少的触发器，消耗较多的组合逻辑，而独热码编码反之。独热码编码的最大优势在于状态比较时仅仅需要比较一个位，从而一定程度上简化了组合逻辑。虽然在需要表示同样的状态数时，独热编码占用较多的位，也就是消耗较多的触发器，但在FPGA 中组合逻辑资源相对较少而寄存器资源较多，所以在FPGA中多使用独热码编码。我们还知道 CPLD 就是一个组合逻辑资源多而寄存器逻辑资源少的器件，所以CPLD设计中更常用二进制编码。
状态机设计
状态机-序列检测:从单bit信号数据流中，检测出连续的“10010”序列，检测成功拉高一个时钟周期的标志。根据设计需求，是否需要重复性检测,如：10010010,如果是不重复检测，则flag_10010就只有1个脉冲标志；如果是重复检测，则flag_10010就有2个脉冲标志。
绘制模块框图及状态图
编写模块代码
module fsm_10010(
input wire clk ,
input wire rst_n ,
input wire data_in ,
output reg flag_10010
);
//状态编码-二进制编码
parameter idel = 4'd0; //5'b0
parameter s0 = 4'd1; //5'b1
parameter s1 = 4'd2; //5'b10
parameter s2 = 4'd3; //5'b100
parameter s3 = 4'd4; //5'b1001
parameter s4 = 4'd5; //5'b10010
reg [3:0] state;
//状态机的描述
//三种写法(都要会):一段式、二段式、三段式
/* //一段式:一个always语句块,使用时序逻辑描述状态转移和输出
always@(posedge clk or negedge rst_n)
begin
if(!rst_n)
begin
state <= idel;
flag_10010 <= 1'b0;
end
else case(state)
idel : begin
flag_10010 <= 1'b0 ;
if(data_in)
state <= s0 ;
else
state <= idel ;
end
s0 :begin
flag_10010 <= 1'b0 ;
if(data_in)
state <= s0 ;
else
state <= s1 ;
end
s1 :begin
flag_10010 <= 1'b0 ;
if(data_in)
state <= s0 ;
else
state <= s2 ;
end
s2 :begin
flag_10010 <= 1'b0 ;
if(data_in)
state <= s3 ;
else
state <= idel ;
end
s3 :begin
flag_10010 <= 1'b0 ;
if(data_in)
state <= s0 ;
else
state <= s4 ;
end
s4 :begin
flag_10010 <= 1'b1 ;
if(data_in)
state <= s0 ;
else
state <= s2 ;
end
default :begin
state <= idel ;
flag_10010 <= 1'b0 ;
end
endcase
end */
//二段式
//二段式第一段:一个always语句块,时序逻辑描述状态转移
//二段式第二段:一个always语句块,组合逻辑描述输出(实际应用情况下,时序允许可选时序逻辑)
//state
always@(posedge clk or negedge rst_n)
begin
if(!rst_n)
begin
state <= idel;
end
else case(state)
idel : begin
if(data_in)
state <= s0 ;
else
state <= idel ;
end
s0 :begin
if(data_in)
state <= s0 ;
else
state <= s1 ;
end
s1 :begin
if(data_in)
state <= s0 ;
else
state <= s2 ;
end
s2 :begin
if(data_in)
state <= s3 ;
else
state <= idel ;
end
s3 :begin
if(data_in)
state <= s0 ;
else
state <= s4 ;
end
s4 :begin
if(data_in)
state <= s0 ;
else
state <= s2 ;
end
default :begin
state <= idel ;
end
endcase
end
//flag_10010
always@(*)
begin
if(!rst_n)
flag_10010 = 1'b0;
else if(state == s4)
flag_10010 = 1'b1;
else
flag_10010 = 1'b0;
end
//三段式
//三段式第一段:一个always语句块,时序逻辑描述状态更新,把次态(下一个状态)赋值给现态(当前状态)
//三段式第二段:一个always语句块,组合逻辑描述状态判断,根据现态(当前状态)以及输入判断次态(下一个状态)
//三段式第三段:一个always语句块,时序逻辑描述输出
reg [3:0] now_state ;
reg [3:0] next_state ;
//now_state
always@(posedge clk or negedge rst_n)
begin
if(!rst_n)
now_state <= idel ;
else
now_state <= next_state ;
end
//next_state
always@(*)
begin
if(!rst_n)
next_state = idel;
else case(now_state)
idel : begin
if(data_in)
next_state = s0 ;
else
next_state = idel ;
end
s0 :begin
if(data_in)
next_state = s0 ;
else
next_state = s1 ;
end
s1 :begin
if(data_in)
next_state = s0 ;
else
next_state = s2 ;
end
s2 :begin
if(data_in)
next_state = s3 ;
else
next_state = idel ;
end
s3 :begin
if(data_in)
next_state = s0 ;
else
next_state = s4 ;
end
s4 :begin
if(data_in)
next_state = s0 ;
else
next_state = s2 ;
end
default :begin
next_state = idel ;
end
endcase
end
// //fsm_10010
// always@(posedge clk or negedge rst_n)
// begin
// if(!rst_n)
// fsm_10010 <= 1'b0;
// else if(now_state == s4)//以现态为准
// fsm_10010 <= 1'b1;
// else
// fsm_10010 <= 1'b0;
// end
endmodule
编写仿真代码
`timescale 1ns/1ps
module fsm_10010_tb();
reg clk ;
reg rst_n ;
reg data_in ;
wire flag_10010 ;
initial
begin
clk = 1'b0;
rst_n = 1'b0;
data_in = 1'b0;
#123
rst_n = 1'b1;
end
always #10 clk = ~clk;//50Mhz
//数据速度保证和时钟同速
always #20 data_in = {$random} % 2;
fsm_10010 fsm_10010_inst(
.clk (clk ) ,
.rst_n (rst_n ) ,
.data_in (data_in ) ,
.flag_10010(flag_10010)
);
endmodule
仿真验证
仿真验证通过。
小练习
设计一个可乐机，完成一下功能：
1.售卖可乐，每瓶可乐售价2.5元。
2.可乐机只能接收0.5元和1元的硬币。
3.可乐机内累计投币值达到或超过2.5元，自动进行结算：如果累计投币值正好2.5元， 出一瓶可乐；如果超过2.5元，出一瓶可乐并且进行找零。(一个投币入口)
绘制模块框图及状态转移图
编写模块代码
module fsm_cola(
input wire clk ,
input wire rst_n ,
input wire in_half ,
input wire in_one ,
output reg out_cola ,
output wire out_money
);
parameter idel = 3'd0;
parameter half = 3'd1;
parameter one = 3'd2;
parameter one_half = 3'd3;
parameter two = 3'd4;
reg [2:0] state;
//state
always@(posedge clk or negedge rst_n)
begin
if(!rst_n)
state <= idel;
else case(state)
idel : if({in_one,in_half} == 2'b00)
state <= idel;
else if({in_one,in_half} == 2'b01)
state <= half;
else
state <= one;
half : if({in_one,in_half} == 2'b00)
state <= half;
else if({in_one,in_half} == 2'b01)
state <= one;
else
state <= one_half;
one : if({in_one,in_half} == 2'b00)
state <= one;
else if({in_one,in_half} == 2'b01)
state <= one_half;
else
state <= two;
one_half : if({in_one,in_half} == 2'b00)
state <= one_half;
else if({in_one,in_half} == 2'b01)
state <= two;
else
state <= idel;//出可乐,不找钱
two : if({in_one,in_half} == 2'b00)
state <= two;
else if({in_one,in_half} == 2'b01)
state <= idel;//出可乐,不找钱
else
state <= idel;//出可乐,找钱
default:state <= idel;
endcase
end
//out_cola
always@(*)
begin
if(!rst_n)
out_cola = 1'b0;
else if( (state == one_half && {in_one,in_half} == 2'b10)
||(state == two && {in_one,in_half} != 2'b00))
out_cola = 1'b1;
else
out_cola = 1'b0;
end
//out_money
assign out_money = (state == two && {in_one,in_half} == 2'b10) ? 1'b1 : 1'b0;
endmodule
编写仿真代码
`timescale 1ns/1ps
module fsm_cola_tb();
reg clk ;
reg rst_n ;
reg in_half ;
reg in_one ;
wire out_cola ;
wire out_money;
initial
begin
clk = 1'b0;
rst_n = 1'b0;
in_half = 1'b0;
in_one = 1'b0;
#123
rst_n = 1'b1;
end
always #10 clk = ~clk;
always @ (posedge clk or negedge rst_n)
begin
if(!rst_n)
{in_one,in_half} <= 2'b00; // 复位初始值
else// 生成 0~2 之间的随机数（共3种，对应 00/01/10）
case({$random} % 3)
0: {in_one,in_half} <= 2'b00;
1: {in_one,in_half} <= 2'b01;
2: {in_one,in_half} <= 2'b10;
endcase
end
fsm_cola fsm_cola_inst(
.clk (clk ),
.rst_n (rst_n ),
.in_half (in_half ),
.in_one (in_one ),
.out_cola (out_cola ),
.out_money(out_money)
);
endmodule
仿真验证
仿真验证通过，可乐机完成。
