同步有限状态机设计课件

第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小结在本章，我们讨论了以下知识点：有限状态机设计的一般步骤：第一步：理解题意，由给定的逻辑功能建立原始状态图；第二步：状态化简；第三步：