基于有限狀態(tài)機的應(yīng)用綜述

胡文欣

（北方工業(yè)大學，北京 100144）

0 引言

有限狀態(tài)機一類應(yīng)用十分廣泛的數(shù)學模型，它不僅能夠高效地描述有限狀態(tài)，還能把這些狀態(tài)之間進行的行為清楚地描述出來。該數(shù)學模型被認為是一種描述與實現(xiàn)順序控制的有效工具，能夠高效地描述事件的邏輯順序。隨著現(xiàn)代信息科技的高速進步和發(fā)展，有限狀態(tài)機的研究和應(yīng)用范圍不斷拓寬，僅對有限狀態(tài)機本身進行研究和開發(fā)已無法滿足現(xiàn)代信息科技進步的需求。從現(xiàn)有研究成果的情況來看，有限狀態(tài)機已經(jīng)和多種不同領(lǐng)域的技術(shù)完美結(jié)合，廣泛地應(yīng)用于嵌入式編程、數(shù)字電路開發(fā)以及可見光通信等多個領(lǐng)域。面對社會的日益進步，如何讓有限狀態(tài)機更好地和其他領(lǐng)域結(jié)合，將其作用發(fā)揮到極致是值得攻克的一個挑戰(zhàn)。

通過查閱文獻，本文整理了有限狀態(tài)機在斷電區(qū)間數(shù)據(jù)快速提取、全自動燙印設(shè)備控制系統(tǒng)設(shè)計、基于FSM的可逆計數(shù)器電路和可逆有限狀態(tài)機電路方面的應(yīng)用。

1 FSM的斷電區(qū)間數(shù)據(jù)快速提取

在供電系統(tǒng)方面，既要滿足供電需求，又得保證供電安全[1]。于是，在發(fā)生故障時，斷電區(qū)間快速判斷則顯得格外重要。利用基于Trie樹結(jié)構(gòu)的算法和基于字符串匹配的分詞算法，并合理利用有限狀態(tài)機匹配模型，實現(xiàn)斷電區(qū)間數(shù)據(jù)的快速提取。

1.1 基于Trie樹結(jié)構(gòu)的算法

Trie樹是一類有序樹，用于自動處理與字符串匹配的數(shù)據(jù)結(jié)構(gòu)，并且它通常能夠快速地從一組字符串中自動尋找到某個字符串?？梢酝ㄟ^對詞圖的掃描來獲得所有可能的成詞，更進一步地，可以得到DAG，便于下一步的操作。在實現(xiàn)的過程中，不僅能夠?qū)⒆值渖梢粋€Trie樹，還可以得到每個一個詞出現(xiàn)的頻率，并且能夠找到一個基于單詞頻率的最佳切分。

1.2 基于字符串匹配的分詞算法

基于字符串的精確匹配、基于詞的理解以及基于統(tǒng)計學方面的分詞算法是現(xiàn)存的三類主要分詞算法[2]。使用者若想要成功匹配需要分析的漢字和詞典中的詞條串，基于字符串匹配的分詞算法是最佳選擇，若匹配成功，則表示準確識別出一個詞。據(jù)資料分析，第一種分詞算法在分詞效率和簡便性方面優(yōu)于其它兩類算法，更適合實際的操作。

1.3 有限狀態(tài)機匹配模型

當需要對斷電區(qū)間的相關(guān)數(shù)據(jù)加以利用和處理的時候，需要先對分詞進行預(yù)處理，之后再合理提取數(shù)據(jù)。起始和終止位置、倍率系數(shù)是斷電區(qū)間相關(guān)數(shù)據(jù)的三個重要元素。首先對斷電區(qū)間數(shù)據(jù)分割，處理成1+2模式，然后進行信息匹配。當提取信息時，需要把各個匹配步驟轉(zhuǎn)換成有限狀態(tài)機對應(yīng)的狀態(tài)，令匹配過程等效為狀態(tài)轉(zhuǎn)移過程，而要想實現(xiàn)由一個狀態(tài)轉(zhuǎn)移至另一個狀態(tài)，輸入量則至關(guān)重要。

模型運行速度很快，可跳過前期訓練或擬合，直接達到在短時間內(nèi)提取出大量數(shù)據(jù)特征信息的需求。因此，經(jīng)過上述算法和模型的運用，基于有限狀態(tài)機的斷電區(qū)間數(shù)據(jù)快速提取方法可以準確快速地完成斷電區(qū)間特征信息提取任務(wù)，節(jié)約時間和成本。

1.4 實驗結(jié)果分析

選取某段時間內(nèi)某地區(qū)高速鐵路供電故障數(shù)據(jù)，以結(jié)構(gòu)化方式存儲。緊接著，在Python架構(gòu)的基礎(chǔ)上具體實現(xiàn)上述FSM模型，并對此模型進行準確率及運行速度測試，然后采用典型評價指標評價結(jié)果。根據(jù)實驗可得：利用有限狀態(tài)機模型，得到斷電區(qū)間起始和終止位置準確率分別達到92.0%和79.0%，提取準確率則為91.5%。

2 FSM的燙印設(shè)備控制系統(tǒng)設(shè)計

2.1 基于變量配置驅(qū)動的狀態(tài)轉(zhuǎn)換算法

基于變量配置驅(qū)動的狀態(tài)轉(zhuǎn)換算法可用于設(shè)計燙印動作的邏輯控制，具體分為以下步驟：首先是將全自動燙印機各燙印動作間的邏輯關(guān)系抽象為狀態(tài)轉(zhuǎn)換圖，然后在T5L智能屏的用戶數(shù)據(jù)存儲空間規(guī)劃用于存儲燙印動作轉(zhuǎn)換圖信息的變量地址，之后就是配置鄰接鏈表，存儲狀態(tài)轉(zhuǎn)換圖的信息。上述步驟一一實現(xiàn)之后，便可以進行對T5L智能觸摸屏的處理，此時需要對其進行變量配置操作。

對T5L智能觸摸屏進行變量配置，首先需要確定全自動燙印機的工作模式，定義全自動燙印機的狀態(tài)信息，然后將用戶數(shù)據(jù)空間中的地址分為系統(tǒng)變量和曲線變量地址，以及存儲全自動燙印機的各項參數(shù)，之后在特定的條件下，確定燙印機實際運行時的狀態(tài)轉(zhuǎn)換過程。

2.2 基于Stateflow建立的全自動燙印機動作的邏輯時序控制模型

該模型共有3層，如圖1所示，輸入事件“E_on”、“E_off”分別模擬全自動燙印機控制系統(tǒng)的開機按鍵和關(guān)機按鍵；剩余的輸入事件分別模擬全自動燙印機控制系統(tǒng)中T5L智能屏上的按鍵，用于控制第1層的5個狀態(tài)的轉(zhuǎn)換。第1層中的5個狀態(tài)采用內(nèi)部轉(zhuǎn)換模式，不僅能夠降低Stateflow框圖的復(fù)雜程度和提高Stateflow的執(zhí)行效率，還能夠使生成的代碼變簡短。第2層含有6個功能模塊，細化這6個功能模塊的任務(wù)則由第3層來完成[3]。

圖1 全自動燙印機動作的邏輯時序控制模型

在設(shè)置全自動燙印機的5個工作模式的參數(shù)值均為1的基礎(chǔ)上，利用基于Stateflow搭建的燙印動作邏輯時序控制模型進行仿真分析，得到的輸出時序圖如圖2所示。

圖2 輸出時序圖

根據(jù)圖2的仿真結(jié)果可知，氣缸與伺服電機時序是正確的，并提高控制系統(tǒng)的可靠性。

綜上，基于FSM的全自動燙印設(shè)備控制系統(tǒng)設(shè)計方法不僅能提高開發(fā)效率，還能提高控制系統(tǒng)的穩(wěn)定性。它在提高配置和開發(fā)效率的同時，能夠?qū)崿F(xiàn)系統(tǒng)級變量配置，擁有巨大的應(yīng)用發(fā)揮空間。

3 可逆有限狀態(tài)機電路

3.1 可逆邏輯綜合算法

對于FSM行為得到的真值表，若要將其對應(yīng)的邏輯功能用可逆電路實現(xiàn)，可以選擇已有的可逆邏輯綜合算法。首先需要改寫功能函數(shù)，分布式改寫需要綜合的信息，然后根據(jù)所有改寫完的表達式和變量順序來生成節(jié)點，再對其進行組合，形成整個功能函數(shù)圖像。之后，在充分維持其函數(shù)的功能和其可逆電路性質(zhì)特征的必要前提下，最大程度地化簡圖像，最后將所有獲得節(jié)點的可逆電路進行級聯(lián)，使其都能夠同時實現(xiàn)相應(yīng)的函數(shù)功能。

利用此類算法來達到目的，可以有效避免根據(jù)原狀態(tài)機來求解逆狀態(tài)機的步驟，簡化綜合的過程。

3.2 基于可逆FSM的可逆時序電路綜合模型

首先借助現(xiàn)有的綜合工具對FSM進行狀態(tài)最小化和分配，把FSM的行為描述成輸入為{輸入，現(xiàn)態(tài)}，輸出為{輸出，次態(tài)}的真值表模式。具體對應(yīng)的邏輯功能則需要在可逆組合電路的基礎(chǔ)上實現(xiàn)，結(jié)合現(xiàn)有的可逆邏輯綜合算法，完成電路與邏輯功能的匹配對應(yīng)。以三位右移電路的設(shè)計為例，首先根據(jù)移位寄存器的規(guī)則列出移位寄存電路的真值表，根據(jù)真值表得到次態(tài)方程和輸出方程，結(jié)合可逆FSM的結(jié)構(gòu)即可得到符合要求的可逆時序電路。由此例可得，基于可逆 FSM 的可逆時序電路綜合模型能夠更加優(yōu)化整個設(shè)計過程。在此綜合模型的整體架構(gòu)的基礎(chǔ)上，得到的可逆FSM電路結(jié)構(gòu)如圖3所示。由圖中反饋的信息可知，虛線框中的電路能夠?qū)崿F(xiàn)第i個狀態(tài)編碼Si的采樣和鎖存。若可逆FSM系統(tǒng)有u位狀態(tài)編碼，則有u個虛線框中的電路結(jié)構(gòu)。

圖3 可逆FSM電路結(jié)構(gòu)圖

若M=0，C=0，則輸出如公式（2）所示：

利用可逆FSM電路結(jié)構(gòu)實現(xiàn)可逆時序電路的綜合方法，可避免求解原狀態(tài)機的逆狀態(tài)機這個繁瑣的環(huán)節(jié)，使得整個綜合過程更為簡便優(yōu)化。

4 基于FSM的可逆計數(shù)器電路

4.1 VHDL硬件描述語言

VHDL語言是應(yīng)用于電子設(shè)計領(lǐng)域中的常用語言，它不受具體地硬件和軟件控制平臺的影響，支持多種設(shè)計模式，如：自頂向下、自底向上等。其中自頂向下的設(shè)計方法不僅能夠讓系統(tǒng)在早期設(shè)計時，便可以檢測功能是否可行，還能隨時仿真模擬。利用VHDL語言，設(shè)計者根據(jù)狀態(tài)轉(zhuǎn)移圖，則能夠直接描述狀態(tài)機，避免繁雜的過程，而且用VHDL語言編寫的程序?qū)哟畏置鳎瑮l理清楚。

4.2 基于有限狀態(tài)機的可逆電路設(shè)計模型

此類可逆電路設(shè)計模型能夠高效地用于同步模4的可逆計數(shù)器的設(shè)置。從狀態(tài)遷移的特點中可以看出，實現(xiàn)何種計數(shù)功能與外部輸入的大小有關(guān)。當輸入值為0時，在時鐘脈沖的基礎(chǔ)上能夠?qū)崿F(xiàn)加法計數(shù)；同樣地，減法計數(shù)功能則在輸入值為1地基礎(chǔ)上實現(xiàn)[6-7]。在有限狀態(tài)機的原理和功能實現(xiàn)基礎(chǔ)上，設(shè)計出的狀態(tài)機的工作結(jié)構(gòu)如圖4所示。當時鐘的有效脈沖信號到來時，Process REG，也就是時序進程能夠?qū)⒋螒B(tài)信號的內(nèi)容傳遞給現(xiàn)態(tài)信號，而次態(tài)的內(nèi)容則由其他進程的操作和運行結(jié)果決定?，F(xiàn)態(tài)信號的狀態(tài)值，則能夠決定主控組合的進程，也就是Process COM，依靠這個量進入對應(yīng)的狀態(tài)，相應(yīng)的狀態(tài)值由外部控制信號賦予次態(tài)信號[4]。而且，外部控制信號功能很強大，相應(yīng)的輸出信號值也是由其控制的。鎖存器進程Process LATCH在時鐘的有效跳變到來的基礎(chǔ)上也能被啟動，它能夠鎖存主控組合進程產(chǎn)生的次態(tài)信號，使得計數(shù)器的輸出始終保持穩(wěn)定。

圖4 狀態(tài)機結(jié)構(gòu)工作示意圖

根據(jù)可逆計數(shù)器的一些設(shè)計基本原理[5]，再結(jié)合VHDL語言，首先設(shè)計一個對應(yīng)的程序，之后在MAX+plusII軟件中進行多次仿真，得到仿真結(jié)果，也就是對應(yīng)的波形。

根據(jù)以上分析，可以得到：VHDL語言能夠從根本上改變電路的設(shè)計模式，由傳統(tǒng)的硬件設(shè)計轉(zhuǎn)變?yōu)檐浖较虻脑O(shè)計。這種思路上的改變可以使得電路更為簡便，便于電路的后期修改。同時，有限狀態(tài)機的運用能夠很好地實現(xiàn)高效率高可靠性的邏輯控制，使得可逆計數(shù)器電路的性能得到大大提升?？赡媸接嫈?shù)器電路在利用有限狀態(tài)機設(shè)計的基礎(chǔ)上可以有效地消除在計數(shù)器中頻繁出現(xiàn)的時序性毛刺。

5 結(jié)論

如表1所示，此處對比了可逆有限狀態(tài)機電路和基于FSM的可逆計數(shù)器電路的優(yōu)點，并總結(jié)了共同點和不同點，前者側(cè)重于構(gòu)造一個行為可逆的FSM，而后者側(cè)重于利用VHDL語言實現(xiàn)對應(yīng)的邏輯功能[8]。雖然兩者在設(shè)計過程中使用的方法有所不同，但是都簡化了電路，也優(yōu)化了整個過程，為以后的可逆電路設(shè)計以及有限狀態(tài)機的應(yīng)用拓寬了思路，開辟了新的途徑。

表1 基于有限狀態(tài)機的兩種電路設(shè)計方案對比