【数字IC/FPGA】手撕代码:模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

状态跳转图如下:

image-20240401075657920

有了这些信息后,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

仿真结果如下:

image-20240329163856082

可见,串行输入分别为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整除的,这就造成了二者的出入。这个情况忽略掉就行。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506527.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

webpack搭建开发环境

webpack搭建开发环境 一.webpack开发模式二.webpack打包模式三.webpack打包模式应用四.Webpack 前端注入环境变量五.Webpack 开发环境调错 source map六. Webpack 设置解析别名路径七.优化-CDN的使用八.多页面打包九.优化-分割公共代码一.webpack开发模式 作用:启动 Web 服务…

亮数据,可视化数据采集强大利器

前言 随着信息技术的飞速发展&#xff0c;我们已经进入了一个以数据为中心的世纪。在这个时代&#xff0c;数据不仅仅是信息的载体&#xff0c;它已经成为了推动社会进步、创新科技、增强决策和驱动经济增长的关键资源。 在这个数据世纪中&#xff0c;掌握数据的能力等同于掌…

[计算机效率] 文件对比工具:Beyond Compare 4

3.10 文件对比工具&#xff1a;Beyond Compare 4 Beyond Compare 4是一款功能强大的文件和文件夹比较工具&#xff0c;它能够帮助用户在不同系统或版本之间快速比较和同步文件和文件夹。以下是Beyond Compare 4软件的一些主要特点&#xff1a; 文件和文件夹比较&#xff1a;Be…

普发Pfeiffer 真空TCP120-TCP380-TCP035-TCP600 使用手侧

普发Pfeiffer 真空TCP120-TCP380-TCP035-TCP600 使用手侧

MultiPath HTTP:北大与华为合作部署FLEETY

当前的终端基本都能支持蜂窝网络和wifi网络&#xff0c;然而&#xff0c;不同的网络通路都不可避免的会出现信号不好或者其他因素引起的通路性能(吞吐量、时延等)下降。为了能够提升终端业务体验&#xff0c;很多不同的MultiPath方案被提出&#xff0c;其中&#xff0c;包括应用…

程序运行要求,三角形三边的值来自于本地一个文本文件input.txt,三角形类型的值最终存储于本地文本文件out.txt中。

本周完成如下2个实验&#xff1a; 面向对象数据持久化编程&#xff0c;使用java编写程序&#xff0c;完成三角形的类型判断&#xff0c;程序模块要求如下&#xff1a; 创建三角形对象triangle&#xff0c;该对象属性有三边a,b,c&#xff0c;该对象有&#xff1a; 方法1&#xf…

linux 软中断入门

在 linux 中&#xff0c;任务执行的载体有很多&#xff0c;包括线程&#xff0c;中断&#xff0c;软中断&#xff0c;tasklet&#xff0c;定时器等。但是从本质上来划分的话&#xff0c;任务执行的载体只有两个&#xff1a;线程和中断。软中断和 tasklet 的执行可能在中断中&am…

【无限列车1】SpringCloudAlibaba 与 SpringBoot后端架构的搭建

【无限列车1】SpringCloudAlibaba 与 SpringBoot后端架构的搭建 1、版本说明二、日志相关配置3、AOP 打印日志 1、版本说明 【SpringCloud 版本说明】https://sca.aliyun.com/zh-cn/docs/2022.0.0.0-RC1/overview/version-explain &#x1f58a; RC&#xff08;Release Candi…

离散数学--谓词逻辑之复习与前束范式与谓词演算的推理理论

引子&#xff1a;在命题演算中&#xff0c;常常要化成规范形式&#xff0c;对于谓词的演算&#xff0c;可以化成与他等价的范式&#xff01; 前束范式定义&#xff1a; 一个公式&#xff0c;如果量词均非否定地在全式的开头&#xff0c;它们的作用域延伸到整个公式的末尾&…

绘制空心环形

1.通过几个div拼接绘制空心环形进度条。 通过 -webkit-mask: radial-gradient(transparent 150px, #fff 150px);绘制空心圆 html:<body><div class"circle"><div class"circle-left"></div><div class"circle-left-mask&…

maven知识加强理解

maven知识 聚合: 父工程通过 modules标签&#xff0c;将子模块聚集起来&#xff0c;好处方便管理&#xff0c;父工程执行maven命令&#xff0c;所有的子模块都会执行 继承: 子模块通过parent标签&#xff0c;可以从父工程继承一些依赖 maven生命周期 三套 第一套:clean清理 第…

蓝桥杯(更新中)

递归与递推 递归 1.指数型枚举 解析&#xff1a;从 1 ∼ n 这 n 个整数中随机选取任意多个&#xff0c;输出所有可能的选择方案。 思路&#xff1a;枚举每一位对应的数字选与不选&#xff0c;例如&#xff1a;第一位对应的数字为1&#xff0c;有一种方案是选1&#xff0c;另…

IC-随便记

1、移远通信---通信模组 物联网解决方案供应商&#xff0c;可提供完备的IoT产品和服务&#xff0c;涵盖蜂窝模组(5G/4G/3G/2G/LPWA)、车载前装模组、智能模组&#xff08;5G/4G/边缘计算&#xff09;、短距离通信模组(Wi-Fi&BT)、GNSS定位模组、卫星通信模组、天线等硬件产…

java数据结构与算法刷题-----LeetCode279. 完全平方数

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 动态规划四平方和定理 动态规划 解题思路&#xff1a;时间复杂度…

图像处理_积分图

目录 1. 积分图算法介绍 2. 基本原理 2.1 构建积分图 2.2 使用积分图 3. 举个例子 1. 积分图算法介绍 积分图算法是图像处理中的经典算法之一&#xff0c;由Crow在1984年首次提出&#xff0c;它是为了在多尺度透视投影中提高渲染速度。 积分图算法是一种快速计算图像区域和…

LeetCode-56. 合并区间【数组 排序】

LeetCode-56. 合并区间【数组 排序】 题目描述&#xff1a;解题思路一&#xff1a;排序&#xff1f;怎么排&#xff1f;当然是排各个区间的左边界&#xff0c;然后判断下一个边界的左边界与结果数组里面的右边界是否重叠。解题思路二&#xff1a;优化解题思路三&#xff1a;0 题…

Linux: 进程优先级

Linux: 进程优先级 一、进程优先级概念二、如何查看进程优先级三、如何修改进程的优先级&#xff08;PRL vs NI&#xff09;四、为何优先级PRL必须限定范围五、进程其他特性 一、进程优先级概念 优先级的本质就是排队&#xff0c;而排队则是资源不足所引起的。在计算机中&#…

《Lost in the Middle: How Language Models Use Long Contexts》AI 解读

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…

【JavaScript 漫游】【049】ES6 规范中对象的扩展

文章简介 本篇文章为【JavaScript 漫游】专栏的第 049 篇文章&#xff0c;对 ES6 规范中对象的扩展知识点进行了记录。具体包括&#xff1a; 属性的简洁表示法属性名表达式方法的 name 属性属性的可枚举性和遍历super 关键字对象的扩展运算符链判断运算符Null 判断运算符新增…

MIT最新研究成果 机器人能够从错误中纠偏 无需编程介入和重复演示

目前科学家们正在努力让机器人变得更加智能&#xff0c;教会他们完成诸如擦拭桌面&#xff0c;端盘子等复杂技能。以往机器人要在非结构化环境执行这样的任务&#xff0c;需要依靠固定编程进行&#xff0c;缺乏场景通用性&#xff0c;而现在机器人的学习过程主要在于模仿&#…