王建民，賀訓(xùn)軍，田曉華，梅金碩，曹一江

(哈爾濱理工大學(xué)電子科學(xué)與技術(shù)系，黑龍江哈爾濱 150080)

0 引言

從廣義上講，有限狀態(tài)機FSM(Finite State Machine)是一種思想方法，在軟件設(shè)計、自動控制等領(lǐng)域都得到了廣泛的應(yīng)用。在數(shù)字電路設(shè)計領(lǐng)域，有限狀態(tài)機等同于時序邏輯電路。事實上，大部分?jǐn)?shù)字系統(tǒng)都可以劃分為控制單元和數(shù)據(jù)通道兩個組成部分?？刂茊卧ǔ６际遣捎糜邢逘顟B(tài)機實現(xiàn)，其作用是接受外部信號以及數(shù)據(jù)通道的狀態(tài)信息，并據(jù)此產(chǎn)生控制信號，協(xié)調(diào)整個系統(tǒng)的工作，即有限狀態(tài)機是數(shù)字系統(tǒng)的核心部分［1］。因此，有限狀態(tài)機設(shè)計一直都是“硬件描述語言”等數(shù)字設(shè)計類課程的重要內(nèi)容，是學(xué)習(xí)的重點和難點［2，3］。

筆者在我院開設(shè)“硬件描述語言”HDL課程的過程中逐漸發(fā)現(xiàn)，當(dāng)前該課程教學(xué)無論是教學(xué)內(nèi)容還是教學(xué)理念和方法，都無法適應(yīng)業(yè)界對數(shù)字設(shè)計人員的能力需求，更無法滿足當(dāng)前工程人才培養(yǎng)的要求。一方面，當(dāng)前有限狀態(tài)機教學(xué)重點關(guān)注HDL描述的代碼風(fēng)格、寄存器傳輸級 RTL(Register Transfer Level)的設(shè)計方法和技巧(流水線設(shè)計和資源共享等)、狀態(tài)賦值和電路優(yōu)化等內(nèi)容，設(shè)計的起點是狀態(tài)轉(zhuǎn)換圖STG(State Transition Graphics)或者算法狀態(tài)機 ASM(Algorithm State Machine)。另一方面，以狀態(tài)轉(zhuǎn)換圖作為設(shè)計起點的數(shù)字電路設(shè)計任務(wù)，已發(fā)展到只需作一些機械性工作:設(shè)計人員只需選擇合適的代碼風(fēng)格(2段式或多段式)對有限狀態(tài)機進(jìn)行描述，編寫合適設(shè)計約束文件，EDA軟件一般就能夠給出符合設(shè)計要求的電路實現(xiàn)。然而，對于實際設(shè)計任務(wù)而言，其起點往往不是狀態(tài)轉(zhuǎn)換圖，而是用戶提出的各類設(shè)計任務(wù)。設(shè)計人員需要經(jīng)過一系列的理解、消化和邏輯抽象過程，建立描述該設(shè)計任務(wù)的有限狀態(tài)機模型，采用合適的方法對模型進(jìn)行描述。這些內(nèi)容的學(xué)習(xí)和訓(xùn)練對于學(xué)生分析解決問題的能力以及創(chuàng)新能力的培養(yǎng)都至關(guān)重要。但是，這部分內(nèi)容在目前教學(xué)實踐中沒有受到足夠重視，體現(xiàn)不多。

筆者通過拓展教學(xué)內(nèi)容(將教學(xué)內(nèi)容起點擴展至實際的設(shè)計任務(wù))，引入算法狀態(tài)機圖對復(fù)雜設(shè)計進(jìn)行描述，采用標(biāo)準(zhǔn)HDL模板對有限狀態(tài)機進(jìn)行描述等手段，形成了一套完整的問題驅(qū)動的有限狀態(tài)機教學(xué)體系，在實踐中取得良好教學(xué)效果。

1 問題驅(qū)動的有限狀態(tài)機教學(xué)

筆者提出的問題驅(qū)動的教學(xué)體系是一切教學(xué)內(nèi)容的安排以解決實際問題為目標(biāo)，明確學(xué)生的學(xué)習(xí)目的，并將該思想貫徹教學(xué)內(nèi)容的始終。該教學(xué)體系和學(xué)生能力培養(yǎng)的關(guān)系，如圖1所示。

圖1 有限狀態(tài)機教學(xué)體系培養(yǎng)

2 有限狀態(tài)機和算法狀態(tài)機圖

2.1 有限狀態(tài)機

在現(xiàn)代數(shù)字設(shè)計中，有限狀態(tài)機無處不在。例如，按鍵掃描過程可以采用有限狀態(tài)機思想描述。一個典型的按鍵掃描過程可以分為空閑狀態(tài)、消抖以及等待按鍵釋放三個狀態(tài)。進(jìn)一步，一個按鍵命令解析過程也可以用有限狀態(tài)機描述。在A狀態(tài)下，觸發(fā)一個按鍵后切換到了B狀態(tài)，在B狀態(tài)如果再觸發(fā)另一個鍵后切換到C狀態(tài)，或者返回到A狀態(tài)，這是最簡單的按鍵狀態(tài)機例子。類似地，SRAM讀寫時序也可以抽象成有限個狀態(tài)，采用有限狀態(tài)機進(jìn)行描述。

事實上，有限狀態(tài)機的本質(zhì)就是對具有邏輯順序或時序規(guī)律事件的一種描述方法。狀態(tài)機由各個狀態(tài)組成，各個狀態(tài)由狀態(tài)轉(zhuǎn)移連接在一起。狀態(tài)是執(zhí)行某項活動或者等待某個事件的條件。轉(zhuǎn)移是兩個狀態(tài)之間的關(guān)系，由某個事件觸發(fā)，然后執(zhí)行特定的操作或評估并導(dǎo)致特定的狀態(tài)結(jié)束。此外，狀態(tài)轉(zhuǎn)移還必須具有某種時序規(guī)律。

時序邏輯電路就是有限狀態(tài)機(在不至于發(fā)生混淆的情況，本文將時序邏輯電路直接稱為有限狀態(tài)機)，圖2所示為典型的時序邏輯電路結(jié)構(gòu)。電路的每一個狀態(tài)包含三個要素:當(dāng)前狀態(tài)、次態(tài)和輸出邏輯。次態(tài)邏輯是當(dāng)前狀態(tài)和輸入的函數(shù)，是組合邏輯電路。狀態(tài)寄存器是由多個D觸發(fā)器組成的寄存器組，用于記錄時序邏輯電路的當(dāng)前狀態(tài)，寄存器組中的所有D觸發(fā)器使用相同的時鐘信號(同步時序邏輯)。輸出邏輯也是組合邏輯電路，用來決定電路的輸出。電路的輸出可能只有電路的狀態(tài)決定，這種類型的輸出稱為摩爾類型的輸出。如果電路的輸出由電路的輸入和電路的狀態(tài)共同決定則稱為米利型的輸出。

除了上述三個要素外，時序規(guī)律也是有限狀態(tài)機必須要考慮的要素，有限狀態(tài)機的狀態(tài)轉(zhuǎn)移必須按照一定的時序規(guī)律進(jìn)行。例如，時序邏輯電路的狀態(tài)轉(zhuǎn)移就是在系統(tǒng)時鐘的統(tǒng)一控制下完成的，每個時鐘周期時序電路都會切換一個狀態(tài)。

圖2 時序邏輯電路典型結(jié)構(gòu)

2.2 算法狀態(tài)機圖

與狀態(tài)轉(zhuǎn)換圖STG一樣，算法狀態(tài)機圖ASM也是一種有限狀態(tài)機的圖形化的表示方法，對于相對復(fù)雜的設(shè)計，算法狀態(tài)機圖比狀態(tài)轉(zhuǎn)換圖更具優(yōu)勢，因而在工程實踐中應(yīng)用廣泛［4，5］。在國外，“硬件描述語言”課程中較多采用算法狀態(tài)機圖作為基本工具，而在國內(nèi)教學(xué)中，算法狀態(tài)機圖還未得到足夠的重視。本節(jié)介紹算法狀態(tài)機圖的畫法和應(yīng)用。

算法狀態(tài)機圖類似于軟件設(shè)計中的流程圖，但兩者存在本質(zhì)區(qū)別。ASM圖由若干ASM塊組成。每個ASM塊包含一個狀態(tài)框以及一個可選的條件判斷框和條件輸出框，典型的ASM塊如圖3所示。

圖3 典型算法狀態(tài)機ASM塊

狀態(tài)框表示有限狀態(tài)機FSM的狀態(tài)，用矩形表示。摩爾類型的輸出直接列于狀態(tài)框內(nèi)部，狀態(tài)名一般標(biāo)注在狀態(tài)框的左上角。通常情況下，ASM圖中只標(biāo)出不等于默認(rèn)值的輸出信號取值，如果在某個狀態(tài)下沒有明確指明輸出的取值，表示在該狀態(tài)下輸出信號取默認(rèn)值。

條件判斷框用菱形表示，其包含關(guān)于輸入信號的邏輯表達(dá)式(狀態(tài)轉(zhuǎn)換條件)，邏輯表達(dá)式取值確定FSM離開該ASM塊的路徑。條件判斷框可以包含復(fù)雜程度不同的狀態(tài)轉(zhuǎn)換條件，根據(jù)狀態(tài)轉(zhuǎn)換表達(dá)式取值不同，F(xiàn)SM按照true路徑或者false路徑切換至相應(yīng)的次態(tài)(另一個ASM塊)。

條件輸出框用圓角矩形表示，其內(nèi)部只列出非默認(rèn)取值的輸出信號。需要強調(diào)的是，條件輸出框只能放在條件判斷框之后，表示當(dāng)條件判斷框中的邏輯表達(dá)式為真時，相應(yīng)的輸出信號才會有效。因為條件判斷框的邏輯表達(dá)式是關(guān)于輸入信號的，說明輸出依賴于當(dāng)前狀態(tài)和輸入信號。通常也只有在輸出信號置位時，才會將其列入條件輸出框。如果沒有條件輸出框，表示輸出信號取默認(rèn)值。

算法狀態(tài)機圖由多個ASM塊組成，每個ASM塊代表有限狀態(tài)機的一個狀態(tài)，根據(jù)條件判斷結(jié)果，在時鐘控制下，實現(xiàn)在不同狀態(tài)之間的轉(zhuǎn)移。圖4給出一個典型的算法狀態(tài)機圖，為了對比同時給出其對應(yīng)的狀態(tài)轉(zhuǎn)換圖。

圖4 算法狀態(tài)機圖及其對應(yīng)的狀態(tài)轉(zhuǎn)換圖

3 有限狀態(tài)機的結(jié)構(gòu)和描述方式

3.1 模板式的HDL描述

有限狀態(tài)機的HDL代碼描述風(fēng)格至關(guān)重要，良好的代碼風(fēng)格有助于提高代碼的可讀性和可維護(hù)性，更有助于綜合軟件給出符合設(shè)計意圖的綜合結(jié)果。相反，不良的代碼風(fēng)格可能導(dǎo)致綜合軟件給出復(fù)雜的甚至是不正確的綜合結(jié)果。

因此，筆者建議在教學(xué)實踐中，采用模板式的代碼描述方式對表示成狀態(tài)轉(zhuǎn)換圖或算法狀態(tài)機圖的有限狀態(tài)機進(jìn)行描述，具體的描述方式如圖5所示。

圖5 有限狀態(tài)機的模板式Verilog HDL描述

此外，以Verilog HDL為例，如果采用VHDL也有類似的描述方式。模板式HDL描述方式的關(guān)鍵是將組合邏輯和時序邏輯分開，并分別采用always塊對次態(tài)邏輯、輸出邏輯和狀態(tài)寄存器進(jìn)行描述。因此，這種描述方式也稱為多段式描述方式［4，5］。

除了圖5給出的多段式描述方式外，2段式也是常用的描述方法。這種描述方法與多段式類似，同樣需要將狀態(tài)寄存器和組合邏輯分開描述，其區(qū)別在于多段式描述將次態(tài)邏輯和輸出邏輯獨立采用always塊實現(xiàn)，2段式描述將次態(tài)邏輯、輸出邏輯統(tǒng)一采用一個always塊描述，對于某些不是特別復(fù)雜的設(shè)計，2段式描述能有效減少代碼量。教學(xué)中，我們應(yīng)盡量避免采用1段式描述。

3.2 狀態(tài)賦值和未用狀態(tài)的處理

狀態(tài)賦值也稱為狀態(tài)編碼，狀態(tài)編碼類型對有限狀態(tài)機有顯著的影響，狀態(tài)編碼方案選取得當(dāng)，有限狀態(tài)機狀態(tài)譯碼電路會很簡單;反之，可能會產(chǎn)生過于復(fù)雜的譯碼邏輯，導(dǎo)致消耗過多的邏輯資源。目前，常用的狀態(tài)編碼方式有二進(jìn)制編碼、格雷編碼和獨熱編碼(one-hot coding)等。

隨著綜合理論和技術(shù)的進(jìn)步，采用HDL描述有限狀態(tài)機時，筆者建議直接使用符號常量。綜合軟件會自動根據(jù)設(shè)計約束選擇合適的狀態(tài)賦值方案(一般會從前面介紹的幾種狀態(tài)賦值方案中選擇1種)，以得到滿足設(shè)計約束的最優(yōu)電路。

采用符號常量表示狀態(tài)時，通常會存在某些狀態(tài)未被使用的情況。對于未被使用的狀態(tài)一般會有兩種處理方式:①將未用狀態(tài)處理成“錯誤狀態(tài)”，一旦進(jìn)入“錯誤狀態(tài)”，狀態(tài)機采用統(tǒng)一的錯誤處理機制進(jìn)行處理。②將未用狀態(tài)處理為“don't care”，認(rèn)為有限狀態(tài)機不會進(jìn)入這些狀態(tài)，按照面積或速度最優(yōu)原則進(jìn)行優(yōu)化。然而，一旦由于某種干擾或者其它情況，有限狀態(tài)機進(jìn)入了這些未用狀態(tài)，就會導(dǎo)致整個系統(tǒng)無法正常工作。

3.3 “面積”和“速度”的折衷

“面積”和“速度”的折衷與平衡是數(shù)字系統(tǒng)設(shè)計的永恒話題，在數(shù)字電路設(shè)計的各個層次存在不同的方法和策略對二者進(jìn)行平衡?！坝布枋稣Z言”課程的教學(xué)中，主要強調(diào)在電路結(jié)構(gòu)層次如何影響電路“面積”和“速度”。核心的教學(xué)內(nèi)容包括:流水線設(shè)計思想(通過提高或者降低電路的并行性改進(jìn)電路的“面積”或者“速度”優(yōu)勢)、復(fù)位電路設(shè)計等內(nèi)容［4］。

4 結(jié)語

本文提出一種貼近工程實踐的問題驅(qū)動有限狀態(tài)機教學(xué)體系，目的是訓(xùn)練和培養(yǎng)學(xué)生分析問題和解決實際工程問題的能力，培養(yǎng)合格的工程化人才。這套教學(xué)體系在實際教學(xué)過程中，已經(jīng)運行了一段時間，得到學(xué)生的好評，教學(xué)效果良好。

［1］ 夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計教程(第2版)［M］.北京:北京航空航天大學(xué)出版社，2003.7

［2］ 周暉，蔣華等.“硬件描述語言”課程的教學(xué)改革探索［J］.南寧:高教論壇，2008，(6):184-186

［3］ 謝躍雷，偉雪明.“數(shù)字系統(tǒng)設(shè)計基礎(chǔ)”教學(xué)探索與研究［J］.南京:電氣電子教學(xué)學(xué)報，2007，29(3):23-25

［4］ 王建民，田曉華，江曉林.Verilog HDL數(shù)字系統(tǒng)設(shè)計［M］.哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2011.6

［5］ Pong P.Chu.FPGA Prototyping by Verilog Examples［M］.New Jersey:A John Wiley ＆ Sons，Inc.Publication，2008.3