第5章同步有限狀態機設計5.1同步有限狀態機引例5.2狀態機的基本概念5.3狀態機的編碼方法5.4復雜狀態機的編寫方法5.5采用狀態機來實現程序算法5.6小結5.1同步有限狀態機引例【例5-1】

設計一個串行數據檢測器。電路的輸入信號A是與時鐘脈沖同步的串行數據，其時序關系如圖所示。輸出信號為Y；要求電路在信號輸入A出現110序列時，輸出信號Y為1，否則為0。5.1同步有限狀態機引例圖5-2時序邏輯電路設計過程5.1同步有限狀態機引例第一步：理解題意，由給定的邏輯功能建立原始狀態圖，如圖5-3所示圖5-3原始狀態圖圖中，S表示狀態，A/Y中橫線上面的為輸入，橫線下面的為輸出。5.1同步有限狀態機引例第二步：狀態化簡，合并等價狀態abc0/01/00/01/01/00/1圖5-4化簡后的狀態圖5.1同步有限狀態機引例第三步：狀態編碼圖5-5編碼后的狀態圖5.1同步有限狀態機引例第四步：選擇觸發器的個數和類型觸發器個數可根據狀態數確定，要求滿足2n-1<M≤2n，式中M為狀態數，n為觸發器的個數。對于本例，已知M為3，所以可求出觸發器的個數為2個。觸發器可以選擇D觸發器、JK觸發器等等，本例選用D觸發器。5.1同步有限狀態機引例第五步：求出電路的激勵方程和輸出方程5.1同步有限狀態機引例第六步：畫出邏輯圖并檢查自啟動能力5.1同步有限狀態機引例【例5-2】對應于步驟六的層次建模方法module fsm_1(clk,A,Y);inputclk,A;outputY;wireq0,q1;assignY=q1&(~A);mydff_2dff0(.D(A),.Q(q0),.clk(clk)),dff1(.D(A&q0),.Q(q1),.clk(clk));endmodule//以下實現被調用模塊mydff_2modulemydff_2(D,Q,clk);inputD,clk;outputregQ;always@(posedge

clk)Q<=D;endmodule5.1同步有限狀態機引例【例5-3】對例5-2的改進——消除毛刺module fsm_1(clk,A,Y);inputclk,A;outputregY;wireq0,q1;mydff_2dff0(.D(A),.Q(q0),.clk(clk)),dff1(.D(A&q0),.Q(q1),.clk(clk));always@(posedge

clk)Y=q1&(~A);endmodule

5.1同步有限狀態機引例【例5-4】對應于步驟五的Verilog建模module fsm_2(clk,A,Y);inputclk,A;outputregY;regq0,q1;always@(posedge

clk)begin q0<=A; q1<=q0&A;Y=q1&(~A);endendmodule5.1同步有限狀態機引例【例5-5】對應于步驟四的Verilog建模///產生JK激勵信號：D觸發器的激勵d---->JK觸發器的激勵J和KmoduleD_JK(d,q,j,k);inputd,q;outputreg

j,k;always@(d,q)

case({d,q}) 2'b00,2'b11: beginj=0;k=0;end 2'b01,2'b10: beginj=1;k=1;end

endcaseendmodule5.1同步有限狀態機引例//頂層模塊，實現例5-2的功能module fsm_3(clk,A,Y);inputclk,A;outputregY;wireq0,q1,j0,k0,j1,k1,temp;assigntemp=q0&A;D_JKd_jk0(A,q0,j0,k0);D_JKd_jk1(temp,q1,j1,k1);JKjk0(clk,j0,k0,q0);JKjk1(clk,j1,k1,q1);always@(posedge

clk)Y=q1&(~A);endmodule

//JK觸發器實現---->JK全1翻轉,全0不變,其它為JmoduleJK(clk,j,k,q);inputclk,j,k;outputregq;always@(posedge

clk)

case({j,k}) 2'b11:q=~q; 2'b10:q=1; 2'b01:q=0; 2'b00:q=q; default:;

endcaseendmodule5.1同步有限狀態機引例【例5-6】對應于步驟一、步驟二和步驟三的同步狀態機modulefsm_3(clk,A,Y);inputclk,A;outputregY;reg[1:0]state;parameters0=2'b00,//狀態編碼為順序編碼方式

s1=2'b01, s2=2'b11;always@(posedge

clk)

case(state) s0:begin

if(A)state<=s1; elsestate<=s0; Y<=0; end

s1:begin

if(A)state<=s2; elsestate<=s0;Y<=0;ends2:begin

if(A)begin state<=s2; Y<=0; end elsebegin state<=s0; Y<=1; end end default:state<=s0;

endcaseendmodule5.2狀態機的基本概念1狀態機的基本描述方式2狀態機的基本要素及分類3同步狀態機和異步狀態機4單進程、雙進程和多進程狀態機狀態機的基本描述方式狀態機的基本描述方式有3種：狀態轉移圖狀態轉移列表HDL語言描述狀態機的基本要素及分類狀態機的基本要素有3個：狀態輸出輸入同步狀態機和異步狀態機異步狀態機是沒有確定時鐘的狀態機，它的狀態轉移不是由唯一的時鐘跳變沿所觸發。目前多數綜合器不能綜合采用VerilogHDL描述的異步狀態機。因此，應盡量不要使用綜合工具來設計異步狀態機。如果一定要設計異步狀態機，我們建議采用原理圖輸入或實例引用的方法，而不要用VerilogHDL輸入的方法。為了能綜合出有效的電路，用VerilogHDL描述的狀態機應明確地由唯一時鐘觸發，這種狀態機我們稱為同步狀態機。同步有限狀態機是設計復雜時序邏輯電路最有效最常用的方法之一。

單進程、雙進程和多進程狀態機一個有限狀態機總是可以被分成次態譯碼、狀態寄存器、輸出譯碼三個模塊，可以有五種不同的方式將這些模塊分配到進程語句，以實現對狀態機的描述。

①三個模塊用一個進程實現，也就是說3個模塊均在1個always塊內，這種狀態機描述稱為單進程有限狀態機。②每一個模塊分別用一個進程實現，也就是說3個模塊對應著3個always塊，這種狀態機描述稱為三進程有限狀態機。其他3種為雙進程狀態機:③次態譯碼、輸出譯碼分配在一個進程中，狀態寄存器用另一個進程描述；④次態譯碼、狀態寄存器分配在一個進程中，輸出譯碼用另一個進程描述；⑤次態譯碼用一個進程描述，狀態寄存器、輸出譯碼分配在另一個進程中。5.3狀態機的編碼方法狀態順序編碼獨熱編碼直接輸出型編碼1直接輸出型編碼2S0000010000001S1010100010010S2101000100100S3--1001100獨熱編碼【例5-9】狀態機設計——獨熱碼表示狀態modulefsm_2(clk,A,Y);inputclk,A;outputregY;reg[2:0]state;parameters0=3'b001, s1=3'b010, s2=3'b100;always@(posedge

clk)

case(state) s0:begin

if(A)state<=s1; elsestate<=s0; Y<=0; end

s1:begin

if(A)state<=s2; elsestate<=s0; Y<=0; end s2:begin

if(A)begin state<=s2; Y<=0; end elsebegin state<=s0; Y<=1; end end default:state<=s0;

endcaseendmodule直接輸出型編碼【例5-10】狀態機設計——狀態編碼包含輸出信息modulefsm_1(clk,A,Y);inputclk,A;outputY;reg[3:0]state;parameters0=4'b0001, s1=4'b0010, s2=4'b0100, s3=4'b1100;assignY=state[3];always@(posedge

clk)

case(state) s0:if(A)state<=s1; elsestate<=s0; s1:if(A)state<=s2; elsestate<=s0; s2:if(A)state<=s2; elsestate<=s3; s3:if(A)state<=s1; elsestate<=s0; default:state<=s0;

endcaseendmodule

非法狀態的處理處理的方法有兩種：（1）在語句中對每一個非法狀態都作出明確的狀態轉換指示，如在原來的case語句中增加諸如以下語句：case(state)N1:state<=s0;N2:state<=s0;…（2）如例5-6、例5-9和例5-10中那樣，利用default語句對未提到的狀態作統一處理。case(state)s0:if(A)state<=s1;elsestate<=s0;…default:state<=s0;endcase由于剩余狀態的次態不一定都指向狀態s0，所以可以使用方法一來分別處理每一個剩余狀態的轉向。5.4復雜狀態機的編寫方法【例5-11】狀態機設計——狀態和輸出使用單獨進程modulefsm_0(clk,A,Y);inputclk,A;outputregY;reg[2:0]current_state,next_state;parameters0=3'b001, s1=3'b010, s2=3'b100;always@(posedge

clk)//狀態寄存器

current_state<=next_state;always@(current_state,A)//產生下一個狀態狀態的組合邏輯

case(current_state) s0:if(A)next_state<=s1; elsenext_state<=s0; s1:if(A)next_state<=s2; elsenext_state<=s0; s2:if(A)next_state<=s2; elsenext_state<=s0; default:next_state<=s0;

endcasealways@(posedge

clk)//產生輸出的時序邏輯

case(current_state) s0:Y<=0; s1:Y<=0; s2:if(A)Y<=0; elseY<=1; default:Y<=0;

endcaseendmodule5.5采用狀態機來實現程序算法1求兩數最大公約數的算法2求兩數最大公約數的實現求兩數最大公約數的算法【例5-12】求最大公約數的算法

0:intx,y,r;1:while(1){2:while(!go_i);3:if(x_i>=y_i){4:x=x_i;5:y=y_i;}else{6:x=y_i;7:y=x_i;}8:while(y!=0){9:r=x%y;10:x=y;11:y=r;}12:d_o=x;

}求兩數最大公約數的實現圖5-18狀態圖轉換模板求兩數最大公約數的實現圖5-19求最大公約數的狀態圖（左）及化簡后的狀態圖（右）求兩數最大公約數的實現【例5-13】求最大公約數的Verilog代碼modulegcd(clk,x_i,y_i,go_i,d_o);parameterN=6;//用于定義輸入數的范圍,最大為2**N-1input[N-1:0]x_i,y_i;inputclk,go_i;outputreg[N-1:0]d_o;parameters0=3'b111,s1=3'b001,s2=3'b010, s3=3'b011,s4=3'b100,s5=3'b101,s6=3'b110;reg[2:0]current_state,next_state;reg[N-1:0]x,y,r;always@(posedge

clk)//狀態寄存器

current_state<=next_state;求兩數最大公約數的實現always@(current_state,x_i,y_i,go_i,x,y,r)//產生下一個狀態的組合邏輯

case(current_state) s0:if(go_i)next_state<=s1; elsenext_state<=s0; s1:if(x_i>=y_i)next_state<=s2; elsenext_state<=s3; s2:beginnext_state<=s4;end s3:beginnext_state<=s4;end s4:if(y>0)next_state<=s5; elsenext_state<=s6; s5:beginnext_state<=s4;end s6:beginnext_state<=s0;end default:next_state<=s0;

endcasealways@(negedge

clk)//產生輸出和中間變量的組合邏輯

case(current_state) s2:beginx=x_i;y=y_i;end s3:beginx=y_i;y=x_i;end s5:beginr=x%y;x=y;y=r;end s6:begind_o=x;end default:;

endcaseendmodule5.6小結在本章，我們討論了以下知識點：有限狀態機設計的一般步驟：第一步：理解題意，由給定的邏輯功能建立原始狀態圖；第二步：狀態化簡；第三步：