狀態編碼

狀態編碼就是對最小化狀態表中用字母或數字表示的狀態指定一個二進制代碼。

基本介紹

• 中文名：狀態編碼
• 外文名：state encoding;
• 編碼方法：二進制碼、格雷碼、one-hot碼
• 性質：字母或數字
• 作用：提高效率
• 套用學科：計算機原理、單片機、電路分析等

簡介

對最小化狀態表中用字母或數字表示的狀態指定一個二進制代碼，稱狀態編碼或稱狀態分配。狀態編碼後的最小化狀態表稱為二進制狀態表。
狀態編碼的方案不同，所得到的輸出函式和激勵函式的表達式也不相同，從而使設計出來的時序邏輯電路其複雜程度也不相同。

狀態編碼的實現步驟

1、確定狀態編碼的長度，即二進制代碼的位數，也就是觸發器的個數。
狀態編碼的長度是由最小化狀態表中的狀態個數確定。設最小化狀態表的狀態數為N，狀態編碼的長度為m，狀態數N與狀態編碼長度m的關係為：2m-1 < N ≤2m。
2、最佳的或者接近最佳的狀態分配方案，

這使所設計的同步時序邏輯電路的輸出函式和激勵函式最簡單。

狀態編碼方案的好壞還與所採用的觸發器類型有關。也就是，某種狀態編碼方案，對某種觸發器是最佳的編碼方案，然而換成另一種觸發器就不一定是最佳的狀態編碼方案。由此可見，一種最佳狀態編碼方案涉及的因素很多。

狀態編碼基本原則

1、狀態表中的兩個現態，如果在相同外部輸入(X=0或X=1)條件下，這兩個現態的次態相同，則儘可能給這兩個現態分配相鄰的代碼。

2、狀態表中的一個現態，如果在不同外部輸入(X=0且X=1)條件下，這個現態的兩個次態不相同，則儘可能給這兩個次態分配相鄰的代碼。

3、狀態表中兩個現態，如果在不同外部輸入條件下，這個次態有相同的外部輸出，則儘可能給兩個現態分配相鄰的代碼。
4、 狀態表中出現次數最多的狀態在狀態編碼上為邏輯0。

狀態編碼方法

1、二進制編碼

順序二進制編碼，即將狀態依次編碼為順序的二進制數。順序二進制編碼是最緊密的編碼，優點在於它使用的狀態向量位數最少。例如對於6 個狀態的狀態機，只需要 3 位二進制數來進行編碼，因此只需要 3 個觸發器來實現，節約了邏輯資源（在實際套用中，往往需要較多組合邏輯對狀態向量進行解碼以產生輸出，因此實際節約資源的效果並不明顯）。 在上面的例子中，3 位二進制數總共有8 種可能的編碼模式，其中 6 種用來表示有效狀態，剩下的2種是無效編碼。

有人認為順序二進制編碼還有一個好處。當晶片受到粒子輻射或者由於異步輸入等問題可能會造成狀態跳轉失常。如果失常中狀態機跳轉到無效的編碼狀態則可能會出現當機，除非復位否則永遠無法回到 IDLE 狀態。而因為順序二進制編碼最緊密，所以無效編碼最少。失常時有更大的機率跳轉到的有效狀態，並最終回到IDLE 狀態。 這種預想的好處並不會發生在實際中。首先，失常的跳轉到有效狀態並不意味著能夠最終回到IDLE 狀態。例如在某個有效狀態，狀態機循環等待某輸入信號，並作出應答。如果狀態機失常的跳轉到該狀態，同樣會陷入死等，因為輸入信號並不會到來。其次，失常的跳轉到有效狀態，意味著可能在不正確的時機產生輸出，這樣會將故障傳播到其他模組。在很多套用中人們寧願當機不輸出任何信號也不願意輸出錯誤的信號。 可見使用順序二進制編碼並不能使得狀態機具有所想像的容錯能力。

2、Gray碼

Gray碼在發生狀態跳轉時，狀態向量只有一位發生變化。理論上說 Gray狀態機在狀態跳轉時不會有任何毛刺。但是實際上綜合後的狀態機是否還有這個好處也很難說。Gray碼狀態機設計中最大的問題是，在狀態機很複雜狀態跳轉的分支很多時，要合理的分配狀態編碼保證每個狀態跳轉都僅有 1 位發生變化，這是很困難的事情。

3、one-hot編碼

雖然獨熱碼多用了觸發器，但所用組合電路可省一些，因而使電路的速度和可靠性有顯著提高，而總的單元數並無顯著增加。同時獨熱碼在狀態躍遷時僅需要改變狀態變數的某一位，在一定程度上簡化了比較邏輯，從而減少了毛刺產生的機率。同時採用獨熱編碼後有了多餘的狀態，就有了一些不可達到的狀態。

為此，在case 語句的最後需要增加default 分支項。 one-hot編碼有很多變體。比如將 IDLE 狀態編碼為0，其他狀態按照正常的one-hot編碼。即對於除IDLE 外的每個給定狀態，對應的狀態向量只有一位置1，其他位置0。這種變體的好處是在復位時可簡單的將狀態向量的各個觸發器清 0。

另一種常見的變體稱為"almost one-hot" 編碼。假設狀態機有功能幾乎相同的兩組狀態（例如，處理對某設備的讀訪問和寫訪問），可以使用1 個狀態位來指示狀態機當前正處在兩組狀態中的哪一組，而剩下的狀態位採用普通的one-hot碼。因此要對給定狀態進行完整的解碼需要考察兩個狀態位。這種機制具有使用純one-hot編碼的大多數好處，但邏輯更小。 one-hot 狀態機有一個缺點，它的狀態每次發生跳轉，很多狀態位都會發生變化。首先，狀態機的輸出往往是由狀態位組合生成的。同時變化的狀態位越多，組合輸出穩定前所需的時間就越長，產生的毛刺就越多。如果該輸出不經同步就直接連線到暫存器的時鐘、使能、或鎖存器的使能等控制連線埠，將很容易導致數據的破壞（正統解決方案是加一級暫存器來同步狀態機的輸出，該方案可能會產生一個周期的延遲，而且如果該輸出穩定前所需的時間過長還是會違背暫存器的建立時間）。其次，對於有異步輸入的系統，在時鐘沿到來時有多個狀態位發生變化，即有多個暫存器可能受異步輸入的影響，使得亞穩態發生的機率有所增加，雖然這並不是one-hot編碼的問題，根本的解決方案還是避免異步輸入。