状态机与数据路径的详细阐述.ppt

2019/5/30,1,6.4 状态机与数据路径,2019/5/30,2,研究内容,基本概念 状态机分类 状态机描述方法 状态机的编码风格 可综合的FSM编码 状态机的优化 状态机容错和设计准则,2019/5/30,3,有限状态机,2019/5/30,4,Finite State Machine，FSM,状态机 一个离散数学模型。给定 一个输入集合，根据对输入的接受次序来决定一个输出集合。（摩尔状态机） 有限状态机 输入集合和输出集合都是有限的，并只有有限数目的状态，实现有限个离散状态及其状态之间转移等行为动作的一种数学模型,2019/5/30,5,有限状态机,有限状态机是由寄存器组和组合逻辑构成的 硬件时序电路； 状态机的状态（即由寄存器组的1和0的组合状态 所构成的有限个状态）只能在同一时钟跳变沿的 情况下才能从一个状态转向另一个状态； 状态机状态转换不但取决于各个输入值，还取决 于当前状态。 状态机可用于产生在时钟跳变沿时刻开关的复杂 的控制逻辑，是数字逻辑的控制核心。,2019/5/30,6,为什么要使用状态机, 有限状态机克服了纯硬件数字系统顺序方式控制不灵活的缺点。, 状态机的结构模式相对简单。, 状态机容易构成性能良好的同步时序逻辑模块。, 状态机的Verilog表述丰富多样。, 在高速运算和控制方面，状态机更有其巨大的优势。,2019/5/30,7,nn,a1 , a2 , , an,x1 , x2 , , xn,状态位置,状态名称,转移方向,输入集合 （触发事件）,输出集合 （执行动作）,状态等待,状态迁移图,S,状态编码,2019/5/30,8,状态机分类,米勒（Mealy）状态机 与当前状态和输入有关 摩尔（Moore）状态机 仅与当前状态有关,2019/5/30,9,状态机状态,次态逻辑：负责状态机译码逻辑，是组合电路。其输入包含当前状态和外部输入信号。 状态记忆：储存目前的状态，是时序寄存电路。下一个逻辑状态的输出是其输入信号。 输出逻辑：负责输出逻辑，是组合电路。摩尔机仅仅与当前状态有关，米勒机与当前状态和输入信号都有关。 输出缓存器：对输出结果再做一次寄存，避免毛刺产生，有利于时序收敛，也能保证输入延迟是一个可预测的量。,2019/5/30,10,Mealy Machine,X/Z,当前状态 S1 S2 S3,0 S1/0 S1/0 S1/1,1 S2/0 S3/0 S3/0,输入,次态/输出,2019/5/30,11,Moore Machine,采用 外部 flip-flop,2019/5/30,12,状态机设计,状态机结构图,状态转换图,2019/5/30,13,状态机真值表,2019/5/30,14,状态机仿真结果,Moore机仿真,Mealy机仿真结果,2019/5/30,15,两种综合结果比较,2019/5/30,16,状态机描述风格,一段式（1-always）,2019/5/30,17,module fsm(clk,ina,out); input clk,ina; output out; reg out; parameter s0 = 3b00,s1 =3b01,s2 =3b10,s3=3b11; reg0:1state; always (posedge clk) begin state=s0; out =0; case(state) s0:begin state=(ina)?s1:s0; out=0; end s1:begin state=(ina)?s2:s0; out=0; end s2:begin state=(ina)?s3:s0; out=0; end s3:begin state=(ina)?s3:s0; out=1; end endcase end endmodule,2019/5/30,18,状态机编写风格,One always 这种风格是将当前状态向量和输出向量用同一时序always块来描述。此法不宜产生毛刺（寄存器输出）且利于综合。 缺点，代码冗长，维护性差；case语句中对输出向量的赋值应是下一个状态输出，这点易出错；状态向量与输出向量都由寄存器实现，面积大，不能实现异步米勒状态机。,2019/5/30,19,如果采用两个always来描述,程序的模块声明、端口定义和信号类型部分不变,只是改动逻辑功能描述部分,改动部分的程序如下： always (posedge dk) state_fsm =next_state; always (state_fsm or ina) begin state=s0;out =0; case(state_fsm ) s0: begin next_state=(ina)?s1:s0;out=0; end s1: begin next state=(ina)?s2:s0;out=0： end s2: begin next_state=(ina)?s3:s0;out=0; end s3: begin next_state=(ina)?s3:s0;out=1; end endcase end,2019/5/30,20,状态机编写风格（Two always）,一个时序过程块给当前状态向量赋值，另一个组合过程块给下一个状态与输出向量赋值。此方法具有面积和时序最优的性能。 存在问题： 组合逻辑输出会产生毛刺，如果输出向量作为三态使能控制或者时钟信号使用的时候，必须消除毛刺。 输出向量必须由状态向量经译码得到，加大了状态向量到输出向量的延迟。 组合输出消耗了部分时钟，增加了其驱动的模块的输入延迟，不利于代码的综合与优化。 Output encoded 风格,2019/5/30,21,module fsm_3(clk,ina,out); input clk,ina; output out; reg out; parameter s0 = 2b00,s1 =2b01,s2 =2b10,s3=2b11; reg1:0state,next_state; always (posedge clk) begin state=s0; state= next_state; end always (state or ina) begin next_state=s0; case(state) s0: if (ina=1) next_state =s1; else next_state =s0; s1: if (ina=1) next_state =s2; else next_state =s0;,s2: if (ina=1) next_state =s3; else next_state =s0; s3: if (ina=1) next_state =s3; else next_state =s0; endcase end always (state) case(state) s0: out=0; s1: out=0; s2: out=0; s3: out=1; endcase endmodule,2019/5/30,22,状态机编写风格（three always）,两个时序过程块分别产生当前状态向量和输出向量，一个组合过程块用于产生下一状态。使用寄存器输出，但面积较小，代码可读性强；与two always相比，面积稍大但无毛刺、有利于综合。,2019/5/30,23,综合结果比较,2019/5/30,24,/第一个过程，同步时序always模块，格式化描述次态寄存器转移到现态寄存器 always (posedge clk or negedge rst_n) /异步复位 if(!rst_n) current_state = IDLE; else current_state = next_state; /注意，使用的是非阻塞赋值 /第二个过程，组合逻辑always模块，描述状态转移条件判断 always (current_state) /电平触发 begin next_state = x; /要初始化，使系统复位后能进入正确的状态 case(current_state) S1: if(.) next_state = S2; /阻塞赋值 else next_state = Sn; . endcase,2019/5/30,25,end /第三个过程，同步时序always模块，格式化描述次态寄存器输出 always (posedge clk or negedge rst_n) ./初始化 case(next_state) S1: out1 = 1b1; /注意是非阻塞逻辑 S2: out2 = 1b1; default:. /default的作用是免除综合工具综合出锁存器 endcase end,2019/5/30,26,描述方法比较,2019/5/30,27,状态机编码风格,状态机编码对状态机速度和面积关系重大 常用编码 二进制码（binary） 独热码（one-hot） 格雷码（Gray） 二进制编码也可称连续编码，也就是码元值的大小是连续变化的。比如000,001,010,011,100,101 独热码就是只有1个是1，其他都是0，如：000001,000010,000100,001000,010000,100000 格雷码就是两个码之间只差1位不同， 000，001，011，010，110，100,2019/5/30,28,二进制码与格雷码是压缩状态编码，使用最少的状态位进行编码。 二进制编码的优点是使用的状态向量最少，但从一个状态转换到相邻状态时，可能有多个比特位发生变化，瞬变次数多，易产生毛刺。,2019/5/30,29,状态编码,独热码N个状态使用N个触发器， 减少了状态寄存器之间的组合逻辑级数，因此提高了运行速度 触发器数量增加，组合逻辑电路减少； 任何状态都可以直接添加/删除等修改而不会影响状态机的其余部分。 由于译码简单，可提高速度，且易于修改。,2019/5/30,30,状态编码,独热码的缺点 变化的状态位越多，组合输出稳定前所需的时间就越长，产生的毛刺就越多 ； 多个寄存器可能受异步输入的影响，使得亚稳态发生的概率有所增加 ； 格雷码即可以消除状态转换时多状态信号传输延迟产生的毛刺，又可降低功耗。 在状态机很复杂状态跳转的分支很多时，要合理的分配状态编码保证每个状态跳转都仅有1位发生变化，这是很困难的事情,2019/5/30,31,状态编码,2019/5/30,32,可综合的FSM编码,2019/5/30,33,2019/5/30,34,状态机设计流程,定义状态变量 S 定义输出 & 下一个状态寄存器 建立状态转换图 状态最小化 选择合适的 flip-flops 选择状态分配 Assignment of binary codes to machine states 设计下一状态寄存器和输出使用组合逻辑结构,2019/5/30,35,Example,State Diagram Mealy Machine,2019/5/30,36,Final State Transition Table,2019/5/30,37,State Reduction,N Flip-Flops = log2 ( N states) States 5 & 6 相同 States 1 & 7 相同 修改后的状态转换表,2019/5/30,38,State Assignment,二进制代码赋值给各个状态,2019/5/30,39,Coded State Transition Table,2019/5/30,40,Problems,状态机的初始化如何解决？ 加入reset信号初始化所有的FF； 当状态机进入不确定状态， 无法保证它进入合法的状态。 设计次状态的解码器，保证进入合法状态。,2019/5/30,41,Corrected State Machine Design,2019/5/30,42,Corrected State Transition Table,2019/5/30,43,Improved Coded State Transition Table,2019/5/30,44,module moore_bad(Clk, Reset, In_Data, Out_Data); input Clk, Reset, In_Data; output 1:0 Out_Data; reg 1:0 Out_Data; reg 1:0 State; parameter S0=2b00, S1=2b01, S2=2b11, S3=2b10; always (posedge Clk) begin if(Reset) State=S0; else begin case(State),S0: begin Out_Data = 0; if(In_Data = 1) State = S2; else State = S0; end S1: begin Out_Data = 1; if(In_Data = 1) State = S2; else State = S0; end,S2: begin Out_Data = 1; if(In_Data = 1) State = S3; else State = S2; end S3: begin Out_Data = 0; if(In_Data = 1) State = S1; else State = S3; end endcase end end endmodule,Moore Machine-Bad Example,Both State and Out_Data are implemented with flip-flops,通过HDL语言描述上述状态机如下：,2019/5/30,45,Note: only “State” is implemented with flip-flops),module moore_good(Clk, Reset, In_Data, Out_Data); input Clk, Reset, In_Data; output 1:0 Out_Data; reg 1:0 Out_Data; reg 1:0 State, NextState; parameter S0=2b00, S1=2b01, S2=2b10, S3=2b11; always (posedge Clk or posedge Reset) begin if(Reset) State = S0; else State = NextState; end,always (In_Data or State) begin case(State) S0: begin if(In_Data = 1) NextState = S2; else NextState = S0; end S1:begin if(In_Data = 1) NextState = S2; else NextState = S0; end S2: begin if(In_Data = 1) NextState = S3; else NextState = S2; end,S3: begin if(In_Data = 1) NextState = S1; else NextState = S3; end endcase end always (State) begin case(State) S0:Out_Data = 0; S1:Out_Data = 1; S2:Out_Data = 1; S3:Out_Data = 0; endcase end endmodule,Output logic,State register (flip-flops),Next state logic,Moore Machine-Good Example,2019/5/30,46,状态机设计准则,状态机要安全,是指FSM不会进入死循环,特别是不会进入非预知的状态,而且由于某些扰动进入非设计状态,也能很快的恢复