胡文欣

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

0 引言

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

通過(guò)查閱文獻(xiàn)，本文整理了有限狀態(tài)機(jī)在斷電區(qū)間數(shù)據(jù)快速提取、全自動(dòng)燙印設(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樹(shù)結(jié)構(gòu)的算法和基于字符串匹配的分詞算法，并合理利用有限狀態(tài)機(jī)匹配模型，實(shí)現(xiàn)斷電區(qū)間數(shù)據(jù)的快速提取。

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

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

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

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

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

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

模型運(yùn)行速度很快，可跳過(guò)前期訓(xùn)練或擬合，直接達(dá)到在短時(shí)間內(nèi)提取出大量數(shù)據(jù)特征信息的需求。因此，經(jīng)過(guò)上述算法和模型的運(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)化方式存儲(chǔ)。緊接著，在Python架構(gòu)的基礎(chǔ)上具體實(shí)現(xiàn)上述FSM模型，并對(duì)此模型進(jìn)行準(zhǔn)確率及運(yùn)行速度測(cè)試，然后采用典型評(píng)價(jià)指標(biāo)評(píng)價(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ū)動(dòng)的狀態(tài)轉(zhuǎn)換算法

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

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

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

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

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

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

圖2 輸出時(shí)序圖

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

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

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

3.1 可逆邏輯綜合算法

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

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

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

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

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

4.1 VHDL硬件描述語(yǔ)言

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

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

此類(lèi)可逆電路設(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í)鐘的有效脈沖信號(hào)到來(lái)時(shí)，Process REG，也就是時(shí)序進(jìn)程能夠?qū)⒋螒B(tài)信號(hào)的內(nèi)容傳遞給現(xiàn)態(tài)信號(hào)，而次態(tài)的內(nèi)容則由其他進(jìn)程的操作和運(yùn)行結(jié)果決定?，F(xiàn)態(tài)信號(hào)的狀態(tài)值，則能夠決定主控組合的進(jìn)程，也就是Process COM，依靠這個(gè)量進(jìn)入對(duì)應(yīng)的狀態(tài)，相應(yīng)的狀態(tài)值由外部控制信號(hào)賦予次態(tài)信號(hào)[4]。而且，外部控制信號(hào)功能很強(qiáng)大，相應(yīng)的輸出信號(hào)值也是由其控制的。鎖存器進(jìn)程Process LATCH在時(shí)鐘的有效跳變到來(lái)的基礎(chǔ)上也能被啟動(dòng)，它能夠鎖存主控組合進(jìn)程產(chǎn)生的次態(tài)信號(hào)，使得計(jì)數(shù)器的輸出始終保持穩(wěn)定。

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

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

根據(jù)以上分析，可以得到：VHDL語(yǔ)言能夠從根本上改變電路的設(shè)計(jì)模式，由傳統(tǒng)的硬件設(shè)計(jì)轉(zhuǎn)變?yōu)檐浖较虻脑O(shè)計(jì)。這種思路上的改變可以使得電路更為簡(jiǎn)便，便于電路的后期修改。同時(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所示，此處對(duì)比了可逆有限狀態(tài)機(jī)電路和基于FSM的可逆計(jì)數(shù)器電路的優(yōu)點(diǎn)，并總結(jié)了共同點(diǎn)和不同點(diǎn)，前者側(cè)重于構(gòu)造一個(gè)行為可逆的FSM，而后者側(cè)重于利用VHDL語(yǔ)言實(shí)現(xiàn)對(duì)應(yīng)的邏輯功能[8]。雖然兩者在設(shè)計(jì)過(guò)程中使用的方法有所不同，但是都簡(jiǎn)化了電路，也優(yōu)化了整個(gè)過(guò)程，為以后的可逆電路設(shè)計(jì)以及有限狀態(tài)機(jī)的應(yīng)用拓寬了思路，開(kāi)辟了新的途徑。

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