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

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

0 引言

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

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

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

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

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

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

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

2.1 有限狀態(tài)機(jī)

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

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

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

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

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

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

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

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

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

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

條件判斷框用菱形表示，其包含關(guān)于輸入信號(hào)的邏輯表達(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)(另一個(gè)ASM塊)。

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

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

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

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

3.1 模板式的HDL描述

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

［4］ 王建民，田曉華，江曉林.Verilog HDL數(shù)字系統(tǒng)設(shè)計(jì)［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