馮 建 文

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

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

馮 建 文

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

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

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

0 引 言

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

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

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

圖1 有限狀態(tài)機結構圖

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

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

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

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

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

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

2 有限狀態(tài)機的實驗應用設計

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

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

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

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

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

圖2 按鍵消抖實驗示意圖

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

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

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

從圖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)轉換與輸出

函數

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由實驗板卡的系統時鐘源100 MHz分頻產生，可將周期調節(jié)在1 ms左右。

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

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

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

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));//二段:輸出函數

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

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

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

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

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

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

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

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

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

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

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

圖6 多周期MIPS CPU系統結構

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

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

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

3 結 語

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

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

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

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

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

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

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

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

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

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

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

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

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

[12] 包 健,馮建文,章復嘉.計算機組成原理與系統結構[M].2版.北京:高等教育出版社,2015.

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

[14] 夏宇聞.Verilog數字系統設計教程[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-)，女，河南汝南人，碩士，副教授，主要研究方向嵌入式系統與智能控制。

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

TP 33

A

1006-7167(2017)06-0138-04