带搜索的下拉框网站,专业做淘宝网站推广,关键词分析网站,wordpress增加自定义栏目今天我们来手撕一个常见的笔试题#xff0c;使用的方法是三段式Moore状态机。
题目描述#xff1a; 输入端口是串行的1bit数据#xff0c;每个时钟周期进来一位新数据后#xff0c;实时检查当前序列是否能整除3#xff0c;若能则输出1#xff0c;否则输出0。 例如#…今天我们来手撕一个常见的笔试题使用的方法是三段式Moore状态机。
题目描述 输入端口是串行的1bit数据每个时钟周期进来一位新数据后实时检查当前序列是否能整除3若能则输出1否则输出0。 例如在4个时钟周期依次输入的数据为1、1、0、1。则有 T1数据序列为110进制的1不能为3整除所以输出flag 0; T2数据序列为1110进制的3能为3整除所以输出flag 1; T3数据序列为11010进制的6能为3整除所以输出flag 1; T4数据序列为110110进制的13不能为3整除所以输出flag 0; 接着简单分析一下题目。一个整数被3除后的余数情况只有3种
余数为0余数为1余数为2
假设当前序列表示的数是num它除3的商为a余数为b 则这个数num可以这么表示 num 3a b 因为每个时钟周期新进来的数都是放入数据序列的最低位其他位则是往左移1位而左移一位等价于乘以2再加上新进来的数cc要么是0、要么是1后那么每个新的周期都有新序列 新的序列 num_n num * 2 c 例如前3个周期分别输入数据1、1、0则有 110 即 6 3 * 2 0 商a2、余b0在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 2b00;
localparam S1 2b01;
localparam S2 2b10;
localparam S3 2b11;//三段式状态机的状态变化
always(posedge clk) beginif(rst) state_cur IDLE;else state_cur state_next;
end//三段式状态机的状态转移条件
always(*)beginif(rst) state_next IDLE;else begincase(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;endcaseend
end//三段式状态机的输出
always(posedge clk) beginif(rst) flag 0;else begincase(state_next)S3: flag 1b1;default: flag 1b0;endcaseend
endendmodule 再写个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/1nsmodule 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 beginclk 1b1;forever #5 clk ~clk;
end//生成高电平有效的同步复位信号持续3个周期
initial beginrst 1;#30rst 0;
endalways(posedge clk) beginif(rst)begin in 0;num 0;error 0;endelse beginin #1 $random $random; //输入是随机的0或1num (num 1) in; //依次左移并加上最新的输入来统计数据大小if((rem 2d0) ! flag)begin //如果二者有误$display(ERROR %d,num);error 1;end else error 0; end
endinitial 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整除的这就造成了二者的出入。这个情况忽略掉就行。
