今天我們來(lái)手撕一個(gè)常見(jiàn)的筆試題，使用的方法是三段式Moore狀態(tài)機(jī)。

題目描述：

輸入端口是串行的1bit數(shù)據(jù)，每個(gè)時(shí)鐘周期進(jìn)來(lái)一位新數(shù)據(jù)后，實(shí)時(shí)檢查當(dāng)前序列是否能整除3，若能則輸出1，否則輸出0。

例如，在4個(gè)時(shí)鐘周期依次輸入的數(shù)據(jù)為1、1、0、1。則有：

?T1：數(shù)據(jù)序列為1（10進(jìn)制的1），不能為3整除，所以輸出flag = 0;

?T2：數(shù)據(jù)序列為11（10進(jìn)制的3），能為3整除，所以輸出flag = 1;

?T3：數(shù)據(jù)序列為110（10進(jìn)制的6），能為3整除，所以輸出flag = 1;

?T4：數(shù)據(jù)序列為1101（10進(jìn)制的13），不能為3整除，所以輸出flag = 0;

接著簡(jiǎn)單分析一下題目。一個(gè)整數(shù)被3除后的余數(shù)情況只有3種：

• 余數(shù)為0
• 余數(shù)為1
• 余數(shù)為2

假設(shè)當(dāng)前序列表示的數(shù)是num，它除3的商為a，余數(shù)為b， 則這個(gè)數(shù)num可以這么表示：

num = 3a + b

因?yàn)槊總€(gè)時(shí)鐘周期新進(jìn)來(lái)的數(shù)都是放入數(shù)據(jù)序列的最低位，其他位則是往左移1位，而左移一位等價(jià)于乘以2，再加上新進(jìn)來(lái)的數(shù)c（c要么是0、要么是1）后，那么每個(gè)新的周期都有新序列：

新的序列 num_n = num * 2 + c

例如，前3個(gè)周期分別輸入數(shù)據(jù)1、1、0，則有 110 即 6 = 3 * 2 + 0 （商a=2、余b=0）；在T4時(shí)刻輸入1，則1101即13 = 6 * 2 + 1（舊的num = 6，新的輸入c = 1 ）。

知道這些后可以對(duì)3種余數(shù)情況來(lái)分別進(jìn)行討論：

（1）余數(shù)為0的情況，也就是數(shù)據(jù)可以表示為 num = 3a + b = 3a + 0

• 新的輸入為0，則新的序列為num_n = 2*num + 0 = 6*a，說(shuō)明此時(shí)可以被3整除
• 新的輸入為1，則新的序列為num_n = 2*num + 1 = 6*a + 1，說(shuō)明此時(shí)不可以被3整除，余數(shù)為1

（2）余數(shù)為1的情況，也就是數(shù)據(jù)可以表示為 num = 3a + b = 3a + 1

• 新的輸入為0，則新的序列為num_n = 2*num + 0 = 6*a + 2，說(shuō)明此時(shí)不可以被3整除，余數(shù)為2
• 新的輸入為1，則新的序列為num_n = 2*num + 1 = 6*a + 3，說(shuō)明此時(shí)可以被3整除

（3）余數(shù)為2的情況，也就是數(shù)據(jù)可以表示為 num = 3a + b = 3a + 2

• 新的輸入為0，則新的序列為num_n = 2*num + 0 = 6*a + 4，說(shuō)明此時(shí)不可以被3整除，余數(shù)為1
• 新的輸入為1，則新的序列為num_n = 2*num + 1 = 6*a + 5，說(shuō)明此時(shí)不可以被3整除，余數(shù)為2

把這些情況劃分為不同的狀態(tài)，狀態(tài)之間的跳轉(zhuǎn)參考上面的分析。一共劃分4個(gè)狀態(tài)，分別是：

• IDLE：初始狀態(tài)，狀態(tài)跳轉(zhuǎn)條件同S3，但是該狀態(tài)不會(huì)輸出有效信號(hào)
• S1：余數(shù)為1的狀態(tài)，該狀態(tài)不會(huì)輸出有效信號(hào)
• S2：余數(shù)為2的狀態(tài)，該狀態(tài)不會(huì)輸出有效信號(hào)
• S3：余數(shù)為0的狀態(tài)，此時(shí)拉高有效信號(hào)flag

狀態(tài)跳轉(zhuǎn)圖如下：

有了這些信息后，Moore型的三段式狀態(tài)機(jī)也很容易寫(xiě)了：

//串行輸入數(shù)據(jù)，實(shí)時(shí)輸出當(dāng)前數(shù)據(jù)能否被3整除。
//新的輸入為低位，之前輸入為高位。例如依次輸入1、0，則視為10，而非01
module test(input       clk,input       rst,		input       in,		//串行輸入output  reg	flag	//輸入能被3整除時(shí)輸出1，其他0
);//定義狀態(tài)寄存器
reg [1:0] state_cur;	
reg [1:0] state_next;//參數(shù)化狀態(tài)變量
localparam	IDLE = 2'b00;
localparam	S1	 = 2'b01;
localparam	S2	 = 2'b10;
localparam	S3	 = 2'b11;//三段式狀態(tài)機(jī)的狀態(tài)變化 
always@(posedge clk) beginif(rst) state_cur <= IDLE;else state_cur <= state_next;
end//三段式狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)移條件
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//三段式狀態(tài)機(jī)的輸出
always@(posedge clk) beginif(rst) flag <= 0;else begincase(state_next)S3: 	 flag <= 1'b1;default: flag <= 1'b0;endcaseend 
endendmodule 

再寫(xiě)個(gè)TB來(lái)測(cè)試一下模塊的正確性，測(cè)試邏輯是這樣的：

復(fù)位完成后，在每個(gè)時(shí)鐘周期隨機(jī)生成1bit輸入，在TB內(nèi)根據(jù)每個(gè)周期的輸入實(shí)時(shí)生成數(shù)據(jù)num來(lái)統(tǒng)計(jì)所有的串行輸入的值，比如前4個(gè)周期依次生成輸入1、1、0、1，則num的值分別為1、11、110、1101，即10進(jìn)制的1、3、6、12。

每個(gè)周期都用%運(yùn)算符（TB文件不用考慮能否綜合的問(wèn)題）來(lái)對(duì)num取模，并將取模結(jié)果與被測(cè)模塊的結(jié)果做比較，若二者有誤，則拉高錯(cuò)誤標(biāo)志error；否則不拉高error。

`timescale 1ns/1nsmodule tb_test();reg		clk;
reg		rst;
reg		in;
wire	flag;reg [127:0] num;		//記錄輸入數(shù)據(jù)的數(shù)值大小
reg			error;		//錯(cuò)誤標(biāo)志
wire [1:0]	rem;			//除3的余數(shù)assign rem = (num % 3);//生成時(shí)鐘信號(hào)，周期10ns
initial beginclk = 1'b1;forever #5	clk = ~clk;
end//生成高電平有效的同步復(fù)位信號(hào)，持續(xù)3個(gè)周期
initial beginrst = 1;#30rst <= 0;
endalways@(posedge clk) beginif(rst)begin in <= 0;num <= 0;error <= 0;endelse beginin <= #1 $random & $random;		//輸入是隨機(jī)的0或1num <= (num << 1) + in;			//依次左移并加上最新的輸入來(lái)統(tǒng)計(jì)數(shù)據(jù)大小if((rem == 2'd0) != flag)begin	//如果二者有誤$display("ERROR %d",num);error = 1;end	else 	error = 0; end
endinitial begin#300 $stop();	//一段時(shí)間后結(jié)束仿真
end//例化被測(cè)試模塊
test	inst_test(.clk	(clk	),.rst	(rst	),	.in		(in		),.flag	(flag	)
);endmodule

仿真結(jié)果如下：

可見(jiàn)，串行輸入分別為00110100010，分別對(duì)應(yīng)10進(jìn)制數(shù)據(jù)0、0、1、3、6、13、26、52、104、208、417、834，在輸入序列分別為10進(jìn)制的0、0、3、6、417、834時(shí)輸出flag為高，說(shuō)明這些數(shù)據(jù)能被3整除。

需要額外說(shuō)明的有兩點(diǎn)：

• 輸出采用了時(shí)序邏輯，所以會(huì)慢一拍。例如在輸入為0011的下一拍，flag才拉高。
• 盡管error在最一開(kāi)始被拉高了一次，但并不說(shuō)明模塊功能發(fā)生了錯(cuò)誤。error拉高的原因是因?yàn)樵诔跏紶顟B(tài)時(shí)，flag沒(méi)有設(shè)計(jì)被拉高，但此時(shí)的數(shù)據(jù)值在TB中被視為0，也就是意味著在TB中是可以被3整除的，這就造成了二者的出入。這個(gè)情況忽略掉就行。