有限狀態(tài)機(jī)的狀態(tài)編碼(第八節(jié))

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

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

X:00101010010…

Z:00010101000…

X:11011010010…

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

[0]10or1S5

[0]00S6

[0]S0

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

只要輸入為1就會(huì)在此循環(huán)1...01...010...100S4

[0]S1[0]S0

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

[0]00S6

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

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

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

[0]S1[0]S0

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

[0]00S6

[0]...1...010...1011VIII-WorkingwithSequentialLogic4?Copyright2004,GaetanoBorrielloandRandyH.Katz有限輸入串的識(shí)別器包括狀態(tài)分配（或狀態(tài)編碼）的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有限輸入串的識(shí)別器（測(cè)試程序）`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狀態(tài)分配狀態(tài)分配是選擇二進(jìn)制位向量分配給每個(gè)符號(hào)狀態(tài)如果m個(gè)狀態(tài)用n位來對(duì)狀態(tài)進(jìn)行編碼，則可能的分配方案有2n!/(2n–m)! 簡(jiǎn)單的按照二進(jìn)制順序來進(jìn)行狀態(tài)分配，設(shè)計(jì)者僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能區(qū)分各個(gè)狀態(tài)單點(diǎn)編碼是用m位狀態(tài)位編碼m個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只有在對(duì)應(yīng)的位上為1，在其它位上均為0啟發(fā)式編碼能實(shí)現(xiàn)良好的狀態(tài)分配，但不能保證是好的電路實(shí)現(xiàn)實(shí)現(xiàn)時(shí)序邏輯網(wǎng)絡(luò)所需門的數(shù)量嚴(yán)重依賴于如何將編碼后的邏輯值分配給符號(hào)狀態(tài)，最優(yōu)的分配方案的唯一途徑是嘗試所有的分配方案VIII-WorkingwithSequentialLogic7?Copyright2004,GaetanoBorrielloandRandyH.Katz狀態(tài)分配策略可能的策略順序編碼隨機(jī)編碼單點(diǎn)編碼面向輸出的編碼啟發(fā)式編碼不能保證結(jié)果是最優(yōu)的–另一個(gè)復(fù)雜的問題VIII-WorkingwithSequentialLogic8?Copyright2004,GaetanoBorrielloandRandyH.Katz順序編碼簡(jiǎn)單的將符號(hào)狀態(tài)名字替換成為規(guī)則的編碼，設(shè)計(jì)者僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)VIII-WorkingwithSequentialLogic9?Copyright2004,GaetanoBorrielloandRandyH.Katz單點(diǎn)編碼簡(jiǎn)單容易編碼、容易診斷和修改小規(guī)模的邏輯函數(shù)適合于FPGA實(shí)現(xiàn)大量的觸發(fā)器可用對(duì)大的狀態(tài)機(jī)不實(shí)用太多的狀態(tài)需要太多的flip-flops對(duì)大的有限狀態(tài)機(jī)劃分成小塊可用單點(diǎn)編碼對(duì)單點(diǎn)編碼進(jìn)行一些改變one-hot+all-0用m位狀態(tài)位編碼m個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只有在對(duì)應(yīng)的位上為1，在其它位上均為0VIII-WorkingwithSequentialLogic10?Copyright2004,GaetanoBorrielloandRandyH.Katz隨機(jī)編碼這是更簡(jiǎn)單的策略，隨機(jī)選擇可能的編碼進(jìn)行分配，它僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)VIII-WorkingwithSequentialLogic11?Copyright2004,GaetanoBorrielloandRandyH.Katz面向輸出的編碼對(duì)于摩爾型，輸出直接與狀態(tài)位有關(guān)，但如果設(shè)計(jì)者直接實(shí)現(xiàn)摩爾型輸出(即觸發(fā)器的輸出就是狀態(tài)機(jī)的輸出），則可以使用輸出來區(qū)別狀態(tài)對(duì)于整個(gè)狀態(tài)機(jī)都使用面向輸出的編碼方式并不是很好的策略，明智的使用部分輸出作為編碼，也許能減少狀態(tài)位的數(shù)量VIII-WorkingwithSequentialLogic12?Copyright2004,GaetanoBorrielloandRandyH.Katz啟發(fā)式方法該方法試圖縮短相關(guān)狀態(tài)間的布爾空間的距離。如狀態(tài)Y用狀態(tài)X轉(zhuǎn)換而來，則它們的狀態(tài)編碼中的不同比特位應(yīng)盡量少狀態(tài)圖：類似于卡諾圖，提供觀察狀態(tài)分配的相鄰性的方法。狀態(tài)圖中的方格按照狀態(tài)位的二進(jìn)制值進(jìn)行索引，給出該編碼的狀態(tài)便放在圖中對(duì)應(yīng)的的方格里VIII-WorkingwithSequentialLogic13?Copyright2004,GaetanoBorrielloandRandyH.Katz最少位變化啟發(fā)式方法目的是使所有狀態(tài)間的轉(zhuǎn)換中發(fā)生變化的位數(shù)最少第二種分配方案：分配S0，由于復(fù)位邏輯工作，通常將全0分配給起始狀態(tài)接下來分配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基于次態(tài)和輸入/輸出的啟發(fā)式方法最高優(yōu)先級(jí)：在給定的輸入轉(zhuǎn)換條件下，具有相同次態(tài)的狀態(tài)應(yīng)該在狀態(tài)圖中放到鄰近的位置

中等優(yōu)先級(jí)：具有相同現(xiàn)態(tài)的次態(tài)應(yīng)放在狀態(tài)圖中鄰近的位置

最低優(yōu)先級(jí)：在給定輸入的情況下，具有相同輸出的狀態(tài)應(yīng)該放在狀態(tài)中鄰近的位置上VIII-WorkingwithSequentialLogic15?Copyright2004,GaetanoBorrielloandRandyH.Katz例1：3比特序列檢測(cè)器，當(dāng)檢測(cè)到010或110時(shí)輸出為1

最高優(yōu)先級(jí)：相同輸入下具有同一次態(tài)的狀態(tài)。S3’、S4’中等優(yōu)先級(jí)：具有相同狀態(tài)的次態(tài)。S3’、S4’最低優(yōu)先級(jí)：在給定輸入條件下具有相同輸出行為的狀態(tài)。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比特序列檢查器最高優(yōu)先級(jí)：相同輸入下具有同一次態(tài)的狀態(tài)。［S3’、S4’］［S7’、S10’］中等優(yōu)先級(jí)：具有相同現(xiàn)態(tài)的次態(tài)。［S1、S2］，2個(gè)［S3’、S4’］［S7’、S10’］最低優(yōu)先級(jí)：在給定輸入條件下具有相同輸出行為的狀態(tài)。0/0：S0、S1、S2、S3’、S4’、S7’1/0：S0、S1、S2、S3’、S4’、S7’、S10’VIII-WorkingwithSequentialLogic17?Copyright2004,GaetanoBorrielloandRandyH.Katz4比特序列檢查器最高優(yōu)先級(jí)：［S3’、S4’］［S7’、S10’］中等優(yōu)先級(jí)：［S1、S2］，2個(gè)［S3’、S4’］［S7’、S10’］最低優(yōu)先級(jí)：0/0：S0、S1、S2、S3’、S4’、S7’

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