基本知识：
1、有限状态机的分类：
- Moore型：输出仅与电路的状态有关；
- Mealy型：输出与当前电路状态和当前电路输入有关。
2、有限状态机的描述方法：
-
状态转换图：节点：状态（Moore输出）；
边：由一个状态转换为另一个状态的对应输入（Mealy） -
算法状态机：类似于流程图。
3、设计步骤：
- S1、定类型；
- S2、列状态+编码；
- S3、画状态转换图；
- S4、代码语言描述
4、状态转移图检查：
- 完备性；
- 互斥性。
设计案例：序列检测器
功能描述：设计一个“1101”的序列检测器，设\(d_{in}\)为数子码流输入，\(s_{out}\)为检出标记输出，高电平表示发现指定序列，低电平表示没有发现指令序列
A.Moore型
-
状态+编码：
S0：未检测到‘1’
S1：检测到输入序列‘1’
S2：检测到输入序列‘11’
S3：检测到输入序列‘110’
S4：检测到输入序列‘1101’
共计5个状态，需要声明位宽为3的状态寄存器*2. -
状态转移图：
- 代码语言描述：
module seqdet
#(parameter s0=3'b000,
parameter s1=3'b001,
parameter s2=3'b010,
parameter s3=3'b011,
parameter s4=3'b100)
(input clk, reset, din,
output reg sout);
reg [2:0] cur_state, next_state;
always@(posedge clk) begin
if(reset) cur_state <= s0;
else cur_state <= next_state;
end
always@(din, cur_state) begin
case(cur_state)
s0: begin
if(din==1'b1) next_state=s1;
else next_state=s0;
end
s1: begin
if(din==1'b1) next_state=s2;
else next_state=s0;
end
s2: begin
if(din==1'b1) next_state=s2;
else next_state=s3;
end
s3: begin
if(din==1'b1) next_state=s4;
else next_state=s0;
end
s4: begin
if(din==1'b1) next_state=s2;
else next_state=s0;
end
endcase
end
always@(cur_state) begin
if(reset) sout=1'b0;
else if(cur_state==s4) sout=1'b1;
else sout=1'b0;
end
endmodule
B.Mealy型
-
状态+编码：
由于Mealy型在边上即可进行输入，故无需S4状态：
S0：未检测到‘1’
S1：检测到输入序列‘1’
S2：检测到输入序列‘11’
S3：检测到输入序列‘110’
共计4个状态，需要声明位宽为2的状态寄存器*2. -
状态转移图：
- 代码语言描述：
module seqdet
#(parameter s0=2'b00,
parameter s1=2'b01,
parameter s2=2'b10,
parameter s3=2'b11)
(input clk, reset, din,
output reg sout);
reg [2:0] cur_state, next_state;
always@(posedge clk) begin
if(reset) cur_state <= s0;
else cur_state <= next_state;
end
always@(cur_state, din) begin
case(cur_state)
s0: begin
if(din==1'b1) next_state=s1;
else next_state=s0;
end
s1: begin
if(din==1'b1) next_state=s2;
else next_state=s0;
end
s2: begin
if(din==1'b1) next_state=s2;
else next_state=s3;
end
s3: begin
if(din==1'b1) next_state=s1;
else next_state=s0;
end
endcase
end
always@(posedge clk) begin
if(reset) sout=1'b0;
else if(cur_state==s3 && din) sout=1'b1;
else sout=1'b0;
end
endmodule
Lab4_有限状态机
一、FSM1--混合输出状态机：
- 功能描述：
依据状态转移图，设计有限状态机，要求采用二段式或三段式描述方法。
- 设计方案：
①定类型：Mealy型和Moore型均需实现；
②状态编码：由状态转移图可知：共有四种状态，可进行编码如下：
#(parameter s0=2'b00,
parameter s1=2'b01,
parameter s2=2'b10,
parameter s3=2'b11)
③无需再画状态转移图，已经给出；
- 关键代码：
always@(posedge clk) begin
if(!rst_n) cur_state <= s0;
else cur_state <= next_state;
end
always@(cur_state, in) begin
case(cur_state)
s0: begin
if(in==1'b1) next_state=s2;
else next_state=s0;
end
s1: begin
if(in==1'b1) next_state=s1;
else next_state=s0;
end
s2: begin
if(in==1'b1) next_state=s3;
else next_state=s0;
end
s3: begin
if(in==1'b1) next_state=s1;
else next_state=s0;
end
endcase
end
always@(cur_state) begin //Moore
if(!rst_n) o_moore=1'b0;
else if(cur_state==s1) o_moore=1'b1;
else o_moore=1'b0;
end
always@(cur_state, in) begin //Mealy
if(!rst_n) o_mealy=1'b0;
else if(cur_state!=s0 && in==1'b0) o_mealy=1'b1;
else o_mealy=1'b0;
end
- 仿真验证：
依据给出的波形图，编写testbench如下：
initial begin
clk=0;
forever #10 clk=~clk;
end
initial begin
rst_n=0; in=1;
#20 rst_n=1; in=1;
#60 in=0;
#20 in=1;
#20 in=0;
#20 in=1;
#40 in=0;
#20 in=1;
#40 in=0;
#20 in=1;
#40 in=0;
#20 in=1;
#80 in=0;
#20 in=1;
#20 in=0;
#20 in=1;
#20 in=0;
#20 in=1;
#20 in=0;
#100 $stop;
end
得到的仿真波形图如下图所示，与给出的设定波形相符，符合题意。
- 综合结果：
- 总结反思：
由于Mealy型和Moore型的触发条件不同，所以不应放在同一个always块中。
二、FSM2——序列检测器（01101）：
-
功能描述：
分别使用Moore和Mealy型有限状态机设计“01101”的序列检测器，要求使用二段式或三段式描述方法。 -
设计方案：
A.Moore型：
①定类型：Moore型；
②状态编码：共有六种状态，可进行编码如下：
#(parameter s0=3'b000,
parameter s1=3'b001,
parameter s2=3'b010,
parameter s3=3'b011,
parameter s4=3'b100,
parameter s5=3'b101)
③画出状态转移图如下；
- 关键代码：
always@(posedge clk, rstn) begin
if(!rstn) cur_state <= s0;
else cur_state <= next_state;
end
always@(cur_state, data) begin
case(cur_state)
s0: begin
if(data==1'b1) next_state=s0;
else next_state=s1;
end
s1: begin
if(data==1'b1) next_state=s2;
else next_state=s1;
end
s2: begin
if(data==1'b1) next_state=s3;
else next_state=s1;
end
s3: begin
if(data==1'b1) next_state=s0;
else next_state=s4;
end
s4: begin
if(data==1'b1) next_state=s5;
else next_state=s1;
end
s5: begin
if(data==1'b1) next_state=s3;
else next_state=s0;
end
default: next_state=s0;
endcase
end
always@(cur_state) begin
if(!rstn) out_moore=1'b0;
else if(cur_state==s5) out_moore=1'b1;
else out_moore=1'b0;
end
- 仿真验证：
编写testbench如下：
initial begin
clk=0;
forever #10 clk=~clk;
end
initial begin
rstn=0; data=1;
#20 rstn=1;
#40 data=0;
#20 data=1;
#60 data=0;
#40 data=1;
#20 data=0;
#20 data=1;
#40 data=0;
#20 data=1;
#40 data=0;
#20 data=1;
#20 data=0;
#30 $stop;
end
得到的仿真波形图如下图所示，与给出的设定波形相符，符合题意。
- 综合结果：
相应的生成的状态转移图为：
B.Mealy型：
①定类型：Mealy型；
②状态编码：共有五种状态，可进行编码如下：
#(parameter s0=3'b000,
parameter s1=3'b001,
parameter s2=3'b010,
parameter s3=3'b011,
parameter s4=3'b100)
③画出状态转移图如下；
- 关键代码：
always@(posedge clk, rstn) begin
if(!rstn) cur_state <= s0;
else cur_state <= next_state;
end
always@(cur_state, data) begin
case(cur_state)
s0: begin
if(data==1'b1) next_state=s0;
else next_state=s1;
end
s1: begin
if(data==1'b1) next_state=s2;
else next_state=s1;
end
s2: begin
if(data==1'b1) next_state=s3;
else next_state=s1;
end
s3: begin
if(data==1'b1) next_state=s0;
else next_state=s4;
end
s4: begin
if(data==1'b1) next_state=s2;
else next_state=s1;
end
endcase
end
always@(cur_state, data) begin
if(!rstn) out_mealy=1'b0;
else if(cur_state==s4 && data==1) out_mealy=1'b1;
else out_mealy=1'b0;
end
- 仿真验证：
编写testbench如下：
initial begin
clk=0;
forever #10 clk=~clk;
end
initial begin
rstn=0; data=1;
#20 rstn=1;
#40 data=0;
#20 data=1;
#60 data=0;
#40 data=1;
#20 data=0;
#20 data=1;
#40 data=0;
#20 data=1;
#40 data=0;
#20 data=1;
#20 data=0;
#30 $stop;
end
得到的仿真波形图如下图所示，与给出的设定波形相符，符合题意。
- 综合结果：
相应地生成的状态转移图如下：
三、FSM4--序列接收器：
- 功能描述：
在某些串行通信协议中，每个数据字节与一个起始位和一个停止位一起发送，以帮助接收器从比特流中划分字节。一种常见的方案是使用一个起始位（0）、8个数据位和1个停止位（1）。当无任何传输（空闲）时，线路也处于逻辑1。
设计一个有限状态机，当给定一个比特流时，它将识别字节何时已经被正确的接收到。它需要识别起始位，等待所有8个数据位，然后验证停止位是否正确。如果停止位正确，那么输出该循环内所接收到的8位数据（注意，数据到达的顺序是从低位到高位），其他时间内输出数据为零；如果停止位未按预期出现，则FSM必须等到找到停止位后再尝试接收下一个字节（该输入无效）。
- 设计方案：
①定类型：Moore型；
②状态编码：
#(parameter IDLE = 3'b000,
parameter START= 3'b001,
parameter HOLD = 3'b010,
parameter STOP = 3'b011,
parameter MISS = 3'b100)
③当处于IDLE状态时，此时若输入1，则继续循环IDLE状态；若输入0，则进入START状态，开始接收数据；
当处于START状态时，此时无论输入任何数据都会在下一步进入HOLD状态；
当处于HOLD状态时，每次在上升沿循环进入此状态时加一，当输入为1时，做出以下判断：
若cnt<7，则继续HOLD；
若cnt=7，则下一STOP，cnt置零；
若cnt>7，则下一MISS，cnt置零；
当处于STOP状态时，输出done=1，以及输出序列，此时若输入为0，则进入START，此时若输入为1，则进入IDLE；
当处于MISS状态时，若输入为0，则进入MISS，若输入为1，则进入IDLE。
据此可以做出状态转移图如下：
- 关键代码：
always@(posedge clk) begin
if(reset) cur_state <= IDLE;
else begin
if(cur_state==HOLD && cnt!=8)
cnt<=cnt+1;
else if(cur_state==STOP||cur_state==MISS)
cnt<=0;
else cnt<=cnt;
cur_state <= next_state;
num_reg[cnt+1]=in;
end
end
always@(cur_state, in, cnt) begin
case(cur_state)
IDLE: begin
if(in==1'b0) next_state=START;
else next_state=IDLE;
end
START: next_state=HOLD;
HOLD: begin
if((cnt==7) && (in==1'b1)) begin next_state=STOP; end
else if((cnt==7) && (in==1'b0)) begin next_state=MISS; end
else begin next_state=HOLD; end
end
STOP: begin
if(in==1'b1) next_state=IDLE;
else next_state=START;
end
MISS: begin
if(in==1'b1) next_state=IDLE;
else next_state=MISS;
end
default: next_state=IDLE;
endcase
end
//assign done=(cur_state==STOP);
//assign out_byte=(cur_state==STOP?num_reg:8'b0);
always@(cur_state) begin
if(reset) begin done=1'b0; out_byte=8'b0; end
else if(cur_state==STOP) begin done=1'b1; out_byte=num_reg; end
else begin done=1'b0; out_byte=8'b0; end
end
- 仿真验证：
根据给出的波形图，编写 testbench如下：
initial begin
clk=1;
forever #10 clk=~clk;
end
initial begin
reset=1; in=0;
#10 reset=0;
#80 in=1;
#20 in=0;
#20 in=1;
#40 in=0;
#20 in=1;
#20 in=0;
#40 in=1;
#20 in=0;
#60 in=1;
#20 in=0;
#20 in=1;
#20 in=0;
#60 in=1;
#20 in=0;
#40 in=1;
#20 in=0;
#60 in=1;
#20 in=0;
#20 in=1;
#40 in=0;
#20 $stop;
end
得到的仿真波形图如下，符合题意：
- 综合结果：
相应生成的状态转移图如下：
- 总结反思：
注意区分各个变量的触发条件！不要混在一起写！！
四、FSM6--表达式状态机-允许括号：
- 功能描述：
1、表达式F中只含有数字0-9，加号"+"，乘号"*"，半角括号"("和")"。
2、表达式F可以按如下的规则产生：
a. 单个数字[0-9]是F；
b. 如果X是F，Y是F，则X+Y也是F；
c. 如果X是F，Y是F，则X*Y也是F。
d. 如果X是F，且X中不含括号，那么(X)也是F。
每个时钟上升沿，状态机从in中读入一个ASCII编码的字符。假设读入的第i个字符为\({(c_i)}\)，则第n个时钟上升沿时，可以拼出一个字符串: \([s=c_1 c_2....c_n]\)我们需要你在此时判断s是否符合表达式F的定义。假如\(s\)符合F的定义，那么\(out\)应输出1，否则输出0;
另外，每个clr上升沿时，请清零状态；如果clk的上升沿时clr为1，也需要清零状态。清零后，上面定义的字符串\((s)\)也应从空串开始计算。如果\((s)\)当前是空串，out也应输出0。
- 设计方案：
①定类型：Moore型；
②状态编码：
#(parameter NULL =3'b000,
parameter NUM =3'b001,
parameter BRACKET =3'b010,
parameter OPERATOR =3'b011,
parameter LEGAL =3'b100,
parameter ILLEGAL =3'b101)
③当处于NULL状态时，此时若输入数字，则NUM状态；若输入运算符，则ILLEGAL；若输入左括号，则BRACKET；若输入右括号，则ILLEGAL;
当处于NUM状态时，若输入数字，则ILLEGAL;若输入运算符，则ILLEGAL；若输入左括号，则ILLEGAL；若输入右括号，如与前面匹配，则LEGAL，否则ILLEGAL;
当处于BRACKET状态时，若输入数字，则NUM；若输入运算符或括号，则ILLEGAL;
当处于OPERATOR状态时，若输入数字，则NUM；若输入运算符，则ILLEGAL；若输入左括号，如前面括号均已匹配，则BRACKET，否则ILLEGAL；若输入右括号，则ILLEGAL;
当处于LEGAL状态时，若输入数字，则NUM；若输入运算符，则OPERATOR；若输入左括号，则BRACKET；若输入右括号，则ILLEGAL;
当处于ILLEGAL状态时，则ILLEGAL.
- 关键代码：
always@(posedge clk) begin
if(clr) begin
cur_state<=NULL;
flag<=1'b1;
end
else begin
if(next_state==BRACKET)
flag<=1'b0;
else if(next_state==LEGAL)
flag<=1'b1;
else
flag<=flag;
cur_state<=next_state;
end
end
always@(in, cur_state) begin
case(cur_state)
NULL: begin
if(isnum(in)) next_state=NUM;
else if(isop(in)) next_state=ILLEGAL;
else if(in==8'h28) begin
if(flag==1) next_state=BRACKET;
else next_state=ILLEGAL;
end
else if(in==8'h29) next_state=ILLEGAL;
else next_state=ILLEGAL;
end
NUM: begin
if(isnum(in)) next_state=ILLEGAL;
else if(isop(in)) next_state=OPERATOR;
else if(in==8'h28) next_state=ILLEGAL;
else if(in==8'h29) begin
if(flag==0) next_state=LEGAL;
else next_state=ILLEGAL;
end
else next_state=ILLEGAL;
end
BRACKET: begin
if(isnum(in)) next_state=NUM;
else if(isop(in)) next_state=ILLEGAL;
else if(in==8'h28) next_state=ILLEGAL;
else if(in==8'h29) next_state=ILLEGAL;
else next_state=ILLEGAL;
end
OPERATOR: begin
if(isnum(in)) next_state=NUM;
else if(isop(in)) next_state=ILLEGAL;
else if(in==8'h28) begin
if(flag==1) next_state=BRACKET;
else next_state=ILLEGAL;
end
else if(in==8'h29) next_state=ILLEGAL;
else next_state=ILLEGAL;
end
LEGAL: begin
if(isnum(in)) next_state=NUM;
else if(isop(in)) next_state=OPERATOR;
else if(in==8'h28) next_state=BRACKET;
else if(in==8'h29) next_state=ILLEGAL;
else next_state=ILLEGAL;
end
ILLEGAL:/*begin
if(isnum(in)) next_state=NUM;
else if(isop(in)) next_state=ILLEGAL;
else if(in==8'h28) begin
if(flag==1) next_state=BRACKET;
else next_state=ILLEGAL;
else if(in==8'h29) next_state=ILLEGAL;
*/
next_state=ILLEGAL;
default: next_state=NULL;
endcase
end
always@(cur_state) begin
if(clr) out=1'b0;
else if((cur_state==LEGAL)||((cur_state==NUM)&&(flag==1'b1))) out=1'b1;
else out=1'b0;
end
- 仿真验证：
根据给出的波形图，编写 testbench如下：
initial begin
clk=0;
forever #10 clk=~clk;
end
initial begin
in="1";
#20 in="+";
#20 in="(";
#20 in="1";
#20 in="+";
#20 in="2";
#20 in=")";
#20 in="*";
#20 in="(";
#20 in="3";
#20 in="+";
#20 in="1";
#20 in=")";
#40 $stop;
/*in="(";
#20 in="1";
#20 in=")";
#20 in="+";
#20 in="(";
#20 in="2";
#20 in=")";
#20 in="(";
#20 in="1";
#20 in="*";
#20 in="2";
#20 in=")";
#20 in="(";
#20 in="1";
#20 in=")";
#20 in="+";
#20 in="(";
#20 in="2";
#20 in=")";
#20 in="*";
#20 in="(";
#20 in="1";
#20 in="*";
#20 in="2";
#20 in=")";
#40 in="1";
#20 in="+";
#20 in="2";
#20 in="+";
#40 in="5";
#40 in="1";
#20 in="2";
#20 in="+";
#20 in="5";
#80 $stop;*/
end
initial begin
clr=1'b0;
/*#230 clr=1'b1;
#10 clr=1'b0;
#270 clr=1'b1;
#10 clr=1'b0;
#130 clr=1'b1;
#10 clr=1'b0;
#140 $stop;*/
end
得到的仿真波形图如下，符合题意：
- 综合结果：
相应生成的状态转移图如下：
- 总结反思：
注意初始化！！
消除LATCH：
- \(if-else\)语句写完整；
- \(case\)语句写好\(default\);
- 变量赋初值；
- 区分组合逻辑与时序逻辑，不要把变量混着放。
![[Love] VSCODE 调试 LOVE 引擎游戏](https://linxiaoxu.oss-cn-hangzhou.aliyuncs.com/static/pic/2023/08/20230824010502_image-20230824010439451.png)
