有限輸入串的識別器設計要求：有限輸入串的識別器一個輸入端(X)和一個輸出端(Z)如果上次復位之后輸入沒有觀察到…100…序列，那么只要在輸入端檢測到…010…的輸入序列，輸出端即為1

步驟1:理解說明最好寫出一些輸入樣本和輸出行為:

X:00101010010…

Z:00010101000…

X:11011010010…

Z:00000001000…VIII-WorkingwithSequentialLogic1?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識別器步驟2:畫狀態圖假設用摩爾機實現先畫出其必須識別的串010和100只有一個輸入，則每個狀態應該有兩個分支S1[0]S2[0]01S3[1]0S4

[0]10or1S5

[0]00S6

[0]S0

[0]resetVIII-WorkingwithSequentialLogic2?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識別器離開狀態S3條件:已經識別到…010序列如果下一位輸入為0，那么狀態機已經接收到…100(終止)，到狀態S6，即終止循環狀態如果下一位輸入為1，則狀態機接收序列為…0101，…01(狀態S2)狀態S1條件:S1表示在接收到1之前的…0序列只要輸入為0就會在此循環狀態S4條件:S4描述連1序列的狀態

只要輸入為1就會在此循環1...01...010...100S4

[0]S1[0]S0

[0]S2[0]101reset0or1S3[1]0S5

[0]00S6

[0]...1...010VIII-WorkingwithSequentialLogic3?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識別器S2和S5仍然是不完整的條件S2=…01;如果下一個輸入為1,就不再是010序列的前綴而成為終止序列的前綴(01)1(00)

S4就是代表這種情況S5=…10;如果下一個輸入為1,

則接收機的序列為101，可能為序列010的前綴，S2就是代表這種情況盡可能復用狀態尋找相同的意思最小的狀態使代表狀態的位數可以盡可能少一旦所有狀態有完整的條件轉換，意味著是一個最終狀態圖1...01...010...100S4

[0]S1[0]S0

[0]S2[0]101reset0or1S3[1]0S5

[0]00S6

[0]...1...010...1011VIII-WorkingwithSequentialLogic4?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識別器包括狀態分配（或狀態編碼）的Verilog描述modulestring1(clk,X,rst,Z);inputclk,X,rst;outputZ;parameterS0=3'b000,S1=3'b001,S2=3'b010,S3=3'b011,S4=3'b100,S5=3'b101,S6=3'b110;reg[2:1]state; reg[2:1]next_state;always@(posedge

clk)if(rst)state<=S0;elsestate<=next_state;assignZ=(state==S2);always@(stateorX)case(state)S0:if(X)next_state=S4;elsenext_state=S1;S1:if(X)next_state=S2;elsenext_state=S1;S2:if(X)next_state=S4;elsenext_state=S3;S3:if(X)next_state=S2;elsenext_state=S6;S4:if(X)next_state=S4;elsenext_state=S5;S5:if(X)next_state=S2;elsenext_state=S6;S6:next_state=S6;default:next_state=S0;

endcaseendmoduleVIII-WorkingwithSequentialLogic5?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識別器（測試程序）`timescale1ns/1ns`include"./seq.v"moduleseqdet_Top;

reg

clk,rst;reg[10:0]data;wirez,x;assignx=data[10];always#10clk=~clk;always@(posedge

clk)data<={data[9:0],data[10]};

initialbegin

clk=0;

rst=0;#2rst=1;#30rst=0;data='b1010_1001_00;#500$stop;end

string1m(clk,x,rst,z);

endmodule

VIII-WorkingwithSequentialLogic6?Copyright2004,GaetanoBorrielloandRandyH.Katz狀態分配狀態分配是選擇二進制位向量分配給每個符號狀態如果m個狀態用n位來對狀態進行編碼，則可能的分配方案有2n!/(2n–m)! 簡單的按照二進制順序來進行狀態分配，設計者僅需要保證每個狀態對應唯一的編碼，以保證組合邏輯能區分各個狀態單點編碼是用m位狀態位編碼m個狀態，每個狀態的單點編碼只有在對應的位上為1，在其它位上均為0啟發式編碼能實現良好的狀態分配，但不能保證是好的電路實現實現時序邏輯網絡所需門的數量嚴重依賴于如何將編碼后的邏輯值分配給符號狀態，最優的分配方案的唯一途徑是嘗試所有的分配方案VIII-WorkingwithSequentialLogic7?Copyright2004,GaetanoBorrielloandRandyH.Katz狀態分配策略可能的策略順序編碼隨機編碼單點編碼面向輸出的編碼啟發式編碼不能保證結果是最優的–另一個復雜的問題VIII-WorkingwithSequentialLogic8?Copyright2004,GaetanoBorrielloandRandyH.Katz順序編碼簡單的將符號狀態名字替換成為規則的編碼，設計者僅需要保證每個狀態對應唯一的編碼，以保證組合邏輯能夠區分各個狀態VIII-WorkingwithSequentialLogic9?Copyright2004,GaetanoBorrielloandRandyH.Katz單點編碼簡單容易編碼、容易診斷和修改小規模的邏輯函數適合于FPGA實現大量的觸發器可用對大的狀態機不實用太多的狀態需要太多的flip-flops對大的有限狀態機劃分成小塊可用單點編碼對單點編碼進行一些改變one-hot+all-0用m位狀態位編碼m個狀態，每個狀態的單點編碼只有在對應的位上為1，在其它位上均為0VIII-WorkingwithSequentialLogic10?Copyright2004,GaetanoBorrielloandRandyH.Katz隨機編碼這是更簡單的策略，隨機選擇可能的編碼進行分配，它僅需要保證每個狀態對應唯一的編碼，以保證組合邏輯能夠區分各個狀態VIII-WorkingwithSequentialLogic11?Copyright2004,GaetanoBorrielloandRandyH.Katz面向輸出的編碼對于摩爾型，輸出直接與狀態位有關，但如果設計者直接實現摩爾型輸出(即觸發器的輸出就是狀態機的輸出），則可以使用輸出來區別狀態對于整個狀態機都使用面向輸出的編碼方式并不是很好的策略，明智的使用部分輸出作為編碼，也許能減少狀態位的數量VIII-WorkingwithSequentialLogic12?Copyright2004,GaetanoBorrielloandRandyH.Katz啟發式方法該方法試圖縮短相關狀態間的布爾空間的距離。如狀態Y用狀態X轉換而來，則它們的狀態編碼中的不同比特位應盡量少狀態圖：類似于卡諾圖，提供觀察狀態分配的相鄰性的方法。狀態圖中的方格按照狀態位的二進制值進行索引，給出該編碼的狀態便放在圖中對應的的方格里VIII-WorkingwithSequentialLogic13?Copyright2004,GaetanoBorrielloandRandyH.Katz最少位變化啟發式方法目的是使所有狀態間的轉換中發生變化的位數最少第二種分配方案：分配S0，由于復位邏輯工作，通常將全0分配給起始狀態接下來分配S1、S2，將它們放在S0鄰近位置然后將S3放在S1、S2之間最后將S4放在S3附近VIII-WorkingwithSequentialLogic14?Copyright2004,GaetanoBorrielloandRandyH.KatzI Q Q+ O

i a c j

i b c kI Q Q+ O

i a b j

k a c lI Q Q+ O

i a b j

i c d jc=i*a

+

i*bb=i*a

c=k*aj=i*a+i*c

b=i*a

d=i*ci/ji/kabcabci/jk/lbdi/jaci/j基于次態和輸入/輸出的啟發式方法最高優先級：在給定的輸入轉換條件下，具有相同次態的狀態應該在狀態圖中放到鄰近的位置

中等優先級：具有相同現態的次態應放在狀態圖中鄰近的位置

最低優先級：在給定輸入的情況下，具有相同輸出的狀態應該放在狀態中鄰近的位置上VIII-WorkingwithSequentialLogic15?Copyright2004,GaetanoBorrielloandRandyH.Katz例1：3比特序列檢測器，當檢測到010或110時輸出為1

最高優先級：相同輸入下具有同一次態的狀態。S3’、S4’中等優先級：具有相同狀態的次態。S3’、S4’最低優先級：在給定輸入條件下具有相同輸出行為的狀態。0/0：S0、S1’、S3’1/0：S0、S1’、S3’、S4’S0S1’S3’S4’X/01/01/00/10/0X/0VIII-WorkingwithSequentialLogic16?Copyright2004,GaetanoBorrielloandRandyH.Katz4比特序列檢查器最高優先級：相同輸入下具有同一次態的狀態。［S3’、S4’］［S7’、S10’］中等優先級：具有相同現態的次態。［S1、S2］，2個［S3’、S4’］［S7’、S10’］最低優先級：在給定輸入條件下具有相同輸出行為的狀態。0/0：S0、S1、S2、S3’、S4’、S7’1/0：S0、S1、S2、S3’、S4’、S7’、S10’VIII-WorkingwithSequentialLogic17?Copyright2004,GaetanoBorrielloandRandyH.Katz4比特序列檢查器最高優先級：［S3’、S4’］［S7’、S10’］中等優先級：［S1、S2］，2個［S3’、S4’］［S7’、S10’］最低優先級：0/0：S0、S1、S2、S3’、S4’、S7’

1/0：S0、S1、S2、S3’、S4’、S7’、S10’VIII-WorkingwithSequentialLogic18?Copyright2004,GaetanoBorrielloandRandyH.Katz指導原則的有效性狀態分配指導原則試圖在次態和輸出函數中生成盡可能大的包含邏輯1的相鄰組，使次態函數和輸出的邏輯盡可能少VIII-WorkingwithSequentialLogic19?Copyright2004,GaetanoBorrielloandRandyH.Katz有限狀態機劃分在某些情況下，無法用一個單一的可編程邏輯模塊來實現復雜的有限狀態機，這時需要對狀態機進行劃分假設有限狀態機有20個輸入和10個輸出，但僅用有15個輸入和5個輸出的可編程邏輯模塊來實現VIII-WorkingwithSequentialLogic20?Copyright2004,GaetanoBorrielloandRandyH.Katz引入空閑狀態劃分有限狀態機將該狀態圖劃分為兩個獨立的狀態機，分別包含狀態S1、S2、S3和狀態S4、S5、S6。Ci表示轉換發生的條件需要使用空閑狀態使狀態轉換發生在劃分后的兩部分之間當狀態機由狀態S1轉換到S6時，左圖的子狀態機將控制權交給了右圖，左邊的子狀態機必須停在空閑狀態，直到重新獲得控制權VIII-WorkingwithSequentialLogic21?Copyright2004,GaetanoBorrielloandRandyH.Katz引入空閑狀態劃分有限狀態機劃分后的狀態圖引入兩個新狀態SA和SB，來同步發生在兩部分之間的狀態轉換。兩個狀態機中總有一個處于空閑狀態，同時兩個狀態機需要互相通信，以獲取對方的狀態VIII-WorkingwithSequentialLogic22?Copyright2004,GaetanoBorrielloandRandyH.Katz引入空閑狀態的劃分規則第一條規則：用于源狀態，即跨越邊界的轉換起始于該狀態跨越邊界的轉換由一個到空閑狀態的轉換替代，并且采用和原始狀態轉換相同的退出條件第二條規則：用于跨越邊界轉換的目標狀態原有的轉換被替換為來自空閑狀態的轉換，并且條件為原有條件和源狀態的與運算VIII-WorkingwithSequentialLogic23?Copyright2004,GaetanoBorrielloandRandyH.Katz引入空閑狀態的劃分規則第三條規則：應用于多個轉換發生在同一個源或目標狀態時如果某個狀態是多個跨越邊界的轉換的源如S2，則所有這些轉換都合并到一個空閑狀態的轉換。新轉換的退出條件是將所有原轉換條件進行或運算如C3+C5如果某個狀態是多個跨越邊界狀態轉換的目標狀態如S5，可以添加一個從空閑狀態到該狀態的轉換。新轉換的條件是原有狀態機中各個獨立轉換條件相或如C3S2+C4S3VIII-WorkingwithSequentialLogic24?Copyright2004,GaetanoBorrielloandRandyH.Katz引入空閑狀態的劃分規則第四條規則：空閑狀態的自環條件將所有退出條件相或之后再求反VIII-WorkingwithSequentialLogic25?Copyright2004,GaetanoBorrielloandRandyH.Katz有限狀態機劃分簡單的6進制加減計數器VIII-WorkingwithSequenti