胡文欣

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

1.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

2.2 基于Stateflow建立的全自動燙印機(jī)動作的邏輯時(shí)序控制模型

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

圖1 全自動燙印機(jī)動作的邏輯時(shí)序控制模型

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

圖2 輸出時(shí)序圖

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

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

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

3.1 可逆邏輯綜合算法

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

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

3.2 基于可逆FSM的可逆時(shí)序電路綜合模型

首先借助現(xiàn)有的綜合工具對FSM進(jìn)行狀態(tài)最小化和分配，把FSM的行為描述成輸入為{輸入，現(xiàn)態(tài)}，輸出為{輸出，次態(tài)}的真值表模式。具體對應(yīng)的邏輯功能則需要在可逆組合電路的基礎(chǔ)上實(shí)現(xiàn)，結(jié)合現(xiàn)有的可逆邏輯綜合算法，完成電路與邏輯功能的匹配對應(yīng)。以三位右移電路的設(shè)計(jì)為例，首先根據(jù)移位寄存器的規(guī)則列出移位寄存電路的真值表，根據(jù)真值表得到次態(tài)方程和輸出方程，結(jié)合可逆FSM的結(jié)構(gòu)即可得到符合要求的可逆時(shí)序電路。由此例可得，基于可逆 FSM 的可逆時(shí)序電路綜合模型能夠更加優(yōu)化整個設(shè)計(jì)過程。在此綜合模型的整體架構(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)實(shí)現(xiàn)可逆時(shí)序電路的綜合方法，可避免求解原狀態(tài)機(jī)的逆狀態(tài)機(jī)這個繁瑣的環(huán)節(jié)，使得整個綜合過程更為簡便優(yōu)化。

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

4.1 VHDL硬件描述語言

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

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

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

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

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

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

5 結(jié)論

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

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