面向工程化教育的有限狀態(tài)機教學設計

王建民，賀訓軍，田曉華，梅金碩，曹一江

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

0 引言

從廣義上講，有限狀態(tài)機FSM(Finite State Machine)是一種思想方法，在軟件設計、自動控制等領域都得到了廣泛的應用。在數(shù)字電路設計領域，有限狀態(tài)機等同于時序邏輯電路。事實上，大部分數(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ù)字設計類課程的重要內(nèi)容，是學習的重點和難點［2，3］。

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

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

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

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

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

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

2.1 有限狀態(tài)機

在現(xiàn)代數(shù)字設計中，有限狀態(tài)機無處不在。例如，按鍵掃描過程可以采用有限狀態(tài)機思想描述。一個典型的按鍵掃描過程可以分為空閑狀態(tài)、消抖以及等待按鍵釋放三個狀態(tài)。進一步，一個按鍵命令解析過程也可以用有限狀態(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)機進行描述。

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

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

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

圖2 時序邏輯電路典型結構

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

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

算法狀態(tài)機圖類似于軟件設計中的流程圖，但兩者存在本質區(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)名一般標注在狀態(tài)框的左上角。通常情況下，ASM圖中只標出不等于默認值的輸出信號取值，如果在某個狀態(tài)下沒有明確指明輸出的取值，表示在該狀態(tài)下輸出信號取默認值。

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

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

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

圖4 算法狀態(tài)機圖及其對應的狀態(tài)轉換圖

3 有限狀態(tài)機的結構和描述方式

3.1 模板式的HDL描述

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

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

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

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

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

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

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

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

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

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

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

4 結語

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

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

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

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

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

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