同步狀態機的原理、結構和設計FSM狀態機分類Moore型狀態機設計狀態機復位Moore型狀態機信號輸出方法Mealy型狀態機狀態機容錯設計狀態機一般定義（FiniteStateMachine，FSM）◆狀態機——

一個離散數學模型。給定一個輸入集合，根據對輸入的接受次序來決定一個輸出集合。（摩爾狀態機）◆狀態——系統的基本數學特征。◆有限狀態機——

輸入集合和輸出集合都是有限的，并只有有限數目的狀態。什么是狀態機有限狀態機(簡稱狀態機)相當于一個控制器，它將一項功能的完成分解為若干步，每一步對應于二進制的一個狀態，通過預先設計的順序在各狀態之間進行轉換，狀態轉換的過程就是實現邏輯功能的過程。

為什么使用狀態機有限狀態機克服了純硬件數字系統順序方式控制不靈活的缺點。

設計方案相對固定，結構模式簡單，可定義符號化枚舉類型的狀態。狀態機的HDL描述層次分明，結構清晰，易讀易懂。狀態機容易構成性能良好的同步時序邏輯模塊。在高速運算和控制方面，狀態機更有其巨大的優勢。基于有限狀態機技術設計的控制器其工作速度大大優于CPU。就可靠性而言，狀態機的優勢也是十分明顯的?；谟邢逘顟B機技術設計的控制器其可靠性也優于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碼還有其他很多好的特性，暫時不屬于這次討論的范疇。一般的綜合工具對狀態機進行綜合時都可以讓用戶對這三種編碼進行選擇?；疽罁鸵陨纤f。狀態機的編碼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碼還有其他很多好的特性，暫時不屬于這次討論的范疇。一般的綜合工具對狀態機進行綜合時都可以讓用戶對這三種編碼進行選擇?；疽罁鸵陨纤f。設計有限狀態機的參考步驟：(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;