同步状态机的原理、结构和设计.ppt

《同步状态机的原理、结构和设计.ppt》由会员分享，可在线阅读，更多相关《同步状态机的原理、结构和设计.ppt（58页珍藏版）》请在三一办公上搜索。

1、同步状态机的原理、结构和设计,汪彦刚,FSM,状态机分类Moore型状态机设计状态机复位Moore型状态机信号输出方法Mealy型状态机状态机容错设计,状态机一般定义,（Finite State Machine，FSM）,状态机 一个离散数学模型。给定 一个输入集合，根据对输入的接受次序 来决定一个输出集合。（摩尔状态机）,状态 系统的基本数学特征。,有限状态机 输入集合和输出集合 都是有限的，并只有有限数目的状态。,什么是状态机,有限状态机(简称状态机)相当于一个控制器，它将一项功能的完成分解为若干步，每一步对应于二进制的一个状态，通过预先设计的顺序在各状态之间进行转换，状态转换的过程就是实

2、现逻辑功能的过程。,为什么使用状态机,有限状态机克服了纯硬件数字系统顺序方式控制不灵活的缺点。设计方案相对固定，结构模式简单，可定义符号化枚举类型的状态。状态机的HDL描述层次分明，结构清晰，易读易懂。状态机容易构成性能良好的同步时序逻辑模块。在高速运算和控制方面，状态机更有其巨大的优势。基于有限状态机技术设计的控制器其工作速度大大优于CPU。就可靠性而言，状态机的优势也是十分明显的。基于有限状态机技术设计的控制器其可靠性也优于CPU。,输入集合 A,输出集合 X,状态记忆,输出形成,状态迁移,状态机一般结构,CLK,组合逻辑,时序逻辑,同步,当前状态,后续状态,S,a1,a2,an,x1,x

3、2,xn,状态位置,状态名称,转移方向,输入集合（触发事件）,输出集合（执行动作）,状态等待,状态迁移图,nn,a1,a2,an,x1,x2,xn,状态位置,状态名称,转移方向,输入集合（触发事件）,输出集合（执行动作）,状态等待,状态迁移图,S,状态编码,FSM应用,FSM通过状态图描述状态转换过程FSM：数字系统控制单元的建模数字系统：受控模块：功能模块，设计较易控制模块实现CPUFSM执行耗费时间，执行时间的确定性方面，FSM优于CPU,FSM 构成,FSM用来解决一般时序逻辑电路问题，包括同步/异步时序逻辑状态寄存器当前状态（现态）寄存器组合逻辑电路下一状态（次态）组合逻辑输出组合逻辑

4、,FSM分类,Moore型：输出信号仅与现态相关Mealy型：输出信号与现态和输入相关,DFFs,OutputComb.Logic,FeedbackComb.Logic,DFFs,OutputComb.Logic,FeedbackComb.Logic,Moore,Mealy,现态,次态,输入,输出,现态,次态,输出,输入,Moore型状态机设计方法,摩尔型状态机的典型结构,Moore型状态机设计方法,More型状态机输出仅和存储电路的状态有关，与外部输入无关，即:外部输出是内部状态的函数。,状态转移图描述方式：,Mealy型状态机设计方法,米勒型状态机的典型结构,Mealy型状态机输出不仅和存

5、储电路状态有关，还和外部输入信号有关，即:外部输出是内部状态和外部输入的函数,状态图描述方式：,Mealy型状态机设计方法,Example of a 5-state Mealy FSM,module mealy(data_in,data_out,reset,clock);output data_out;input 1:0 data_in;input reset,clock;reg data_out;reg 2:0 pres_state,next_state;parameter st0=3d0,st1=3d1,st2=3d2,st3=3d3,st4=3d4;/FSM registeralways

6、(posedge clock or negedge reset)begin:stateregif(!reset)/asynchronous resetpres_state=st0;elsepres_state=next_state;end/statereg,/FSM combinational blockalways(pres_state or data_in)begin:fsmcase(pres_state)st0:case(data_in)2b00:next_state=st0;2b01:next_state=st4;2b10:next_state=st1;2b11:next_state=

7、st2;endcasest1:case(data_in)2b00:next_state=st0;2b10:next_state=st2;default:next_state=st1;endcasest2:case(data_in)2b0 x:next_state=st1;2b1x:next_state=st3;endcasest3:case(data_in)2bx1:next_state=st4;default:next_state=st3;endcasest4:case(data_in)2b11:next_state=st4;default:next_state=st0;endcasedef

8、ault:next_state=st0;endcaseend/fsm,/Mealy output definition using pres_state w/data_inalways(data_in or pres_state)begin:outputscase(pres_state)st0:case(data_in)2b00:data_out=1b0;default:data_out=1b1;endcasest1:data_out=1b0;st2:case(data_in)2b0 x:data_out=1b0;default:data_out=1b1;endcasest3:data_out

9、=1b1;st4:case(data_in)2b1x:data_out=1b1;default:data_out=1b0;endcasedefault:data_out=1b0;endcaseend/outputsendmodule,Example of a 5-state Moore FSM,module moore(data_in,data_out,reset,clock);output data_out;input 1:0 data_in;input reset,clock;reg data_out;reg 2:0 pres_state,next_state;parameter st0=

10、3d0,st1=3d1,st2=3d2,st3=3d3,st4=3d4;/FSM registeralways(posedge clock or negedge reset)begin:stateregif(!reset)pres_state=st0;elsepres_state=next_state;end/statereg/FSM combinational blockalways(pres_state or data_in)begin:fsmcase(pres_state)st0:case(data_in)2b00:next_state=st0;2b01:next_state=st4;2

11、b10:next_state=st1;2b11:next_state=st2;endcase,st1:case(data_in)2b00:next_state=st0;2b10:next_state=st2;default:next_state=st1;endcasest2:case(data_in)2b0 x:next_state=st1;2b1x:next_state=st3;endcasest3:case(data_in)2bx1:next_state=st4;default:next_state=st3;endcasest4:case(data_in)2b11:next_state=s

12、t4;default:next_state=st0;endcasedefault:next_state=st0;endcaseend/fsm/Moore output definition using pres_state onlyalways(pres_state)begin:outputscase(pres_state)st0:data_out=1b1;st1:data_out=1b0;st2:data_out=1b1;st3:data_out=1b0;st4:data_out=1b1;default:data_out=1b0;endcaseend/outputsendmodule/Moo

13、re,verilog语言描述FSM的建立过程,跟据具体要求分析控制过程，建立状态转移图后：1。定义枚举类型的信号描述状态2。建立第1个always，描述次态组合逻辑，现态和输入信号作为敏感量，3。在进程中定义状态转移CASE 语句的一条表示一个状态，状态转移通过IF ELSE语句实现4。对于双进程FSM，建立第2个进程，现态寄存器描述进程，CLK，RST为敏感量；对于单进程FSM，则在一个进程中完成同步状态转移。,Mealy状态机：如果时序逻辑的输出不仅取决于状态还取决于输入，那么称之为Mealy机。而有些时序逻辑电的输出只取决于当前状态，即输出信号=G（当前状态），这样的就称为Moore状态

14、机。,两种电路结构除了在输出电路部分有些不同外，其他地方都是相同的。在设计高速电路时，常常有必要使状态机的输出与时钟几乎完全同步。有一个办法是把状态变量直接用作输出，为此在指定状态编码时多费一些脑力，有可能会多用几个寄存器。设计告诉状态机还有一个办法，在输出逻辑G后面再加一组与时钟同步的寄存器输出流水线寄存器，让G所有的输出信号在下一个时钟跳变沿时同时存入寄存器组，即完全同步的输出，这种输出称为流水线化的输出的Mealy状态机。,Flip-Flops,FLIP-FLOPs are trivial FSMsUse state diagrams to remember flip-flops fun

15、ctions,S&R,S&R,SR,FSM performance,Maximum frequency of operation is computed as:,Tnextstate,Tsetup,Td,Tout,FSM Equations,What values of D1 and D2 will move the FSM to the state 01?,FSM next state and output logic can be easily derived by inspecting the state diagram.,To move the FSM to state 01 the

16、next state logic must produce 1 on D2 and 0 on D1.,D2=Q2+=in1&00#in1&11#in1&01#.,D1=Q1+=,coming from state:00 11 01,FSM Equations,The output logic can be easily derived as a logical sum of all the states where 1 on the output is produced(Moore).,D2=Q1+=in1&00#in1&11#in1&01#.,D1=Q1+=.,D2=Q1+=in1&Q1&Q

17、2#in1&Q1&Q2#in1&Q1&Q2#.,Out1=Q1&Q2#.,FSM Equations,Moore型FSM信号输出方法,由状态编码位经组合译码后输出并行输出寄存器的译码输出状态位里的编码输出一位有效编码方式,FSM输出方法1,由状态编码位经组合译码后输出 delay,FSM输出方法2,并行输出寄存器的译码输出,FSM输出方法3,状态位里的编码输出缩短输出延时要求状态位编码与输出信号要求的值相结合,DFFs,OutputComb.Logic,FeedbackComb.Logic,FSM输出方法4,ONE HOT编码使用N位状态寄存器表达具有Ng 状态的FSM，每个状态具有独立的寄存

18、器位。任意时刻只有1位寄存器为1，即hot point。此为one hot。One hot 编码方程用简单的次态方程驱动，减少了状态寄存器之间的组合逻辑级数，因此提高了运行速度。同时是以牺牲寄存器逻辑资源和提高成本为代价的。目标器件具有较多寄存器资源，寄存器之间组合逻辑较少时比较适用。,FSM的容错设计,枚举型数据状态编码在综合时转换为矢量信号，状态位数目=log2N，N：状态数若log2N不为整数，存在未定义状态，非法状态。不考虑非法状态则可减少设计的逻辑数目，考虑非法状态则可降低系统容错性原因：干扰，噪声，电源变化等引起触发器翻转误入非法状态，造成死锁。处理：转入空闲态；转入指定态；转入预

19、定义的错误处理告警状态default:State=idle;-转入空闲态；default:State=“XXXXX”;-忽略；对one hot型FSM，可编写检错程序，判断是否同时又多个状态寄存器为1，若有做相应出错处理。,状态机的状态编码 有限状态机设计是基于状态描述的，因此首先必须对系统中的每一个工作状态有一个合理的表达。对于设计者而言，为了表达简捷方便通常使用符号化状态机。例如：二进制编码方案：是用N位二进制数，表示M个工作状态，当然必须满足2N大于等于M。一位热码编码方案：用N位二进制数表示N个状态，每一位编码对应一个触发器，状态机中的每个状态都由其中一个触发器的状态来表示。,Choo

20、se bit vectors to assign to each“symbolic”stateWith n state bits for m states there are 2n!/(2n m)!state assignments log n=m=2n2n codes possible for 1st state,2n1 for 2nd,2n2 for 3rd,Huge number even for small values of n and mIntractable for state machines of any sizeHeuristics are necessary for pr

21、actical solutionsOptimize some metric for the combinational logicSize(amount of logic and number of FFs)Speed(depth of logic and fanout)Dependencies(decomposition),State Assignment Strategies,Possible StrategiesSequential just number states as they appear in the state tableRandom pick random codesOn

22、e-hot use as many state bits as there are states(bit=1 state)Output use outputs to help encode states(counters)Heuristic rules of thumb that seem to work in most casesNo guarantee of optimality an intractable problem,One-hot State Assignment,SimpleEasy to encode,debugSmall Logic FunctionsEach state

23、function requires only predecessor state bits as inputGood for Programmable DevicesLots of flip-flops readily availableSimple functions with small support(signals its dependent upon)Impractical for Large MachinesToo many states require too many flip-flopsDecompose FSMs into smaller pieces that can b

24、e one-hot encodedMany Slight Variations to One-hot“two hot”,The encoding style for an FSM has a high impact on the quality of the FSM implementation in timing,area,power,and other attributes.Some of the most common encoding styles include one-hot encoding,Gray encoding,and minimum encoding.The one-h

25、ot-encoding style means that only one bit of the state registers can be at one for any given state of the FSM.a higher number of registers in the final implementation.The combinational-logic complexity resulting from one-hot encoding may be comparable or slightly more than other encoding styles,but

26、the combinational logic controlling the data input of each state register may be smaller,which may contribute to better timing performance.A designer may choose this encoding style for its simplicity and its timing performance.FPGA has lot of registers compared to CPLD.so onehot is more suitable for

27、 FPGA,Gray encoding states for any transition in an FSM have only one different bit in their encodings.Because a single register can change value during any transition,Gray encoding is the best choice for lower power consumption.The number of registers for encoding the states may be small,but the co

28、mbinational-logic complexity for next-state and output generation is unpredictable.It may be difficult to find an optimal Gray-encoding scheme for large FSMs with many transitions.,Minimum encodingthe minimum number of state registers,but the control logic may be more complex.A designer can minimize

29、 the combinational logic with carefully assigned encoding.Depending on the level of optimization in the encoding,this encoding style may result in good or poor timing and area performance.Unless a designer deploys an optimized encoding scheme,this encoding style may be a poor choice.Use it if the to

30、tal number of registers in a design is a concern,but dont use it if power is the main concern.,Designers may want to consider custom encoding as a variation of the minimum-encoding style,which adds extra bits or registers to accomplish power,area,or timing goals.It does not have to follow the one-ho

31、t-or Gray-encoding style,and designers should not use it unless the projects performance requirements justify its use.One-hot encoding-more efficient for FPGA architectures.one flip-flop per state and decreased width of combinatorial logic.One-hot encoding is usually the preferred method for large F

32、PGA-based state machine implementation.For small state machines(fewer than 8 states),binary encoding may be more efficient.To improve design performance,you can divide large(greater than 32 states)state machines into several small state machines and use the appropriate encoding style for each.,介绍一下独

33、热编码：Parameter Idle=4b1000,Start=4b0100,Stop=4b0010,Clear=4b0001;用独热编码还是Gray码要看具体情况而定。对于用FPGA实现的有限状态机建议用独热码，虽然独热码多用了触发器，但所用组合电路可省一些，因而使电路的速度和可靠性有显著提高，而总的单元数并无显著增加。采用独热编码后出现的多余状态，在case语句的最后需要增加default分支项。确保可以回到Idle。,One-hot编码的特点,组合逻辑最少，触发器最多，工作时钟频率可以做到最高。FPGA 的一个最小结构单元（CLB/LE）中含有查找表（实现组合逻辑）和DFF（实现时序逻辑

34、），布局布线最好的结果是同一个结构单元中的查找表和DFF都使用，但是大部分情况是仅使用其中一种资源，这样另外的资源就是闲置而浪费。而CPLD中DFF资源本来就很少，由此可见One-hot编码更适合于 FPGA设计，而不适合CPLD设计，在CPLD中应该选择二进制编码。IC设计中，应该综合考虑。因为One-hot编码使用DFF会大大增加设计面积（die size），因此在时序可以满足的条件下尽可能使用二进制编码。就面积与速度的折中考虑来说Gray码是最好的选择，当然Gray码还有其他很多好的特性，暂时不属于这次讨论的范畴。一般的综合工具对状态机进行综合时都可以让用户对这三种编码进行选择。基本依据

35、就以上所说。,状态机的编码,Binary、gray-code 编码使用最少的触发器，较多的组合逻辑。而one-hot编码反之。由于CPLD 更多的提供组合逻辑资源，而FPGA 更多的提供触发器资源，所以CPLD多使用gray-code，而FPGA多使用one-hot 编码。另一方面，对于小型设计使用gray-code和binary 编码更有效，而大型状态机使用one-hot 更高效。,IC设计中，应该综合考虑。因为One-hot编码使用DFF会大大增加设计面积（die size），因此在时序可以满足的条件下尽可能使用二进制编码。就面积与速度的折中考虑来说Gray码是最好的选择，当然Gray码还

36、有其他很多好的特性，暂时不属于这次讨论的范畴。一般的综合工具对状态机进行综合时都可以让用户对这三种编码进行选择。基本依据就以上所说。,设计有限状态机的参考步骤：(5 steps)逻辑抽象，得出状态转换图：就是把给出的一个实际逻辑关系表示为时序逻辑函数。可以用状态转换表来描述，也可以用状态转换图来描述。状态化简：如果在状态转换图中出现这样两个状态：它们在相同的输入下转换到同一个状态中，并得到相同的输出，或称它们为等价状态。显然等价状态是重复的，可以合并为一个。电路的状态越少，存储电路也就越简单。状态分配：状态分配又称状态编码。通常有很多编码方法，编码方案选择得当，设计的电路简单，反之，选得不好，

37、则设计的电路就会复杂许多。选定触发器的类型并求出状态方程、驱动方程和输出方程按照方程得出逻辑图,用Verilog HDL来描述有限状态机，可以充分发挥硬件描述语言的抽象建模能力，使用always块语句和case(if)等条件语句及赋值语句即可方便实现。具体的逻辑化简、逻辑电路和触发器映射均可由计算机自动完成，上述设计步骤中的第(2)布及(4)、(5)步不再需要很多的人为干预，使电路设计工作得以简化，效率也大为提高。,FSM 描述风格,用Verilog 语言描述有限状态机可使用多种风格，不同的风格会极大地影响电路性能。通常有3种描述方式：单always块、双always块和三always块。单a

38、lways块把组合逻辑和时序逻辑用同一个时序always块描述，其输出是寄存器输出，无毛刺。但是这种方式会产生多余的触发器，代码难于修改和调试，应该尽量避免使用。,FSM 描述风格,双always块大多用于描述Mealy状态机和组合输出的Moore状态机，时序always块描述当前状态逻辑，组合逻辑always块描述次态逻辑并给输出赋值。这种方式结构清晰，综合后的面积和时间性能好。但组合逻辑输出往往会有毛刺，当输出向量作为时钟信号时，这些毛刺会对电路产生致命的影响。三always块大多用于同步Mealy状态机，两个时序always块分别用来描述现态逻辑和对输出赋值，组合always块用于产生下

39、一状态。这种方式的状态机也是寄存器输出，输出无毛刺，并且代码比单always块清晰易读，但是面积大于双always块。随着芯片资源和速度的提高，目前这种方式得到了广泛应用。,Verilog三段式状态机描述,时序电路的状态是一个状态变量集合，这些状态变量在任意时刻的值都包含了为确定电路的未来行为而必需考虑的所有历史信息。状态机采用VerilogHDL语言编码，建议分为三个always段完成。三段式建模描述FSM的状态机输出时，只需指定case敏感表为次态寄存器，然后直接在每个次态的case分支中描述该状态的输出即可，不用考虑状态转移条件。三段式描述方法虽然代码结构复杂了一些，但是换来的优势是：使

40、FSM做到了同步寄存器输出，消除了组合逻辑输出的不稳定与毛刺的隐患，而且更利于时序路径分组，一般来说在FPGA/CPLD等可编程逻辑器件上的综合与布局布线效果更佳。,三段式状态机描述示列,/第一个进程，同步时序always模块，格式化描述次态寄存器迁移到现态寄存器always(posedge clk or negedge rst_n)/异步复位if(!rst_n)current_state=IDLE;else current_state=next_state;/注意，使用的是非阻塞赋值/第二个进程，组合逻辑always模块，描述状态转移条件判断always(current_state)/电平触

41、发 begin next_state=x;/要初始化，使得系统复位后能进入正确的状态 case(current_state)S1:if(.)next_state=S2;/阻塞赋值.endcaseend,三段式状态机描述示列,/第三个进程，同步时序always模块，格式化描述次态寄存器输出always(posedge clk or negedge rst_n)./初始化case(next_state)S1:out1=1b1;/注意是非阻塞逻辑S2:out2=1b1;default:./default的作用是免除综合工具综合出锁存器endcaseend,两段式与三段式有限状态机的区别,FSM将时序

42、部分（状态转移部分）和组合部分（判断状态转移条件和产生输出）分开，写为两个always语句，即为两段式有限状态机。将组合部分中的判断状态转移条件和产生输入再分开写，则为三段式有限状态机。区别：二段式在组合逻辑特别复杂时适用，但要注意需在后面加一个触发器以消除组合逻辑对输出产生的毛刺。三段式没有这个问题，由于第三个always会生成触发器。,综合状态机的一般原则,在硬件描述语言中，许多基于仿真的语句虽然符合语法规则，但是不能映射到硬件逻辑电路单元，如果要最终实现硬件设计，必须写出可以综合的程序。通常，综合的原则为：综合之前一定要进行仿真，仿真会暴露逻辑错误。如果不做仿真，没有发现的逻辑错误会进入

43、综合器，使综合的结果产生同样的逻辑错误。每一次布线之后都要进行仿真，在器件编程或流片之前一定要进行最后的仿真。用Verilog HDL描述的异步状态机是不能综合的，应该避免用综合器来设计。在必须设计异步状态机时，建议用电路图输入的方法 状态机应该有一个异步或同步复位端，以便在通电时将硬件电路复位到有效状态。建议使用异步复位以简化硬件开销。时序逻辑电路建模时，用非阻塞赋值。用always块写组合逻辑时，采用阻塞赋值。不要在多个always块中为同一个变量赋值。always块中应该避免组合反馈回路。在赋值表达式右端参与赋值的信号都必须出现在敏感信号列表中，否则在综合时，会为没有列出的信号隐含地产生

44、一个透明锁存器。,More reference,The Fundamentals of Efficient Synthesizable Finite State Machine Design using NC-Verilog and BuildGatesCoding And Scripting Techniques For FSM Designs With Synthesis-Optimized,Glitch-Free OutputsState Machine Coding Styles for Synthesis技术笔记状态机性能考察,Other methods,Quartus state machine design entry toolexample,谢谢大家！,