FSM有限状态机,是FPGA和数字IC相关岗位必须要掌握的知识点,在笔试和面试中都非常常见。
(1)了解状态机:什么是摩尔型状态机,什么是米利型状态机,两者的区别是什么?一段式、二段式、三段式状态机的区别?
(2)使用状态机产生序列“11010110”,串行循环输出该序列;
(3)使用状态机检测“1101”,串行输入的测试序列为“11101101011010”,输出信号为valid有效信号,检测到时输出高,否则为低,考虑序列叠加情况,比如“1101101”,则有两个“1101”,
即:
时钟 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | … |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
输入 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | … |
输出 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | … |
11101101011010,在第5个时钟检测到序列,下一个时钟输出高电平;
11101101011010,在第8个时钟检测到序列,下一个时钟输出高电平;
11101101011010,在第13个时钟检测到序列,下一个时钟输出高电平;
给出WORD或PDF版本的报告,包括但不限于文字说明、代码、仿真测试图等。
【解答】:
(1)状态机
状态机由状态寄存器和组合逻辑电路构成,能够根据控制信号按照预先设定的状态进行状态转移,是协调相关信号动作、完成特定操作的控制中心。有限状态机简写为FSM(Finite State Machine),主要分为2大类:
第一类,输出只和状态有关而与输入无关,则称为Moore状态机;
第二类,输出不仅和状态有关而且和输入有关系,则称为Mealy状态机。
Mealy型:输出信号不仅取决于当前状态,还取决于输入;
Moore型:输出信号只取决于当前状态;
实现相同的功能时,Mealy型比Moore型能节省一个状态(大部分情况下能够节省一个触发器资源,其余情况下使用的资源相同,视状态数和状态编码方式决定),Mealy型比Moore型输出超前一个时钟周期。
(2)状态机写法
一段式:一个always块,既描述状态转移,又描述状态的输入输出,当前状态用寄存器输出。一段式写法简单,但是不利于维护,状态扩展麻烦,状态复杂时易出错,不推荐;
二段式:两个always块,时序逻辑与组合逻辑分开,一个always块采用同步时序描述状态转移;另一个always块采用组合逻辑判断状态转移条件,描述状态转移规律以及输出,当前状态用组合逻辑输出,可能出现竞争冒险,产生毛刺,而且不利于约束,不利于综合器和布局布线器实现高性能的设计;
三段式:三个always块,一个always模块采用同步时序描述状态转移;一个always采用组合逻辑判断状态转移条件,描述状态转移规律;第三个always块使用同步时序描述状态输出,寄存器输出。
三段式与二段式相比,关键在于根据状态转移规律,在上一状态根据输入条件判断出当前状态的输出,从而在不插入额外时钟节拍的前提下,实现了寄存器输出。
(3)状态机序列检测
使用三段式FSM有限状态机进行序列检测,使用摩尔型状态机,最终输出与输入无关。
使用状态机检测“1101”,串行输入的测试序列为“11101101011010”,输出信号为valid有效信号,检测到时输出高,否则为低,考虑序列叠加情况,比如“1101101”,则有两个“1101”,
即:
时钟 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | … |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
输入 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | … |
输出 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | … |
11101101011010,在第5个时钟检测到序列,下一个时钟输出高电平;
11101101011010,在第8个时钟检测到序列,下一个时钟输出高电平;
11101101011010,在第13个时钟检测到序列,下一个时钟输出高电平;
根据待检测的序列“1101”确定状态,其中S1为检测到第1个有效位“1”,S2为检测到2个有效位“11”,S3为检测到3个有效位“110”,S4位检测到4个有效位“1101”,IDLE为其他状态;
IDLE:初始状态,除S1~S4外的其他所有状态
S1:1, 来1则到S2(11),否则回到IDLE;
S2:11, 来0则到S3(110),否则保持S2(11);
S3:110, 来1则到S4(1101),否则回到IDLE;
S4:1101, 来1则到S2(11),否则回到IDLE;
摩尔型,输出和输入无关,S4时无论输入什么,都输出1
即
三段式FSM的代码:
/************************************************************
** Author :FPGA探索者公众号
** Times :2020-7-7
************************************************************/
module FSM_SequDetection_1(
clk,
rst_n,
data_in,
data_valid
);
input clk;
input rst_n;
input data_in;
output reg data_valid;
//定义状态,这里采用的独热码(One-Hot),FPGA中推荐用独热码和格雷码(Gray)
//状态较少时(4-24个状态)用独热码效果好,状态多时格雷码(状态数大于24)效果好
parameter IDLE = 5'b00001;
parameter S1 = 5'b00010;
parameter S2 = 5'b00100;
parameter S3 = 5'b01000;
parameter S4 = 5'b10000;
reg [4:0] current_state; //现态
reg [4:0] next_state; //次态
//三段式FSM,第一段,同步时序逻辑,描述状态切换,这里的写法固定
always @ ( posedge clk )
begin
if(!rst_n ) begin
current_state<= IDLE;
end
elsebegin
current_state<= next_state;
end
end
//三段式FSM,第二段,组合逻辑,判断状态转移条件,描述状态转移规律
//这里面用"="赋值和用"<="没区别
always @ (*)
begin
if(!rst_n ) begin
next_state<= IDLE;
end
elsebegin
case(current_state )
IDLE: begin
if(data_in == 1 )
next_state<= S1;
else
next_state<= IDLE;
end
S1 : begin
if(data_in == 1 )
next_state<= S2;
else
next_state<= IDLE;
end
S2 : begin
if(data_in == 0 )
next_state<= S3;
else
next_state<= S2;
end
S3 : begin
if(data_in == 1 )
next_state<= S4;
else
next_state<= IDLE;
end
S4 : begin
if(data_in == 1 )
next_state<= S2;
else
next_state<= IDLE;
end
default : begin
next_state<= IDLE;
end
endcase
end
end
//三段式FSM,第三段,同步时序逻辑,描述状态输出,摩尔型输出
always @ ( posedge clk )
begin
if(!rst_n ) begin
data_valid<= 1'b0;
end
elsebegin
case(next_state )
S4 : data_valid <= 1'b1;
default : data_valid <= 1'b0;
endcase
end
end
endmodule
综合后的RTL图:
其中,状态机部分为:
这里的状态机考虑到复位的情况,不论处在哪个状态,当复位信号有效时,均回到IDLE初始状态。
仿真测试文件(TestBench):
/************************************************************
** Author :FPGA探索者公众号
** Times :2020-7-7
************************************************************/
`timescale 1 ns/1 ns
module FSM_2_tb();
reg clk;
reg rst_n;
reg data_in;
wire data_valid;
FSM_SequDetection U1(
.clk(clk),
.rst_n(rst_n),
.data_in(data_in),
.data_valid(data_valid)
);
initial
begin
clk = 0;
rst_n = 0;
#15;
rst_n = 1;
data_in = 1;#10;
data_in = 1;#10;
data_in = 1;#10;
data_in = 0;#10;
data_in = 1;#10;
data_in = 1;#10;
data_in = 0;#10;
data_in = 1;#10;
data_in = 0;#10;
data_in = 1;#10;
data_in = 1;#10;
data_in = 0;#10;
data_in = 1;#10;
data_in = 0;#10;
#50;
$stop; //停止仿真
end
always #5 clk = ~clk;
endmodule
ModelSim仿真如下,输入“1_1101101_0_1101”,检测到3次有效的“1101”。