今天我们来手撕一个常见的笔试题,使用的方法是三段式Moore状态机。
题目描述:
输入端口是串行的1bit数据,每个时钟周期进来一位新数据后,实时检查当前序列是否能整除3,若能则输出1,否则输出0。
例如,在4个时钟周期依次输入的数据为1、1、0、1。则有:
T1:数据序列为1(10进制的1),不能为3整除,所以输出flag = 0;
T2:数据序列为11(10进制的3),能为3整除,所以输出flag = 1;
T3:数据序列为110(10进制的6),能为3整除,所以输出flag = 1;
T4:数据序列为1101(10进制的13),不能为3整除,所以输出flag = 0;
接着简单分析一下题目。一个整数被3除后的余数情况只有3种:
- 余数为0
- 余数为1
- 余数为2
假设当前序列表示的数是num,它除3的商为a,余数为b, 则这个数num可以这么表示:
num = 3a + b
因为每个时钟周期新进来的数都是放入数据序列的最低位,其他位则是往左移1位,而左移一位等价于乘以2,再加上新进来的数c(c要么是0、要么是1)后,那么每个新的周期都有新序列:
新的序列 num_n = num * 2 + c
例如,前3个周期分别输入数据1、1、0,则有 110 即 6 = 3 * 2 + 0 (商a=2、余b=0);在T4时刻输入1,则1101即13 = 6 * 2 + 1(旧的num = 6,新的输入c = 1 )。
知道这些后可以对3种余数情况来分别进行讨论:
(1)余数为0的情况,也就是数据可以表示为 num = 3a + b = 3a + 0
- 新的输入为0,则新的序列为num_n = 2*num + 0 = 6*a,说明此时可以被3整除
- 新的输入为1,则新的序列为num_n = 2*num + 1 = 6*a + 1,说明此时不可以被3整除,余数为1
(2)余数为1的情况,也就是数据可以表示为 num = 3a + b = 3a + 1
- 新的输入为0,则新的序列为num_n = 2*num + 0 = 6*a + 2,说明此时不可以被3整除,余数为2
- 新的输入为1,则新的序列为num_n = 2*num + 1 = 6*a + 3,说明此时可以被3整除
(3)余数为2的情况,也就是数据可以表示为 num = 3a + b = 3a + 2
- 新的输入为0,则新的序列为num_n = 2*num + 0 = 6*a + 4,说明此时不可以被3整除,余数为1
- 新的输入为1,则新的序列为num_n = 2*num + 1 = 6*a + 5,说明此时不可以被3整除,余数为2
把这些情况划分为不同的状态,状态之间的跳转参考上面的分析。一共划分4个状态,分别是:
- IDLE:初始状态,状态跳转条件同S3,但是该状态不会输出有效信号
- S1:余数为1的状态,该状态不会输出有效信号
- S2:余数为2的状态,该状态不会输出有效信号
- S3:余数为0的状态,此时拉高有效信号flag
状态跳转图如下:
有了这些信息后,Moore型的三段式状态机也很容易写了:
//串行输入数据,实时输出当前数据能否被3整除。
//新的输入为低位,之前输入为高位。例如依次输入1、0,则视为10,而非01
module test(
input clk,
input rst,
input in, //串行输入
output reg flag //输入能被3整除时输出1,其他0
);
//定义状态寄存器
reg [1:0] state_cur;
reg [1:0] state_next;
//参数化状态变量
localparam IDLE = 2'b00;
localparam S1 = 2'b01;
localparam S2 = 2'b10;
localparam S3 = 2'b11;
//三段式状态机的状态变化
always@(posedge clk) begin
if(rst)
state_cur <= IDLE;
else
state_cur <= state_next;
end
//三段式状态机的状态转移条件
always@(*)begin
if(rst)
state_next = IDLE;
else begin
case(state_cur)
IDLE: state_next = in ? S1 : S3;
S1 : state_next = in ? S3 : S2;
S2 : state_next = in ? S2 : S1;
S3 : state_next = in ? S1 : S3;
default:state_next = IDLE;
endcase
end
end
//三段式状态机的输出
always@(posedge clk) begin
if(rst)
flag <= 0;
else begin
case(state_next)
S3: flag <= 1'b1;
default: flag <= 1'b0;
endcase
end
end
endmodule
再写个TB来测试一下模块的正确性,测试逻辑是这样的:
复位完成后,在每个时钟周期随机生成1bit输入,在TB内根据每个周期的输入实时生成数据num来统计所有的串行输入的值,比如前4个周期依次生成输入1、1、0、1,则num的值分别为1、11、110、1101,即10进制的1、3、6、12。
每个周期都用%运算符(TB文件不用考虑能否综合的问题)来对num取模,并将取模结果与被测模块的结果做比较,若二者有误,则拉高错误标志error;否则不拉高error。
`timescale 1ns/1ns
module tb_test();
reg clk;
reg rst;
reg in;
wire flag;
reg [127:0] num; //记录输入数据的数值大小
reg error; //错误标志
wire [1:0] rem; //除3的余数
assign rem = (num % 3);
//生成时钟信号,周期10ns
initial begin
clk = 1'b1;
forever #5 clk = ~clk;
end
//生成高电平有效的同步复位信号,持续3个周期
initial begin
rst = 1;
#30
rst <= 0;
end
always@(posedge clk) begin
if(rst)begin
in <= 0;
num <= 0;
error <= 0;
end
else begin
in <= #1 $random & $random; //输入是随机的0或1
num <= (num << 1) + in; //依次左移并加上最新的输入来统计数据大小
if((rem == 2'd0) != flag)begin //如果二者有误
$display("ERROR %d",num);
error = 1;
end
else
error = 0;
end
end
initial begin
#300 $stop(); //一段时间后结束仿真
end
//例化被测试模块
test inst_test(
.clk (clk ),
.rst (rst ),
.in (in ),
.flag (flag )
);
endmodule
仿真结果如下:
可见,串行输入分别为00110100010,分别对应10进制数据0、0、1、3、6、13、26、52、104、208、417、834,在输入序列分别为10进制的0、0、3、6、417、834时输出flag为高,说明这些数据能被3整除。
需要额外说明的有两点:
- 输出采用了时序逻辑,所以会慢一拍。例如在输入为0011的下一拍,flag才拉高。
- 尽管error在最一开始被拉高了一次,但并不说明模块功能发生了错误。error拉高的原因是因为在初始状态时,flag没有设计被拉高,但此时的数据值在TB中被视为0,也就是意味着在TB中是可以被3整除的,这就造成了二者的出入。这个情况忽略掉就行。