有限狀態(tài)機在FPGA硬件實驗中的應(yīng)用

馮 建 文

(杭州電子科技大學 計算機學院，杭州 310018)

有限狀態(tài)機在FPGA硬件實驗中的應(yīng)用

馮 建 文

(杭州電子科技大學 計算機學院，杭州 310018)

有限狀態(tài)機(FSM)是描述與實現(xiàn)順序控制的有效工具，廣泛應(yīng)用于計算機、數(shù)字系統(tǒng)和工業(yè)自動化領(lǐng)域。介紹了FSM的概念、原理與設(shè)計步驟，闡述了使用FSM實現(xiàn)按鍵消抖實驗、串行通信實驗和多周期CPU實驗的原理和具體方法。將FSM應(yīng)用于FPGA硬件實驗中，使學生能夠理解FSM的原理，并掌握其設(shè)計方法，取得了較好的實驗教學效果。

有限狀態(tài)機； 現(xiàn)場可編程門陣列； 硬件實驗； 按鍵消抖； 串行通信； 多周期CPU

0 引 言

有限狀態(tài)機(Finite State Machine，F(xiàn)SM)是描述有限個狀態(tài)以及在這些狀態(tài)之間進行轉(zhuǎn)移和動作等行為的數(shù)學模型[1]。它廣泛應(yīng)用于自動化、數(shù)字系統(tǒng)、計算機系統(tǒng)等領(lǐng)域，譬如PLC控制器的順序控制功能、CPU的指令執(zhí)行控制等，均是FSM的典型應(yīng)用范例。因此，對于高等院校工科學生而言，掌握FSM的原理與設(shè)計方法非常重要。隨著EDA技術(shù)的發(fā)展，F(xiàn)PGA器件逐步成為最廣泛的硬件實驗平臺[2]。如何將FSM應(yīng)用與融合在基于FPGA的硬件實驗中，是一個非常現(xiàn)實而又有意義的課題。FSM實際上是一種描述與解決問題的模型工具，因此，其實驗必定是基于某種應(yīng)用背景而設(shè)計的。遵循實用、易于掌握、循序漸進的原則，針對高校計算機大類專業(yè)本科生，本文設(shè)計了3個基于FSM的FPGA實驗，取得了較好的實驗效果。

1 有限狀態(tài)機概述

FSM包含了一組有限的狀態(tài)量和2個函數(shù)：下一狀態(tài)函數(shù)和輸出函數(shù)[3]，如圖1所示。圖中：rst信號用于確定有限狀態(tài)機的初始狀態(tài)(S0)和原始輸出；clk用于同步狀態(tài)轉(zhuǎn)換的邊沿或者定時狀態(tài)轉(zhuǎn)換的周期。狀態(tài)集包含可能出現(xiàn)在中間過程中的所有狀態(tài)量，使用觸發(fā)器保存。下一狀態(tài)函數(shù)則是通過輸入變量和當前狀態(tài)確定轉(zhuǎn)移到下一狀態(tài)的組合邏輯函數(shù)。輸出函數(shù)根據(jù)當前狀態(tài)和輸入變量產(chǎn)生電路的一組輸出變量。與普通的時序邏輯函數(shù)一樣，如果輸出函數(shù)僅僅依賴于當前狀態(tài)，則稱該有限狀態(tài)機為Moore型狀態(tài)機；如果輸出函數(shù)不僅依賴于當前狀態(tài)，也依賴于當前輸入，則稱該有限狀態(tài)機為Mealy型狀態(tài)機[4]。

圖1 有限狀態(tài)機結(jié)構(gòu)圖

用硬件描述語言(HDL)描述的FPGA電路大都是并行實現(xiàn)，但是對于實際工程應(yīng)用，往往需要讓硬件來實現(xiàn)一些具有一定順序邏輯的工作。而FSM就是通過不同的狀態(tài)遷移來完成一些特定的順序邏輯[5]。因此，F(xiàn)SM是FPGA數(shù)字系統(tǒng)設(shè)計的重要工具與精髓所在[6]。

基于FPGA的FSM的設(shè)計步驟如下[5-6]：

(1) 進行邏輯分析與抽象，確定輸入、輸出與狀態(tài)變量，畫出狀態(tài)轉(zhuǎn)移圖；

(2) 狀態(tài)簡化，得到最簡的狀態(tài)轉(zhuǎn)移圖；

(3) 對狀態(tài)進行編碼。可選擇binary、gray、one-hot編碼方式之一，在FPGA的開發(fā)綜合平臺和綜合工具中，可以進行選擇或者自定義[7-8]；

(4) 用HDL描述，并綜合、仿真與實現(xiàn)：描述方式有一段式、二段式和三段式三種方式[7-8]。

2 有限狀態(tài)機的實驗應(yīng)用設(shè)計

有限狀態(tài)機作為一種實現(xiàn)順序控制與定時的手段，其實驗設(shè)計應(yīng)與具體的實驗目標相結(jié)合。因此，在計算機科學與技術(shù)專業(yè)的硬件課程實驗改革中，設(shè)計了3個難度遞增的硬件實驗，在不同的本體應(yīng)用背景中，使學生逐步掌握FSM的原理與設(shè)計方法。表1描述了3個應(yīng)用實驗的本體實驗目的與FSM實驗目標。

2.1 按鍵消抖實驗的有限狀態(tài)機設(shè)計

實驗原理如圖2所示[9]。將按鍵信號key作為輸入，經(jīng)過消抖后，產(chǎn)生一個單脈沖信號pulse。按鍵按下為高電平，松開為低電平。雖然按鍵消抖方法很多，但是實驗要求使用FSM實現(xiàn)一種更可靠的按鍵消抖方法。

分析按鍵按下到松開的整個過程，將其分為6個狀態(tài)，如圖3所示。

表1 有限狀態(tài)機實驗設(shè)計

圖2 按鍵消抖實驗示意圖

圖3 按鍵狀態(tài)分析

分析狀態(tài)變化的條件和輸出，可以畫出FSM的狀態(tài)轉(zhuǎn)移圖，如圖4所示。

圖4 按鍵消抖FSM狀態(tài)轉(zhuǎn)移圖

從圖4可知，該FSM屬于Mealy型，按照一段式描述方式，Verilog HDL程序如下：

module Key_OK(input rst, //復位

input clk, //時鐘源

input key, //按鍵

output regpulse //輸出單脈沖

);

parameter S0=3'd0,S1=3'd1,S2=3'd2,S3=3'd3,S4=3'd4,

S5=3'd5;//狀態(tài)集定義

reg[2:0] ST;//當前狀態(tài)

always @(posedgerst or posedgeclk)//一段:狀態(tài)轉(zhuǎn)換與輸出

函數(shù)

begin

if (rst) begin//初始狀態(tài)賦值

ST<=key?S3:S0; pulse<=key;

endelse

case (ST)

S0:begin ST<=key?S1:S0; pulse<=1'b0; end

S1: begin ST<=key?S3:S2; pulse<=key; end

S2: begin ST<=key?S1:S0; pulse<=1'b0; end

S3: begin ST<=key?S3:S4; pulse<=1'b1; end

S4: begin ST<=key?S5:S0; pulse<=key; end

S5: begin ST<=key?S3:S4; pulse<=1'b1; end

default: begin ST<=key?S3:S0; pulse<=1'b0; end

endcase

end;

endmodule

實驗的時鐘clk由實驗板卡的系統(tǒng)時鐘源100 MHz分頻產(chǎn)生，可將周期調(diào)節(jié)在1 ms左右。

在完成了這個邏輯簡單的按鍵消抖實驗后，引導學生思考并嘗試實現(xiàn)：如何將其變成二段式FSM？該FSM能否轉(zhuǎn)變成Moore型FSM？從而真正理解FSM的基本概念與基本設(shè)計方法。

二段式、Moore型FSM的按鍵消抖核心程序如下：

always @(posedgerst or posedgeclk)//一段:狀態(tài)轉(zhuǎn)換

begin

if (rst)//初始狀態(tài)賦值

ST<=key?S3:S0;

else

case (ST)

S0: ST<=key?S1:S0;

S1: ST<=key?S3:S2;

S2: ST<=key?S1:S0;

S3: ST<=key?S3:S4;

S4: ST<=key?S5:S0;

S5: ST<=key?S3:S4;

default: ST<=key?S3:S0;

endcase

end;

assign pulse=((ST==S3)||(ST==S4)||(ST==

S5));//二段:輸出函數(shù)

實驗結(jié)果表明，這種基于自動狀態(tài)機的按鍵消抖方法，不僅適用于按鍵，而且對抖動特別厲害的撥碼開關(guān)，效果也非常好，使學生直觀地體會到自動狀態(tài)機的妙用。

2.2 串口通信實驗的有限狀態(tài)機設(shè)計

串口通信實驗要求設(shè)計一個簡單的起止式異步串口通信模塊，包含4個部件：波特率發(fā)生器、發(fā)送器、接收器、控制與狀態(tài)設(shè)置電路，目的是在FPGA實驗板卡與PC之間實現(xiàn)串口通信[9-10]。其中的發(fā)送器和接收器，可以各使用一個有限狀態(tài)機實現(xiàn)，圖5為接收器有限狀態(tài)機的狀態(tài)轉(zhuǎn)移圖，默認波特率因子是16。

圖5 串行通信接收狀態(tài)機轉(zhuǎn)移圖

在該實驗的狀態(tài)機中，狀態(tài)轉(zhuǎn)移條件不是簡單的串行輸入信號Sin，而是需要對接收時鐘和對接收的數(shù)據(jù)位數(shù)進行計數(shù)。譬如在S1狀態(tài)下，對Sin低電平進行脈沖計數(shù)，超過8個clk，即表明確實收到了起始位，則轉(zhuǎn)移到S2；在S2狀態(tài)下，不僅需要對clk計數(shù)(16個clk時記錄數(shù)據(jù)位Sin)，而且還須對接收的數(shù)據(jù)位數(shù)進行計數(shù)，當接收數(shù)據(jù)位和校驗位的位數(shù)等于通信參數(shù)設(shè)定的格式時，轉(zhuǎn)移到S3；S3是接收停止位的狀態(tài)，同樣對輸入信號Sin=1狀態(tài)進行clk計數(shù)，符合通信數(shù)據(jù)格式中規(guī)定的停止位數(shù)(1位/16clk、1.5位/24clk、2位/32clk)時，則轉(zhuǎn)入線路空閑狀態(tài)。

通過串行通信收發(fā)器的有限狀態(tài)機設(shè)計，不僅可靠地完成了起止式串行通信的收發(fā)功能，而且使學生深刻理解了SFM在較為復雜的順序執(zhí)行過程控制中的不可替代的優(yōu)勢，同時進一步掌握SFM的靈活應(yīng)用與實現(xiàn)方法。

由于綜合工具的影響，在該實驗的調(diào)試過程中，會碰到有限狀態(tài)機“跑飛”現(xiàn)象，即狀態(tài)機可能會進入無效狀態(tài)，且無法自啟動。因此，教導學生學習設(shè)置有限狀態(tài)機的綜合選項非常重要，譬如選擇狀態(tài)編碼方式、開啟安全狀態(tài)機開關(guān)等等，從而使得SFM安全、可靠運行。

2.3 多周期CPU實驗的有限狀態(tài)機設(shè)計

我校計算機科學與技術(shù)專業(yè)的“計算機組成原理”課程實踐環(huán)節(jié)，最終目標是設(shè)計一個能執(zhí)行19條MIPS核心指令的單周期CPU[11-12]。

然而，硬布線控制器由于執(zhí)行速度快，是目前大部分CPU實現(xiàn)指令的主要方式[13]。本文設(shè)計的多周期CPU實驗，要求使用自動狀態(tài)機實現(xiàn)硬布線控制器，其MIPS系統(tǒng)結(jié)構(gòu)如圖6所示[12]，可以實現(xiàn)典型的R型、I型、J型3種格式的MIPS核心指令，含運算、訪存、分支、跳轉(zhuǎn)指令。

從計算模型的角度來看，計算機的本質(zhì)就是一臺有限狀態(tài)自動機，它任何時間都處在有限狀態(tài)集的某一個狀態(tài)中。因此，該實驗中，最關(guān)鍵的步驟是引導學生通過對指令執(zhí)行過程的分析，確定CPU的狀態(tài)集，即指令流程圖的每一個方框。圖7為一個CPU指令執(zhí)行狀態(tài)集的轉(zhuǎn)移圖范例，是由指令流程圖變換、合并而來。

圖6 多周期MIPS CPU系統(tǒng)結(jié)構(gòu)

圖7 CPU的有限狀態(tài)圖

圖7中每一個方框均為一個狀態(tài)；狀態(tài)轉(zhuǎn)移條件為當前指令的6位指令操作碼op；輸出變量則為各種控制信號與運算操作碼。

顯然，這個狀態(tài)機的控制較為復雜，可以引導學生采用三段式描述方式，即：狀態(tài)轉(zhuǎn)移使用一個時序邏輯的always語句模塊；下一狀態(tài)函數(shù)采用一個組合邏輯的always語句模塊；輸出模塊則采用另一個組合邏輯電路。這樣的描述特別適合于復雜的有限狀態(tài)機[14]，其邏輯結(jié)構(gòu)清晰，調(diào)試與修改方便。

3 結(jié) 語

有限狀態(tài)機在數(shù)字系統(tǒng)、計算機及工程應(yīng)用中占有非常重要的地位，是實現(xiàn)順序控制的有效工具。本文結(jié)合計算機硬件系列課程實驗改革，基于統(tǒng)一的FPGA實驗平臺，巧妙地將有限狀態(tài)機的設(shè)計融合在三門課程的3個硬件實驗中，使學生在實際應(yīng)用中掌握有限狀態(tài)機的概念、原理與設(shè)計方法，順應(yīng)了強調(diào)一體化實驗教學改革的大趨勢[15]。

經(jīng)過2年3屆學生、3門課程的試點與推廣，學生對有限狀態(tài)機的使用與設(shè)計能力都有了很大地提升，尤其在CPU的設(shè)計實驗中，學生更是深刻地理解了“計算機就是一個有限狀態(tài)機”的含義，大大提高了教學效果。

[1] 孫宏旭,邢 薇,陶 林.基于有限狀態(tài)機的模型轉(zhuǎn)換方法的研究[J].計算機技術(shù)與發(fā)展,2012,22(2):10-13.

[2] 陸玲霞,姚 維,高 健.基于VHDL的FPGA新實驗開發(fā)——簡易處理器實現(xiàn)[J].實驗室研究與探索.2013,32(11):269-272.

[3] [美]David A.Patterson,John L Hennessy.計算機組成與設(shè)計-硬件/軟件接口[M].北京:機械工業(yè)出版社,2007.

[4] 陳 勇.有限狀態(tài)機的建模與優(yōu)化設(shè)計[J].重慶工學院學報(自然科學版)，2007,21(5):55-58.

[5] 吳厚航.深入淺出玩轉(zhuǎn)FPGA(第2版)[M].北京:北京航空航天大學出版社，2013.

[6] 呂高煥,楊 亮,鄧冠龍.VHDL中的有限狀態(tài)機教學方法研究[J].電氣電子教學學報,2015,37(6):63-67.

[7] 孔 昕,吳武臣,侯立剛,等.基于Verilog的有限狀態(tài)機設(shè)計與優(yōu)化[J].微電子學與計算機，2010,27(2):180-183.

[8] 劉小平,何云斌,董懷國.基于Verilog HDL的有限狀態(tài)機設(shè)計與描述[J].計算機工程與設(shè)計，2008,29(4):958-960.

[9] 馮建文,章復嘉,包 健,等.基于FPGA的數(shù)字電路實驗指導書[M].西安:西安電子科技大學出版社,2016.4.

[10] 于志翔.基于FPGA的UART設(shè)計與實現(xiàn)[J].電子測量技術(shù)，2015,38(3):77-81.

[11] 馮建文,章復嘉,包 健.計算機組成原理與系統(tǒng)結(jié)構(gòu)實驗指導書[M].2版.北京:高等教育出版社,2015.

[12] 包 健,馮建文,章復嘉.計算機組成原理與系統(tǒng)結(jié)構(gòu)[M].2版.北京:高等教育出版社,2015.

[13] 高 艷,富 坤,羅淑貞，等.基于FPGA模型機的組合邏輯控制器[J].實驗室研究與探索，2015,34(4):86-91.

[14] 夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計教程[M].3版.北京:北京航空航天大學出版社,2013.

[15] 全成斌,鄭寧漢,楊士強.計算機一體化實驗教學改革與探索[J].中國大學教學，2014(6):78-80.

Application of Finite State Machine in FPGA Hardware Experiment

FENGJianwen

(College of Computer Science， Hangzhou Dianzi University， Hangzhou 310018， China)

Finite state machine (FSM) is an effective tool to describe and implement sequential control, and it is widely used in the fields of computer, digital system and industrial automation. The article introduces the concept, principles and design procedure of FSM, and expounds the principles and methods of using FSM to realize the key jitter elimination experiment, serial communication experiment and multi-cycle CPU experiment. In this article, FSM is applied to FPGA hardware experiment, so that students can understand the principles of FSM, and master the FSM design methods. The experiment design has achieved good teaching effect.

finite state machine(FSM); field-programmable gate array(FPGA); hardware experiment; key jitter elimination; serial communication; multi-cycle CPU

2016-08-10

浙江省高等教育教學改革項目(jg2013058)；教育部國家精品資源共享課程(高教廳函[2016]54號)

馮建文(1971-)，女，河南汝南人，碩士，副教授，主要研究方向嵌入式系統(tǒng)與智能控制。

Tel.：18167103516；E-mail：fengjianwen@hdu.edu.cn

TP 33

A

1006-7167(2017)06-0138-04