【数字IC/FPGA】手撕代码：模3检测器(判断输入序列能否被3整除)

今天我们来手撕一个常见的笔试题：模3检测，使用的方法是三段式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整除的，这就造成了二者的出入。这个情况忽略掉就行。

• 📣您有任何问题，都可以在评论区和我交流📃！
• 📣本文由 孤独的单刀 原创，首发于CSDN平台🐵，博客主页：wuzhikai.blog.csdn.net
• 📣您的支持是我持续创作的最大动力！如果本文对您有帮助，还请多多点赞👍、评论💬和收藏⭐！