同步状态机的原理、结构与设计

同步状态机的原理、结构和设计FSM状态机分类Moore型状态机设计状态机复位Moore型状态机信号输出方法Mealy型状态机状态机容错设计状态机一般定义（FiniteStateMachine，FSM）◆状态机——

一个离散数学模型。给定一个输入集合，根据对输入的接受次序来决定一个输出集合。（摩尔状态机）◆状态——系统的基本数学特征。◆有限状态机——

输入集合和输出集合都是有限的，并只有有限数目的状态。什么是状态机有限状态机(简称状态机)相当于一个控制器，它将一项功能的完成分解为若干步，每一步对应于二进制的一个状态，通过预先设计的顺序在各状态之间进行转换，状态转换的过程就是实现逻辑功能的过程。

为什么使用状态机有限状态机克服了纯硬件数字系统顺序方式控制不灵活的缺点。

设计方案相对固定，结构模式简单，可定义符号化枚举类型的状态。状态机的HDL描述层次分明，结构清晰，易读易懂。状态机容易构成性能良好的同步时序逻辑模块。在高速运算和控制方面，状态机更有其巨大的优势。基于有限状态机技术设计的控制器其工作速度大大优于CPU。就可靠性而言，状态机的优势也是十分明显的。基于有限状态机技术设计的控制器其可靠性也优于CPU。输入集合A输出集合X状态记忆输出形成状态迁移状态机一般结构CLK组合逻辑时序逻辑同步当前状态后续状态Sa1,a2,…,anx1,x2,…,xn状态位置状态名称转移方向输入集合（触发事件）输出集合（执行动作）状态等待状态迁移图nna1,a2,…,anx1,x2,…,xn状态位置状态名称转移方向输入集合（触发事件）输出集合（执行动作）状态等待状态迁移图S状态编码FSM应用FSM通过状态图描述状态转换过程FSM：数字系统控制单元的建模数字系统：受控模块：功能模块，设计较易控制模块实现CPUFSM执行耗费时间，执行时间的确定性方面，FSM优于CPUFSM构成FSM用来解决一般时序逻辑电路问题，包括同步/异步时序逻辑状态寄存器当前状态（现态）寄存器组合逻辑电路下一状态（次态）组合逻辑输出组合逻辑FSM分类Moore型：输出信号仅与现态相关Mealy型：输出信号与现态和输入相关DFFsOutput

Comb.LogicFeedback

Comb.LogicDFFsOutput

Comb.LogicFeedback

Comb.LogicMooreMealy现态次态输入输出现态次态输出输入Moore型状态机设计方法摩尔型状态机的典型结构Moore型状态机设计方法

More型状态机输出仅和存储电路的状态有关，与外部输入无关，即:

外部输出是内部状态的函数。状态转移图描述方式：Si/ZOiData_INiMealy型状态机设计方法米勒型状态机的典型结构

Mealy型状态机输出不仅和存储电路状态有关，还和外部输入信号有关，即:

外部输出是内部状态和外部输入的函数状态图描述方式：SiData_INi/ZOiMealy型状态机设计方法Exampleofa5-stateMealyFSM

modulemealy(data_in,data_out,reset,clock);outputdata_out;input[1:0]data_in;inputreset,clock;regdata_out;reg[2:0]pres_state,next_state;parameterst0=3'd0,st1=3'd1,st2=3'd2,st3=3'd3,st4=3'd4;//FSMregisteralways@(posedgeclockornegedgereset)begin:stateregif(!reset)//asynchronousresetpres_state=st0;elsepres_state=next_state;end//statereg//FSMcombinationalblockalways@(pres_stateordata_in)begin:fsmcase(pres_state)st0:

case(data_in)2'b00:

next_state=st0;2'b01:

next_state=st4;2'b10:

next_state=st1;2'b11:

next_state=st2;endcasest1:

case(data_in)2'b00:

next_state=st0;2'b10:

next_state=st2;default:

next_state=st1;endcasest2:

case(data_in)2'b0x:

next_state=st1;2'b1x:

next_state=st3;endcasest3:

case(data_in)2'bx1:

next_state=st4;default:

next_state=st3;endcasest4:

case(data_in)2'b11:

next_state=st4;default:

next_state=st0;endcasedefault:

next_state=st0;endcaseend//fsm//Mealyoutputdefinitionusingpres_statew/data_inalways@(data_inorpres_state)begin:outputscase(pres_state)st0:

case(data_in)2'b00:

data_out=1'b0;default:

data_out=1'b1;endcasest1:

data_out=1'b0;st2:

case(data_in)2'b0x:

data_out=1'b0;default:

data_out=1'b1;endcasest3:

data_out=1'b1;st4:

case(data_in)2'b1x:

data_out=1'b1;default:

data_out=1'b0;endcasedefault:

data_out=1'b0;endcaseend//outputsendmoduleExampleofa5-stateMooreFSMmodulemoore(data_in,data_out,reset,clock);outputdata_out;input[1:0]data_in;inputreset,clock;regdata_out;reg[2:0]pres_state,next_state;parameterst0=3'd0,st1=3'd1,st2=3'd2,st3=3'd3,st4=3'd4;//FSMregisteralways@(posedgeclockornegedgereset)begin:stateregif(!reset)pres_state=st0;elsepres_state=next_state;end//statereg//FSMcombinationalblockalways@(pres_stateordata_in)begin:fsmcase(pres_state)st0:

case(data_in)2'b00:

next_state=st0;2'b01:

next_state=st4;2'b10:

next_state=st1;2'b11:

next_state=st2;endcasest1:

case(data_in)2'b00:

next_state=st0;2'b10:

next_state=st2;default:

next_state=st1;endcasest2:

case(data_in)2'b0x:

next_state=st1;2'b1x:

next_state=st3;endcasest3:

case(data_in)2'bx1:

next_state=st4;default:

next_state=st3;endcasest4:

case(data_in)2'b11:

next_state=st4;default:

next_state=st0;endcasedefault:

next_state=st0;endcaseend//fsm//Mooreoutputdefinitionusingpres_stateonlyalways@(pres_state)begin:outputscase(pres_state)st0:

data_out=1'b1;st1:

data_out=1'b0;st2:

data_out=1'b1;st3:

data_out=1'b0;st4:

data_out=1'b1;default:data_out=1'b0;endcaseend//outputsendmodule//Mooreverilog语言描述FSM的建立过程跟据具体要求分析控制过程，建立状态转移图后：1。定义枚举类型的信号描述状态2。建立第1个always，描述次态组合逻辑，现态和输入信号作为敏感量，3。在进程中定义状态转移CASE语句的一条表示一个状态，状态转移通过IFELSE语句实现4。对于双进程FSM，建立第2个进程，现态寄存器描述进程，CLK，RST为敏感量；对于单进程FSM，则在一个进程中完成同步状态转移。Mealy状态机：如果时序逻辑的输出不仅取决于状态还取决于输入，那么称之为Mealy机。而有些时序逻辑电的输出只取决于当前状态，即输出信号=G（当前状态），这样的就称为Moore状态机。两种电路结构除了在输出电路部分有些不同外，其他地方都是相同的。在设计高速电路时，常常有必要使状态机的输出与时钟几乎完全同步。有一个办法是把状态变量直接用作输出，为此在指定状态编码时多费一些脑力，有可能会多用几个寄存器。设计告诉状态机还有一个办法，在输出逻辑G后面再加一组与时钟同步的寄存器输出流水线寄存器，让G所有的输出信号在下一个时钟跳变沿时同时存入寄存器组，即完全同步的输出，这种输出称为流水线化的输出的Mealy状态机。Flip-FlopsFLIP-FLOPsaretrivialFSMsUsestatediagramstorememberflip-flopsfunctions10DDDDD10TTTTT10JKJKJK10S&RS&RSRSRFSMperformanceMaximumfrequencyofoperationiscomputedas:

Out1Q1Q2D2D1Q1Q2in1ClkNextState01outTnextstate

Tsetup

Td

Tout

FSMEquationsOut1Q1Q2D2D1Q1Q2in1ClkNextState01out010011in1in1in11in1StructureofaFSMwithtwoF-FsofDtypeSamplepartofastatediagramWhatvaluesofD1andD2willmovetheFSMtothestate01?FSMnextstateandoutputlogiccanbeeasilyderivedbyinspectingthestatediagram.TomovetheFSMtostate01thenextstatelogicmustproduce‘1’onD2and‘0’onD1.D2=Q2+=in1&00#in1&11#in1&01#...D1=Q1+=Out1Q1Q2D2D1Q1Q2in1ClkNextState01out010011in1in1in11in1comingfromstate:001101FSMEquationsTheoutputlogiccanbeeasilyderivedasalogicalsumofallthestateswhere‘1’ontheoutputisproduced(Moore).D2=Q1+=in1&00#in1&11#in1&01#...D1=Q1+=...D2=Q1+=in1&Q1&Q2#in1&Q1&Q2#in1&Q1&Q2#...Out1=Q1&Q2#....Out1Q1Q2D2D1Q1Q2in1ClkNextState01out010011in1in1in11in1FSMEquationsMoore型FSM信号输出方法由状态编码位经组合译码后输出并行输出寄存器的译码输出状态位里的编码输出一位有效编码方式FSM输出方法1由状态编码位经组合译码后输出delayFSM输出方法2并行输出寄存器的译码输出FSM输出方法3状态位里的编码输出缩短输出延时要求状态位编码与输出信号要求的值相结合DFFsOutput

Comb.LogicFeedback

Comb.LogicFSM输出方法4ONEHOT编码使用N位状态寄存器表达具有Ng状态的FSM，每个状态具有独立的寄存器位。任意时刻只有1位寄存器为1，即hotpoint。此为onehot。Onehot编码方程用简单的次态方程驱动，减少了状态寄存器之间的组合逻辑级数，因此提高了运行速度。同时是以牺牲寄存器逻辑资源和提高成本为代价的。目标器件具有较多寄存器资源，寄存器之间组合逻辑较少时比较适用。FSM的容错设计枚举型数据状态编码在综合时转换为矢量信号，状态位数目=log2N，N：状态数若log2N不为整数，存在未定义状态，非法状态。不考虑非法状态则可减少设计的逻辑数目，考虑非法状态则可降低系统容错性原因：干扰，噪声，电源变化等引起触发器翻转误入非法状态，造成死锁。处理：转入空闲态；转入指定态；转入预定义的错误处理告警状态default:State<=idle;---转入空闲态；default:State<=“XXXXX”;---忽略；对onehot型FSM，可编写检错程序，判断是否同时又多个状态寄存器为1，，若有做相应出错处理。状态机的状态编码有限状态机设计是基于状态描述的，因此首先必须对系统中的每一个工作状态有一个合理的表达。对于设计者而言，为了表达简捷方便通常使用符号化状态机。例如：二进制编码方案：是用N位二进制数，表示M个工作状态，当然必须满足2N大于等于M。一位热码编码方案：用N位二进制数表示N个状态，每一位编码对应一个触发器，状态机中的每个状态都由其中一个触发器的状态来表示。Choosebitvectorstoassigntoeach“symbolic”stateWithnstatebitsformstatesthereare2n!/(2n

–m)!stateassignments[logn<=m<=2n]2ncodespossiblefor1ststate,2n–1for2nd,2n–2for3rd,…HugenumberevenforsmallvaluesofnandmIntractableforstatemachinesofanysizeHeuristicsarenecessaryforpracticalsolutionsOptimizesomemetricforthecombinationallogicSize(amountoflogicandnumberofFFs)Speed(depthoflogicandfanout)Dependencies(decomposition)StateAssignmentStrategiesPossibleStrategiesSequential

–

justnumberstatesastheyappearinthestatetableRandom

–

pickrandomcodesOne-hot

–

useasmanystatebitsastherearestates(bit=1–>state)Output

–

useoutputstohelpencodestates(counters)Heuristic

–

rulesofthumbthatseemtoworkinmostcasesNoguaranteeofoptimality

–

anintractableproblemOne-hotStateAssignmentSimpleEasytoencode,debugSmallLogicFunctionsEachstatefunctionrequiresonlypredecessorstatebitsasinputGoodforProgrammableDevicesLotsofflip-flopsreadilyavailableSimplefunctionswithsmallsupport(signalsitsdependentupon)ImpracticalforLargeMachinesToomanystatesrequiretoomanyflip-flopsDecomposeFSMsintosmallerpiecesthatcanbeone-hotencodedManySlight

VariationstoOne-hot

–

“twohot”TheencodingstyleforanFSMhasahighimpactonthequalityoftheFSMimplementationintiming,area,power,andotherattributes.Someofthemostcommonencodingstylesinclude

one-hotencoding,Grayencoding,andminimumencoding.

Theone-hot-encodingstylemeansthatonlyonebitofthestateregisterscanbeatoneforanygivenstateoftheFSM.ahighernumberofregistersinthefinalimplementation.Thecombinational-logiccomplexityresultingfromone-hotencodingmaybecomparableorslightlymorethanotherencodingstyles,butthecombinationallogiccontrollingthedatainputofeachstateregistermaybesmaller,whichmaycontributetobettertimingperformance.Adesignermaychoosethisencodingstyleforitssimplicityanditstimingperformance.FPGAhaslotofregisterscomparedtoCPLD.soonehotismoresuitableforFPGAGrayencodingstatesforanytransitioninanFSMhaveonlyonedifferentbitintheirencodings.Becauseasingleregistercanchangevalueduringanytransition,Grayencodingisthebestchoiceforlowerpowerconsumption.Thenumberofregistersforencodingthestatesmaybesmall,butthecombinational-logiccomplexityfornext-stateandoutputgenerationisunpredictable.ItmaybedifficulttofindanoptimalGray-encodingschemeforlargeFSMswithmanytransitions.Minimumencodingtheminimumnumberofstateregisters,butthecontrollogicmaybemorecomplex.Adesignercanminimizethecombinationallogicwithcarefullyassignedencoding.Dependingonthelevelofoptimizationintheencoding,thisencodingstylemayresultingoodorpoortimingandareaperformance.Unlessadesignerdeploysanoptimizedencodingscheme,thisencodingstylemaybeapoorchoice.Useitifthetotalnumberofregistersinadesignisaconcern,butdon'tuseitifpoweristhemainconcern.Designersmaywanttoconsidercustomencodingasavariationoftheminimum-encodingstyle,whichaddsextrabitsorregisterstoaccomplishpower,area,ortiminggoals.Itdoesnothavetofollowtheone-hot-orGray-encodingstyle,anddesignersshouldnotuseitunlesstheproject'sperformancerequirementsjustifyitsuse.One-hotencoding->moreefficientforFPGAarchitectures.oneflip-flopperstateanddecreasedwidthofcombinatoriallogic.One-hotencodingisusuallythepreferredmethodforlargeFPGA-basedstatemachineimplementation.Forsmallstatemachines(fewerthan8states),binaryencodingmaybemoreefficient.Toimprovedesignperformance,youcandividelarge(greaterthan32states)statemachinesintoseveralsmallstatemachinesandusetheappropriateencodingstyleforeach.介绍一下独热编码：ParameterIdle=4’b1000,Start=4’b0100, Stop=4’b0010,Clear=4’b0001;用独热编码还是Gray码要看具体情况而定。对于用FPGA实现的有限状态机建议用独热码，虽然独热码多用了触发器，但所用组合电路可省一些，因而使电路的速度和可靠性有显著提高，而总的单元数并无显著增加。采用独热编码后出现的多余状态，在case语句的最后需要增加default分支项。确保可以回到Idle。One-hot编码的特点

组合逻辑最少，触发器最多，工作时钟频率可以做到最高。

FPGA的一个最小结构单元（CLB/LE）中含有查找表（实现组合逻辑）和DFF（实现时序逻辑），布局布线最好的结果是同一个结构单元中的查找表和DFF都使用，但是大部分情况是仅使用其中一种资源，这样另外的资源就是闲置而浪费。而CPLD中DFF资源本来就很少，由此可见One-hot编码更适合于FPGA设计，而不适合CPLD设计，在CPLD中应该选择二进制编码。

IC设计中，应该综合考虑。因为One-hot编码使用DFF会大大增加设计面积（diesize），因此在时序可以满足的条件下尽可能使用二进制编码。就面积与速度的折中考虑来说Gray码是最好的选择，当然Gray码还有其他很多好的特性，暂时不属于这次讨论的范畴。一般的综合工具对状态机进行综合时都可以让用户对这三种编码进行选择。基本依据就以上所说。状态机的编码Binary、gray-code编码使用最少的触发器，较多的组合逻辑。而one-hot编码反之。由于CPLD更多的提供组合逻辑资源，而FPGA更多的提供触发器资源，所以CPLD多使用gray-code，而FPGA多使用one-hot编码。另一方面，对于小型设计使用gray-code和binary编码更有效，而大型状态机使用one-hot更高效。IC设计中，应该综合考虑。因为One-hot编码使用DFF会大大增加设计面积（diesize），因此在时序可以满足的条件下尽可能使用二进制编码。就面积与速度的折中考虑来说Gray码是最好的选择，当然Gray码还有其他很多好的特性，暂时不属于这次讨论的范畴。一般的综合工具对状态机进行综合时都可以让用户对这三种编码进行选择。基本依据就以上所说。设计有限状态机的参考步骤：(5steps)逻辑抽象，得出状态转换图：就是把给出的一个实际逻辑关系表示为时序逻辑函数。可以用状态转换表来描述，也可以用状态转换图来描述。状态化简：如果在状态转换图中出现这样两个状态：它们在相同的输入下转换到同一个状态中，并得到相同的输出，或称它们为等价状态。显然等价状态是重复的，可以合并为一个。电路的状态越少，存储电路也就越简单。状态分配：状态分配又称状态编码。通常有很多编码方法，编码方案选择得当，设计的电路简单，反之，选得不好，则设计的电路就会复杂许多。选定触发器的类型并求出状态方程、驱动方程和输出方程按照方程得出逻辑图用VerilogHDL来描述有限状态机，可以充分发挥硬件描述语言的抽象建模能力，使用always块语句和case(if)等条件语句及赋值语句即可方便实现。具体的逻辑化简、逻辑电路和触发器映射均可由计算机自动完成，上述设计步骤中的第(2)布及(4)、(5)步不再需要很多的人为干预，使电路设计工作得以简化，效率也大为提高。FSM描述风格用Verilog语言描述有限状态机可使用多种风格，不同的风格会极大地影响电路性能。通常有3种描述方式：单always块、双always块和三always块。

单always块把组合逻辑和时序逻辑用同一个时序always块描述，其输出是寄存器输出，无毛刺。但是这种方式会产生多余的触发器，代码难于修改和调试，应该尽量避免使用。

FSM描述风格双always块大多用于描述Mealy状态机和组合输出的Moore状态机，时序always块描述当前状态逻辑，组合逻辑always块描述次态逻辑并给输出赋值。这种方式结构清晰，综合后的面积和时间性能好。但组合逻辑输出往往会有毛刺，当输出向量作为时钟信号时，这些毛刺会对电路产生致命的影响。三always块大多用于同步Mealy状态机，两个时序always块分别用来描述现态逻辑和对输出赋值，组合always块用于产生下一状态。这种方式的状态机也是寄存器输出，输出无毛刺，并且代码比单always块清晰易读，但是面积大于双always块。随着芯片资源和速度的提高，目前这种方式得到了广泛应用。Verilog三段式状态机描述时序电路的状态是一个状态变量集合，这些状态变量在任意时刻的值都包含了为确定电路的未来行为而必需考虑的所有历史信息。状态机采用VerilogHDL语言编码，建议分为三个always段完成。三段式建模描述FSM的状态机输出时，只需指定case敏感表为次态寄存器，然后直接在每个次态的case分支中描述该状态的输出即可，不用考虑状态转移条件。三段式描述方法虽然代码结构复杂了一些，但是换来的优势是：使FSM做到了同步寄存器输出，消除了组合逻辑输出的不稳定与毛刺的隐患，而且更利于时序路径分组，一般来说在FPGA/CPLD等可编程逻辑器件上的综合与布局布线效果更佳。三段式状态机描述示列//第一个进程，同步时序always模块，格式化描述次态寄存器迁移到现态寄存器always@(posedgeclkornegedgerst_n)

//异步复位

if(!rst_n)

current_state<=IDLE;