有限状态机在FPGA硬件实验中的应用

冯 建 文

(杭州电子科技大学 计算机学院，杭州 310018)

有限状态机在FPGA硬件实验中的应用

冯 建 文

(杭州电子科技大学 计算机学院，杭州 310018)

有限状态机(FSM)是描述与实现顺序控制的有效工具，广泛应用于计算机、数字系统和工业自动化领域。介绍了FSM的概念、原理与设计步骤，阐述了使用FSM实现按键消抖实验、串行通信实验和多周期CPU实验的原理和具体方法。将FSM应用于FPGA硬件实验中，使学生能够理解FSM的原理，并掌握其设计方法，取得了较好的实验教学效果。

有限状态机； 现场可编程门阵列； 硬件实验； 按键消抖； 串行通信； 多周期CPU

0 引 言

有限状态机(Finite State Machine，FSM)是描述有限个状态以及在这些状态之间进行转移和动作等行为的数学模型[1]。它广泛应用于自动化、数字系统、计算机系统等领域，譬如PLC控制器的顺序控制功能、CPU的指令执行控制等，均是FSM的典型应用范例。因此，对于高等院校工科学生而言，掌握FSM的原理与设计方法非常重要。随着EDA技术的发展，FPGA器件逐步成为最广泛的硬件实验平台[2]。如何将FSM应用与融合在基于FPGA的硬件实验中，是一个非常现实而又有意义的课题。FSM实际上是一种描述与解决问题的模型工具，因此，其实验必定是基于某种应用背景而设计的。遵循实用、易于掌握、循序渐进的原则，针对高校计算机大类专业本科生，本文设计了3个基于FSM的FPGA实验，取得了较好的实验效果。

1 有限状态机概述

FSM包含了一组有限的状态量和2个函数：下一状态函数和输出函数[3]，如图1所示。图中：rst信号用于确定有限状态机的初始状态(S0)和原始输出；clk用于同步状态转换的边沿或者定时状态转换的周期。状态集包含可能出现在中间过程中的所有状态量，使用触发器保存。下一状态函数则是通过输入变量和当前状态确定转移到下一状态的组合逻辑函数。输出函数根据当前状态和输入变量产生电路的一组输出变量。与普通的时序逻辑函数一样，如果输出函数仅仅依赖于当前状态，则称该有限状态机为Moore型状态机；如果输出函数不仅依赖于当前状态，也依赖于当前输入，则称该有限状态机为Mealy型状态机[4]。

图1 有限状态机结构图

用硬件描述语言(HDL)描述的FPGA电路大都是并行实现，但是对于实际工程应用，往往需要让硬件来实现一些具有一定顺序逻辑的工作。而FSM就是通过不同的状态迁移来完成一些特定的顺序逻辑[5]。因此，FSM是FPGA数字系统设计的重要工具与精髓所在[6]。

基于FPGA的FSM的设计步骤如下[5-6]：

(1) 进行逻辑分析与抽象，确定输入、输出与状态变量，画出状态转移图；

(2) 状态简化，得到最简的状态转移图；

(3) 对状态进行编码。可选择binary、gray、one-hot编码方式之一，在FPGA的开发综合平台和综合工具中，可以进行选择或者自定义[7-8]；

(4) 用HDL描述，并综合、仿真与实现：描述方式有一段式、二段式和三段式三种方式[7-8]。

2 有限状态机的实验应用设计

有限状态机作为一种实现顺序控制与定时的手段，其实验设计应与具体的实验目标相结合。因此，在计算机科学与技术专业的硬件课程实验改革中，设计了3个难度递增的硬件实验，在不同的本体应用背景中，使学生逐步掌握FSM的原理与设计方法。表1描述了3个应用实验的本体实验目的与FSM实验目标。

2.1 按键消抖实验的有限状态机设计

实验原理如图2所示[9]。将按键信号key作为输入，经过消抖后，产生一个单脉冲信号pulse。按键按下为高电平，松开为低电平。虽然按键消抖方法很多，但是实验要求使用FSM实现一种更可靠的按键消抖方法。

分析按键按下到松开的整个过程，将其分为6个状态，如图3所示。

表1 有限状态机实验设计

图2 按键消抖实验示意图

图3 按键状态分析

分析状态变化的条件和输出，可以画出FSM的状态转移图，如图4所示。

图4 按键消抖FSM状态转移图

从图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;//状态集定义

reg[2:0] ST;//当前状态

always @(posedgerst or posedgeclk)//一段:状态转换与输出

函数

begin

if (rst) begin//初始状态赋值

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分频产生，可将周期调节在1 ms左右。

在完成了这个逻辑简单的按键消抖实验后，引导学生思考并尝试实现：如何将其变成二段式FSM？该FSM能否转变成Moore型FSM？从而真正理解FSM的基本概念与基本设计方法。

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

always @(posedgerst or posedgeclk)//一段:状态转换

begin

if (rst)//初始状态赋值

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

实验结果表明，这种基于自动状态机的按键消抖方法，不仅适用于按键，而且对抖动特别厉害的拨码开关，效果也非常好，使学生直观地体会到自动状态机的妙用。

2.2 串口通信实验的有限状态机设计

串口通信实验要求设计一个简单的起止式异步串口通信模块，包含4个部件：波特率发生器、发送器、接收器、控制与状态设置电路，目的是在FPGA实验板卡与PC之间实现串口通信[9-10]。其中的发送器和接收器，可以各使用一个有限状态机实现，图5为接收器有限状态机的状态转移图，默认波特率因子是16。

图5 串行通信接收状态机转移图

在该实验的状态机中，状态转移条件不是简单的串行输入信号Sin，而是需要对接收时钟和对接收的数据位数进行计数。譬如在S1状态下，对Sin低电平进行脉冲计数，超过8个clk，即表明确实收到了起始位，则转移到S2；在S2状态下，不仅需要对clk计数(16个clk时记录数据位Sin)，而且还须对接收的数据位数进行计数，当接收数据位和校验位的位数等于通信参数设定的格式时，转移到S3；S3是接收停止位的状态，同样对输入信号Sin=1状态进行clk计数，符合通信数据格式中规定的停止位数(1位/16clk、1.5位/24clk、2位/32clk)时，则转入线路空闲状态。

通过串行通信收发器的有限状态机设计，不仅可靠地完成了起止式串行通信的收发功能，而且使学生深刻理解了SFM在较为复杂的顺序执行过程控制中的不可替代的优势，同时进一步掌握SFM的灵活应用与实现方法。

由于综合工具的影响，在该实验的调试过程中，会碰到有限状态机“跑飞”现象，即状态机可能会进入无效状态，且无法自启动。因此，教导学生学习设置有限状态机的综合选项非常重要，譬如选择状态编码方式、开启安全状态机开关等等，从而使得SFM安全、可靠运行。

2.3 多周期CPU实验的有限状态机设计

我校计算机科学与技术专业的“计算机组成原理”课程实践环节，最终目标是设计一个能执行19条MIPS核心指令的单周期CPU[11-12]。

然而，硬布线控制器由于执行速度快，是目前大部分CPU实现指令的主要方式[13]。本文设计的多周期CPU实验，要求使用自动状态机实现硬布线控制器，其MIPS系统结构如图6所示[12]，可以实现典型的R型、I型、J型3种格式的MIPS核心指令，含运算、访存、分支、跳转指令。

从计算模型的角度来看，计算机的本质就是一台有限状态自动机，它任何时间都处在有限状态集的某一个状态中。因此，该实验中，最关键的步骤是引导学生通过对指令执行过程的分析，确定CPU的状态集，即指令流程图的每一个方框。图7为一个CPU指令执行状态集的转移图范例，是由指令流程图变换、合并而来。

图6 多周期MIPS CPU系统结构

图7 CPU的有限状态图

图7中每一个方框均为一个状态；状态转移条件为当前指令的6位指令操作码op；输出变量则为各种控制信号与运算操作码。

显然，这个状态机的控制较为复杂，可以引导学生采用三段式描述方式，即：状态转移使用一个时序逻辑的always语句模块；下一状态函数采用一个组合逻辑的always语句模块；输出模块则采用另一个组合逻辑电路。这样的描述特别适合于复杂的有限状态机[14]，其逻辑结构清晰，调试与修改方便。

3 结 语

有限状态机在数字系统、计算机及工程应用中占有非常重要的地位，是实现顺序控制的有效工具。本文结合计算机硬件系列课程实验改革，基于统一的FPGA实验平台，巧妙地将有限状态机的设计融合在三门课程的3个硬件实验中，使学生在实际应用中掌握有限状态机的概念、原理与设计方法，顺应了强调一体化实验教学改革的大趋势[15]。

经过2年3届学生、3门课程的试点与推广，学生对有限状态机的使用与设计能力都有了很大地提升，尤其在CPU的设计实验中，学生更是深刻地理解了“计算机就是一个有限状态机”的含义，大大提高了教学效果。

[1] 孙宏旭,邢 薇,陶 林.基于有限状态机的模型转换方法的研究[J].计算机技术与发展,2012,22(2):10-13.

[2] 陆玲霞,姚 维,高 健.基于VHDL的FPGA新实验开发——简易处理器实现[J].实验室研究与探索.2013,32(11):269-272.

[3] [美]David A.Patterson,John L Hennessy.计算机组成与设计-硬件/软件接口[M].北京:机械工业出版社,2007.

[4] 陈 勇.有限状态机的建模与优化设计[J].重庆工学院学报(自然科学版)，2007,21(5):55-58.

[5] 吴厚航.深入浅出玩转FPGA(第2版)[M].北京:北京航空航天大学出版社，2013.

[6] 吕高焕,杨 亮,邓冠龙.VHDL中的有限状态机教学方法研究[J].电气电子教学学报,2015,37(6):63-67.

[7] 孔 昕,吴武臣,侯立刚,等.基于Verilog的有限状态机设计与优化[J].微电子学与计算机，2010,27(2):180-183.

[8] 刘小平,何云斌,董怀国.基于Verilog HDL的有限状态机设计与描述[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