同步有限状态机设计课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,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,同步有限状态机引例,第二步：状态化简，合并等价状态,a,b,c,0/0,1/0,0/0,1/0,1/0,0/1,图,5-4,化简后的状态图,5.1,同步有限状态机引例,第三步：状态编码,图,5-5,编码后的状态图,5.1,同步有限状态机引例,第四步：选择触发器的个数和类型,触发器个数可根据状态数确定，要求满足,2n-1M2n,，式中,M,为状态数，,n,为触发器的个数。对于本例，已知,M,为,3,，所以可求出触发器的个数为,2,个。,触发器可以选择,D,触发器、,JK,触发器等等，本例选用,D,触发器。,5.1,同步有限状态机引例,第五步：求出电路的激励方程和输出方程,5.1,同步有限状态机引例,第六步：画出逻辑图并检查自启动能力,5.1,同步有限状态机引例,【例,5-2,】 对应于步骤六的层次建模方法,module fsm_1(clk,A,Y);,input clk,A,;,output Y;,wire q0,q1;,assign Y= q1 ,mydff_2 dff0(.D(A),.Q(q0),.clk(clk),dff1(.D(A&q0), .Q(q1), .clk(clk,);,endmodule,/,以下实现被调用模块,mydff_2,module mydff_2(D,Q,clk);,input D,clk,;,output reg,Q;,always (posedge clk,),Q=D;,endmodule,5.1,同步有限状态机引例,【例,5-3,】 对例,5-2,的改进,消除毛刺,module fsm_1(clk,A,Y);,input clk,A,;,output reg,Y;,wire q0,q1;,mydff_2 dff0(.D(A),.Q(q0),.clk(clk),dff1(.D(A&q0), .Q(q1), .clk(clk,);,always (posedge clk,),Y= q1 ,endmodule,5.1,同步有限状态机引例,【例,5-4,】 对应于步骤五的,Verilog,建模,module fsm_2(clk,A,Y);,input clk,A,;,output reg,Y;,reg,q0,q1;,always (posedge clk,),begin,q0 = A;,q1 JK,触发器的激励,J,和,K,module D_JK(d,q,j,k,);,input d,q,;,output reg j,k,;,always (d,q,),case(d,q,),2b00,2b11:,begin j=0; k=0; end,2b01,2b10:,begin j=1; k=1; end,endcase,endmodule,5.1,同步有限状态机引例,/,顶层模块，实现例,5-2,的功能,module fsm_3(clk,A,Y);,input clk,A,;,output reg,Y;,wire q0,q1,j0,k0,j1,k1,temp;,assign temp=q0,D_JK d_jk0(A,q0,j0,k0);,D_JK d_jk1(temp,q1,j1,k1);,JK jk0(clk,j0,k0,q0);,JK jk1(clk,j1,k1,q1);,always (posedge clk,),Y= q1 ,endmodule,/JK,触发器实现,-JK,全,1,翻转,全,0,不变,其它为,J,module JK(clk,j,k,q,);,input clk,j,k,;,output reg,q;,always (posedge clk,),case(j,k,),2b11: q=q;,2b10: q=1;,2b01: q=0;,2b00: q=q;,default: ;,endcase,endmodule,5.1,同步有限状态机引例,【例,5-6,】 对应于步骤一、步骤二和步骤三的同步状态机,module fsm_3(clk,A,Y);,input clk,A,;,output reg,Y;,reg1:0 state;,parameter s0=2b00,/,状态编码为顺序编码方式,s1=2b01,s2=2b11;,always (posedge clk,),case(state,),s0: begin,if(A,) state=s1;,else state=s0;,Y=0;,end,s1: begin,if(A,) state=s2;,else state=s0;,Y=0;,end,s2: begin,if(A,) begin,state=s2;,Y=0;,end,else begin,state=s0;,Y=1;,end,end,default: state=s0;,endcase,endmodule,5.2,状态机的基本概念,1,状态机的基本描述方式,2,状态机的基本要素及分类,3,同步状态机和异步状态机,4,单进程、双进程和多进程状态机,状态机的基本描述方式,状态机的基本描述方式有,3,种：,状态转移图,状态转移列表,HDL,语言描述,状态机的基本要素及分类,状态机的基本要素有,3,个：,状态,输出,输入,同步状态机和异步状态机,异步状态机是没有确定时钟的状态机，它的状态转移不是由唯一的时钟跳变沿所触发。目前多数综合器不能综合采用,Verilog,HDL,描述的异步状态机。因此，应尽量不要使用综合工具来设计异步状态机。 如果一定要设计异步状态机，我们建议采用原理图输入或实例引用的方法，而不要用,Verilog,HDL,输入的方法。,为了能综合出有效的电路，用,Verilog,HDL,描述的状态机应明确地由唯一时钟触发，这种状态机我们称为同步状态机。同步有限状态机是设计复杂时序逻辑电路最有效最常用的方法之一。,单进程、双进程和多进程状态机,一个有限状态机总是可以被分成次态译码、状态寄存器、输出译码三个模块，可以有五种不同的方式将这些模块分配到进程语句，以实现对状态机的描述。,三个模块用一个进程实现，也就是说,3,个模块均在,1,个,always,块内，这种状态机描述称为单进程有限状态机。,每一个模块分别用一个进程实现，也就是说,3,个模块对应着,3,个,always,块，这种状态机描述称为三进程有限状态机。,其他,3,种为双进程状态机,:,次态译码、输出译码分配在一个进程中，状态寄存器用另一个进程描述；,次态译码、状态寄存器分配在一个进程中，输出译码用另一个进程描述；,次态译码用一个进程描述，状态寄存器、输出译码分配在另一个进程中。,5.3,状态机的编码方法,状态,顺序编码,独热编码,直接输出型编码,1,直接输出型编码,2,S0,00,001,000,0001,S1,01,010,001,0010,S2,10,100,010,0100,S3,-,-,100,1100,独热编码,【例,5-9,】状态机设计,独热码表示状态,module fsm_2(clk,A,Y);,input clk,A,;,output reg,Y;,reg2:0 state;,parameter s0=3b001,s1=3b010,s2=3b100;,always (posedge clk,),case(state,),s0: begin,if(A,) state=s1;,else state=s0;,Y=0;,end,s1: begin,if(A,) state=s2;,else state=s0;,Y=0;,end,s2: begin,if(A,) begin,state=s2;,Y=0;,end,else begin,state=s0;,Y=1;,end,end,default: state=s0;,endcase,endmodule,直接输出型编码,【例,5-10,】状态机设计,状态编码包含输出信息,module fsm_1(clk,A,Y);,input clk,A,;,output Y;,reg3:0 state;,parameter s0=4b0001,s1=4b0010,s2=4b0100,s3=4b1100;,assign Y=state3;,always (posedge clk,),case(state,),s0: if(A,) state=s1;,else state=s0;,s1: if(A,) state=s2;,else state=s0;,s2: if(A,) state=s2;,else state=s3;,s3: if(A,) state=s1;,else state=s0;,default: state=s0;,endcase,endmodule,非法状态的处理,处理的方法有两种：,（,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;,else state=s0;,default: state=s0;,endcase,由于剩余状态的次态不一定都指向状态,s0,，所以可以使用方法一来分别处理每一个剩余状态的转向。,5.4,复杂状态机的编写方法,【例,5-11,】状态机设计,状态和输出使用单独进程,module fsm_0(clk,A,Y);,input clk,A,;,output reg,Y;,reg2:0 current_state,next_state,;,parameter s0=3b001,s1=3b010,s2=3b100;,always (posedge clk,) /,状态寄存器,current_state=next_state,;,always (current_state,A,),/,产生下一个状态状态的组合逻辑,case(current_state,),s0: if(A) next_state,=s1;,else next_state,=s0;,s1: if(A) next_state,=s2;,else next_state,=s0;,s2: if(A) next_state,=s2;,else next_state,=s0;,default: next_state,=s0;,endcase,always (posedge clk,) /,产生输出的时序逻辑,case(current_state,),s0: Y=0;,s1: Y=0;,s2: if(A,) Y=0;,else Y=1;,default: Y= 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,代码,module gcd(clk,x_i,y_i,go_i,d_o,);,parameter N=6; /,用于定义输入数的范围,最大为,2*N-1,inputN-1:0 x_i,y_i,;,input clk,go_i,;,output regN-1:0 d_o;,parameter s0=3b111,s1=3b001,s2=3b010,s3=3b011,s4=3b100,s5=3b101,s6=3b110;,reg2:0 current_state,next_state,;,regN-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;,else next_state,=y_i) next_state,=s2;,else next_state,=s3;,s2: begin next_state,=s4;end,s3: begin next_state,0) next_state,=s5;,else next_state,=s6;,s5: begin next_state,=s4;end,s6: begin next_state,=s0;end,default: next_state,=s0;,endcase,always (negedge clk,) /,产生输出和中间变量的组合逻辑,case(current_state,),s2: begin x=x_i;y=y_i;end,s3: begin x=y_i;y=x_i;end,s5: begin r=x%y;x=y;y,=r; end,s6: begin d_o,=x; end,default: ;,endcase,endmodule,5.6,小结,在本章，我们讨论了以下知识点：,有限状态机设计的一般步骤：,第一步：理解题意，由给定的逻辑功能建立原始状态图；,第二步：状态化简；,第三步：状态编码；,第四步：选择触发器的个数和类型；,第五步：求出电路的激励方程和输出方程；,第六步：画出逻辑图并检查自启动能力。,用,Verilog,HDL,来描述有限状态机，可以充分发挥硬件描述语言的抽象建模能力，使用,always,块语句和,case,选择语句（或,if,条件语句）及赋值语句即可方便实现。具体的逻辑化简、逻辑电路到触发器映射均可由计算机自动完成，也就是说，上述第四步、第五步和第六步不再需要过多的人为干预，使电路设计工作得到简化，效率也有很大提高。,5.6,小结,等价状态是指两个或多个状态，它们在相同的输入下转换到同一个状态去，并得到一样的输出。显然等价状态是重复的，可以合并为一个。电路的状态数越少，存储电路也就越简单。状态化简的目的就在于将等价状态尽可能地合并，以得到最简的状态转换图。这一步，不管是手工完成设计，还是利用计算机自动设计，都是很重要的。但对于,FPGA,等可编程逻辑设计，由于可用逻辑资源比较丰富，而且状态编码要考虑设计的稳定性，安全性等因素，所以通常不进行状态化简。,编码方法有很多，编码方案选择得当，设计的电路可以简单，反之，选得不好，则设计的电路就会复杂许多。在实际设计时，须综合考虑电路复杂度与电路性能之间的折衷。在触发器资源丰富的,FPGA,设计中，采用独热编码既可以使电路性能得到保证又可充分利用其触发器数量多的优势，也可以采取输出编码的状态指定来简化电路结构，以提高状态机的运行速度。,触发器个数可根据状态数确定，要求满足,2n-1M2n,，式中,M,为状态数，,n,为触发器的个数。触发器可选为,D,触发器，事实上,D,触发器、,JK,触发器、,T,触发器等等，其等价电路图很容易实现。,对于任何程序算法，均可采用状态机理论将其转换为纯硬件实现，本章介绍了将程序转化为硬件实现的一种实用的方法。,P128,T1,、,2,、,3,、,4,、,5,、,6,、,7,、,8,作业,