楊宏亮，金炎勝，王剛毅

（1.穆棱卷煙廠，黑龍江穆棱157500; 2.哈爾濱工業(yè)大學(xué)電子與信息工程學(xué)院，黑龍江哈爾濱150001）

隨著EDA技術(shù)的不斷發(fā)展，F(xiàn)PGA在各個領(lǐng)域都得到了廣泛的應(yīng)用，而在這些FPGA應(yīng)用中，絕大部分都使用到狀態(tài)機的方法，狀態(tài)機對于每個各自的設(shè)計都起著至關(guān)重要的作用，一旦狀態(tài)機出現(xiàn)卡死，也就是出現(xiàn)了通常說的“狀態(tài)機跑飛”現(xiàn)象，整個設(shè)計將無法繼續(xù)工作。鑒于狀態(tài)機的設(shè)計的重要性，有必要對狀態(tài)機的安全性進行深入的研究。

本文的研究內(nèi)容如下：首先，從狀態(tài)機編碼討論狀態(tài)機出現(xiàn)卡死的可能性；然后，詳細(xì)分析狀態(tài)機“跑飛”現(xiàn)象的原因，并提供幾種解決狀態(tài)機“跑飛”問題的方法；最后，深入研究了EDA工具軟件Quartus II中“Safe State Machine”選項選中后對狀態(tài)機電路帶來的影響。

1 導(dǎo)致狀態(tài)機“跑飛”現(xiàn)象的原因分析

1.1 狀態(tài)機編碼問題

在對狀態(tài)機進行編碼的時候，總是不可避免地會出現(xiàn)大量的剩余狀態(tài)[1]，即未被定義的編碼組合，這些編碼組合由于在狀態(tài)機正常運行時是不需要出現(xiàn)的，所以通常被稱為非法狀態(tài)。

正是由于非法狀態(tài)的存在，為狀態(tài)機跑飛現(xiàn)象提供了可能性。

1.2 惡劣工作環(huán)境的影響

這個原因比較容易理解，如果最后的產(chǎn)品工作環(huán)境比較惡劣，比如工作在太空中，眾所周知，太空中存在著各種粒子，受輻射程度很高，F(xiàn)PGA中的存儲單元就有可能因為受到各種粒子的撞擊而改變其中存儲的值[1]。如果狀態(tài)機中的狀態(tài)存儲器中的一位突然改變了，那么狀態(tài)機就有可能進入到非法狀態(tài)。例如：一個3個工作狀態(tài)采用One-hot編碼的狀態(tài)機，其合法編碼組合為“001”，“010”，“100”。如果在狀態(tài)“001”時，突然其中一位受到影響而翻轉(zhuǎn)了，變成了“101”，現(xiàn)在顯然就進入了非法狀態(tài)，如果沒有相應(yīng)的補救措施，這個狀態(tài)機就會卡死。

1.3 狀態(tài)機中有異步輸入

也就是說狀態(tài)機如何跳轉(zhuǎn)不僅僅受當(dāng)前狀態(tài)的影響，還受異步輸入的控制。為方便分析，舉一個帶異步輸入實例，其狀態(tài)轉(zhuǎn)換圖如圖1所示。

圖1 一個簡單的狀態(tài)轉(zhuǎn)換圖Fig.1 A simple state transition diagram

根據(jù)這個轉(zhuǎn)換圖，很容易用狀態(tài)機來實現(xiàn)，下面是一個簡單的VHDL程序狀態(tài)機實現(xiàn)部分：

在上述代碼中，sidle，srun，send表示 ST1，ST2，ST3三個工作狀態(tài)，‘a(chǎn)’為異步輸入。用Quartus II對上面代碼進行綜合，可以得到狀態(tài)機部分電路如圖2所示。

圖2 綜合的狀態(tài)機電路圖Fig.2 Quartus II integrated circuit of state machine

從狀態(tài)轉(zhuǎn)換方程中可以看出有兩個觸發(fā)器次態(tài)跟異步輸入‘a(chǎn)’有關(guān)，分別為D1和D3。當(dāng)a發(fā)生變化時，D1和D3的值也會隨之發(fā)生相應(yīng)的改變。在時鐘clk上升沿到來時，如果輸入a穩(wěn)定保持不變，則D1，D2，D3這三個觸發(fā)器輸出也會穩(wěn)定，狀態(tài)機保持正常運行；但是如果a的值也剛好正在變化，情況就變得不可預(yù)測了。因為各個觸發(fā)器D端組合邏輯不盡相同，所以各個組合邏輯產(chǎn)生的延遲也不同。這樣，如果在同一時刻，a正在變化，由于延遲不同的緣故，各個觸發(fā)器所采集到的a的值也會有所不同，可能有的是‘1’，有的是‘0’，還有可能因觸發(fā)器建立保持時間不夠出現(xiàn)亞穩(wěn)態(tài)。假設(shè)D1觸發(fā)器采集到的a為1，而D3觸發(fā)器采集到的a為‘0’，那么D1和D3這兩個觸發(fā)器的輸出就肯定有一個是錯誤的，從而就有可能導(dǎo)致狀態(tài)機出現(xiàn)非法狀態(tài)而卡死。

2 解決的辦法

分析完導(dǎo)致狀態(tài)機跑飛現(xiàn)象的幾種原因，針對不同的原因我們可以提出不同的解決方案。問題的解決方案，總是有兩種類型：事先預(yù)防和事后補救。同樣，解決狀態(tài)機跑飛問題也是如此。

2.1 預(yù)防措施

事故的最好解決辦法一定是“防患于未然”，事故一旦發(fā)生，無論補救措施多么的及時，或多或少都會造成一些損失。狀態(tài)機跑飛現(xiàn)象也是如此，如果能預(yù)防狀態(tài)機進入非法狀態(tài)，或者減少狀態(tài)機進入非法狀態(tài)的可能性，無疑是一個好辦法。

2.1.1 選用合適的編碼方式

既然由于大量非法狀態(tài)的存在，為狀態(tài)機跑飛提供了可能性，那么減少這種可能性就是一個好的努力方向。對同一個狀態(tài)機來說，不用的編碼方式，其剩余狀態(tài)可能會不同。Binary編碼和One-hot編碼是最常用的兩種編碼方式。

對于Binary編碼來說，如果狀態(tài)數(shù)N正好是2的冪次，則不會出現(xiàn)非法狀態(tài)。然而剛好符合這種情況的時候很少。更一般的情形，如果用到的合法狀態(tài)數(shù)量為N，觸發(fā)器的數(shù)量n=[log2N]，由此非法狀態(tài)的數(shù)量M=2n-N。對于One-hot編碼來說，出現(xiàn)非法狀態(tài)是必然的結(jié)果。如果使用到的合法狀態(tài)數(shù)量為N，則設(shè)計狀態(tài)機所需的觸發(fā)器數(shù)量也為N，由此非法狀態(tài)的數(shù)量M=2n-N。假設(shè)同樣是6個狀態(tài)，用Binary編碼只有兩個非法狀態(tài)，而用One-hot進行編碼卻有58個非法狀態(tài)。正因為非法狀態(tài)的存在，為狀態(tài)機跑飛提供了可能，而非法狀態(tài)越多，可能性就越大，單就這一點可以得出：One-hot編碼的狀態(tài)機比Binary編碼的狀態(tài)機更容易跑飛，而且狀態(tài)機狀態(tài)數(shù)越多，這種趨勢越明顯。

然而，選用什么樣的編碼方式對狀態(tài)機進行編碼是一個綜合考慮的問題，而并不是說Binary編碼剩余狀態(tài)少就一定要用它對狀態(tài)機進行編碼。事實上，Quartus II的默認(rèn)編碼方式是One-hot編碼。

2.1.2 異步輸入同步化

這是針對狀態(tài)機有異步輸入的情況。異步輸入同步化是一個跨時鐘域的問題。對于1.3節(jié)中的狀態(tài)機，因為只是單比特的異步信號，可以通過“雙跳”技術(shù)來對其進行同步。

圖3 雙跳以及雙跳重新同步Fig.3 Double jump and double jump to re-sync

在圖3中b是第一個觸發(fā)器的輸出，a是第二個觸發(fā)器的輸出。理論上說，可以輸出準(zhǔn)穩(wěn)態(tài)信號，但是實際上準(zhǔn)穩(wěn)態(tài)信號會很快穩(wěn)定下來，不能一直維持其準(zhǔn)穩(wěn)態(tài)的狀態(tài)。所以第二個觸發(fā)器可用來防止其他電路發(fā)現(xiàn)這個準(zhǔn)穩(wěn)態(tài)信號?？梢钥吹揭肓穗p跳技術(shù)會對輸入a延遲1～2個時鐘周期，但是一般情況下一個外部事件觸發(fā)引起FPGA內(nèi)部一個動作的一個比特位可能發(fā)生的頻率很小，通常附加幾個納秒對邏輯將不構(gòu)成影響[2]。

2.2 事后容錯機制

有時候，雖然做了足夠的預(yù)防措施，但是也無法做到能消除一切隱患。事故發(fā)生了，就需要及時地采取行動進行補救以減少損失。比如由于惡劣的環(huán)境影響，狀態(tài)機已經(jīng)進入了非法狀態(tài)，這件事已經(jīng)發(fā)生了，要能在出現(xiàn)更大損失之前糾正狀態(tài)機的狀態(tài)，使其能夠自動地回到正常工作狀態(tài)。所謂“事后”是指狀態(tài)機進入了非法狀態(tài)后，而不是出現(xiàn)跑飛之后。

2.2.1 非法狀態(tài)的處理

正是由于大量非法狀態(tài)的存在，為狀態(tài)機跑飛現(xiàn)象提供了可能性，所以理論上如果對所有的非法狀態(tài)都進行邏輯控制，使能回來正常工作狀態(tài)上來，就能杜絕狀態(tài)機跑飛現(xiàn)象。

（1）方法一

假設(shè)一個狀態(tài)機正常用到的狀態(tài)為“st0”、“st1”、“st2”等3個，用的編碼方式是Binary,那么還剩余1個編碼組合，也就是說還剩下1個非法狀態(tài)。這1個非法狀態(tài)在正常狀態(tài)機運轉(zhuǎn)的時候用不到，但是現(xiàn)在在枚舉狀態(tài)時，也把這些列上：“undefined”。用VHDL語言表示如下：

定義部分：

實現(xiàn)部分：

這樣，即使?fàn)顟B(tài)機進入了非法狀態(tài)“undefined”，由于加入對這個狀態(tài)的處理，狀態(tài)機也會重新回到正常工作狀態(tài)。

這種方法對Binary編碼方式來說還可能有效，但是對于One-hot編碼來說，因為One-hot編碼的非法狀態(tài)太多了，編寫起來過于繁瑣，同樣是上面的例子，用One-hot來進行編碼，就會出現(xiàn)5個非法狀態(tài)。

（2）方法二

VHDL語法提供了另一種簡便的方法，如2.2節(jié)所述，利用others語句對未提到的狀態(tài)進行統(tǒng)一處理。參照2.2節(jié)中有關(guān)部分重新改寫如下：

在others時，state不一定必須指到st0，也可以指到別的狀態(tài)或者是特定的處理模塊。語法上這種方法很有效果，但是實際上會有所不同，例如Quartus、Synplify等EDA工具在綜合以上的代碼時，會自動忽視others這一行，并不生成相應(yīng)的電路。這種忽視是有意的，是對狀態(tài)機進行優(yōu)化的結(jié)果。在絕大多數(shù)情況下，狀態(tài)機不會進入到非法狀態(tài)，即使在極少數(shù)情況下狀態(tài)機進到非法狀態(tài)了，用以上的采用冗余方法綜合出來的電路所費得資源太多，所以許多EDA工具采取忽視這條語句的做法，而提供了另一條更有效的方法：“安全狀態(tài)機”。

如果想others這一句不被綜合掉，可以選擇自己手動對狀態(tài)機進行編碼而不采用聲明為狀態(tài)機的語法。這種編寫方法Quartus II無法識別出狀態(tài)機，自然也就無法對其進行優(yōu)化，others這一行就能綜合處正常的電路來。

圖4 一種自動恢復(fù)電路模式Fig.4 An automatic recovery circuit mode

一般情況下，這種恢復(fù)電路是通過加入組合邏輯來實現(xiàn)的。如圖4所示，為了能使?fàn)顟B(tài)機恢復(fù)正常，在觸發(fā)器的D端原組合邏輯的基礎(chǔ)上，增加了一些新的組合邏輯。這種電路雖然實現(xiàn)了自動恢復(fù)的功能，但是也增加了延遲?？赡軒硪恍┴?fù)面的影響，如可允許的最大時鐘頻率減小或者達(dá)不到觸發(fā)器建立保持時間等。可以考慮另一種方法：利用D觸發(fā)器的異步清零端來恢復(fù)。當(dāng)狀態(tài)機出現(xiàn)異常時，將每個觸發(fā)器的狀態(tài)清零。這種方式克服了前一種方法的增加延遲的缺點，但對狀態(tài)機的編碼有一定的要求。對所有的觸發(fā)器進行清零后，狀態(tài)機回到了全零狀態(tài)，所以全零狀態(tài)必須是一個合法的工作狀態(tài)。這就要求在對狀態(tài)機編碼時，注意必須要有一個狀態(tài)是全零。D觸發(fā)器除了有一個清零端外，還有一個置位端，為什么這里用清零而不用置位呢？這是因為許多FPGA中D觸發(fā)器沒有置位端，只有清零端，要實現(xiàn)置位，必須要加入其他邏輯，所以使用清零端是最高效的方法。

2.2.2 加入檢測模塊

采用檢測模塊來檢測狀態(tài)機是否進入非法狀態(tài)，如果檢測到了，就進行一個特殊操作使?fàn)顟B(tài)機轉(zhuǎn)入一個特定的狀態(tài)。以O(shè)ne-hot編碼為例：One-hot編碼方式有自己的特點,正常狀態(tài)只可能有一個觸發(fā)器的狀態(tài)為“1”,其余觸發(fā)器的狀態(tài)皆為“0”,即任何多于1個觸發(fā)器為“1”的狀態(tài)均為非法狀態(tài)。因此,可通過判斷是否在同一時刻有多個寄存器為“1”,若有,則啟動相關(guān)操作來恢復(fù)狀態(tài)機。

2.2.3 選用安全狀態(tài)機

采用EDA工具中安全狀態(tài)機?，F(xiàn)在EDA工具都提供這一功能。以Quartus II 8.1為例，進入界面后，選擇“Assignments-＞settings-＞Analysis&Synthesis settings-＞more settings”，找到“Safe State Machine”，將其設(shè)置為“ON”即可。

3 結(jié)論

（1）有剩余狀態(tài)的存在，為狀態(tài)機跑飛想象的出現(xiàn)提供了可能。剩余狀態(tài)的多少與編碼方式有關(guān)系，所以可以通過選擇合適的編碼方式來盡量減少這種可能性；

（2）在編寫程序階段，設(shè)計者對惡劣環(huán)境因素的影響是無能為力的。幸好經(jīng)常遇到的狀態(tài)機跑飛問題都是由異步輸入引起的，利用雙跳技術(shù)將異步輸入同步化即可消除這個因素；

（3）因為不可能徹底消除狀態(tài)機跑飛的可能性，所以事后容錯機制是必不可少的。本文列出了一些容錯方法，其中最簡單有效的就是選用安全狀態(tài)機；

（4）要想設(shè)計安全健壯，就必須努力減少狀態(tài)機進入非法狀態(tài)的可能。安全狀態(tài)機所謂的“安全”，并不是真正的安全，實際上只是容錯機制的一種。

[1]潘松,黃繼業(yè).EDA技術(shù)實用教程:VHDL版(第4版)[M].北京：科學(xué)出版社,2010.

[2]ALTERA CORPORATION.Quartus II Handbook,Version 1:Design and Synthesis[M].2009.

[3]克里茲,孟憲元.高級FPGA設(shè)計:結(jié)構(gòu)、實現(xiàn)也優(yōu)化[M].北京：機械工業(yè)出版社,2009.