有限状态机FSM在PLD中的实现分析
研究设计 电 子 测 量 技 术
EL ECTRONIC MEASUREMEN T TECHNOLO GY
第 30 卷 第 10 期
2007 年 10 月
有限状态机 FSM 在 PLD 中的实现分析 3
何永泰
(云南楚雄师范学院物理与电子科学系 楚雄 675000)
摘 要 : 随着 EDA 技术的发展 ,利用 V HDL 语言描述有限状态机 ( FSM) ,得到广泛应用研究。本文通过举例 ,利用
V HDL 语言描述了不同模式的有限状态机 ,分析了有限状态机在 PLD 中综合的特点。同时 ,本文中对不同描述风格
的有限状态机在 PLD EMP7032 中综合的特性进行了比较分析。可以看出 ,不同的模式、不同的描述风格 ,对有限状
态机的特性具有较大的影响。这一结果 ,为在实际的设计中 ,对有限状态机的 V HDL 语言设计的优化提供了有效的
参考依据。
关键词 : 有限状态机 (FSM) ; 可编程逻辑器件 ; V HDL 语言
中图分类号 : TP331. 2 文献标识码 : A
Analyzed realization of finite state machine on programmable logic device
He Yongtai
(Department of Physics and Electron Science ,Chuxiong Normal University ,Chuxiong 675000)
Abstract : With developing of EDA technique ,using V HDL language describes FSM is in broad use. Different pattern
of FSM were described through V HDL language in this paper. We also analyzed characteristic of synthesis of FSM on
PLD by giving an example in the paper. At the same time ,the different characteristic in different description style of
FSM synthesized on the EMP7032 was compared. Comparing results show that different patter ,different description all
contributes to the characteristic of FSM ,which provide us a solid reference basis for the V HDL language optimization
for FSM.
Keywords : finite state machine ; programmable logic device(PLD) ; V HDL language
3 基金项目 :楚雄师范学院院级自然科学基金项目 (05 - YJ RC01)
0 引 言
目前 ,随着 PLD 技术的发展 ,以可编程逻辑器件为载
体 ,以 V HDL 语言为描述方式 ,以相应的集成开发环境为
开发工具的现代数字系统设计方法 ,正在取代传统的数字
系统设计方法。有限状态机(finite state machine ,FSM) 作
为时序逻辑电路的主要表示方式 ,其 V HDL 语言的描述风
格和在可编程逻辑器件 ( PLD) 综合的特点得到越来越广
泛的研究。本文从有限状态机的模式及 V HDL 描述风格
两方面入手 ,分析不同模式不同描述风格状态机对 PLD 资
源的占用及其运行速度等方面的影响 ,结果表明 PLD 的结
构特点非常适合于实现有限状态机 FSM ,为利用 V HDL
语言设计有限状态机及在 PLD 中综合 FSM 提供了依据。
1 有限状态机的模式及特点
1. 1 有限状态机的模式
一个限状态机是一个 5 元函数 M = ( X , Y , S , f , g) ,其
中 X 为输入信号变量; Y 为输出信号变量; S 为状态; f 为
状态转换函数 ,表示由输入信号变量 X 和当前状态 S 决定
下一个状态即 : X Y →S ; g 为输出函数 ,表示由输入信号变
量 X 和状态 S 决定状态机的输出变量 Y 即 : X S →Y 。根
据有限状态机的输出 Y 与当前状态和当前输入的关系 ,可
以将有限状态机分为莫尔 (Moore) 型和米勒 (Mealy) 型 2
类。Moore 状态机的输出只与有限状态机的当前状态有
关 ,与输入信号的当前值无关 ,输入对输出的影响要到下
一个时钟周期才能反映出来。其行为描述可用式 ( 1)
表示 :
S n + 1 = f ( X n , S n)
Y n = g( S n)
(1)
Mealy 有限状态机的输出与输入信号的当前值有关 ,
其行为描述可用方程(2) 表示 :
S n + 1 = f ( X n , S n)
Y n = g( X n , S n)
(2)
Mealy 有限状态机输入信号可能在一个时钟周期内任
·4·
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
何永泰 :有限状态机 FSM 在 PLD 中的实现分析 第 10 期
意时刻变化 ,这使得 Mealy 有限状态机对输入的影响发生
在当前时钟周期 ,比 Moore 有限状态机对输入信号的响应
要早一个时钟周期。例如 ,一个空调控制系统的状态转换
如图 1 所示 ,利用 V HDL 语言描述的 Moore 型有限状态
机和 Mealy 型空调控制系统 ,在 MAXPLUSII 中时序仿真
结果如图 2(a) 、2(b) 所示。
图 1 空调控制系统的状态转换图
图 2 空调控制系统状态机时序仿真图
同时 ,根据有限状态机状态编码方式的不同 ,可将状
态机分为二进制编码和一位有效 (one2hot) 编码两种。二
进制编码 ,即将状态依次编码为顺序的二进制数 ,它是最
紧密的编码 ,优点在于它使用状态向量的位数最少。例如
对于 8 个状态 ,只需要 3 位二进制数来进行编码。在 one2
hot 编码中 ,对于任何给定状态 ,状态向量只有 1 位置为 1 ,
所有其他的状态位都为 0 ,one2hot 编码最长 ,因为 n 个状
态就需要 n 位的状态向量 ,one2hot 编码的状态机最大的优
势是它的速度。莫尔 (Moore) 型二进制编码与 one2hot 编
码的速度随状态数量变化如表 1 所示。
从表 1 中可以看出 ,对于同一类型的状态机 ,在状态
数量相等的情况下 ,one2hot 编码状态机的速度总比二进制
编码状态机的速度快。
表 1 状态编码与状态机的速度比较
状态数 状态机的时钟
二进制编码/ M Hz One2hot 编码/ M Hz
3 142. 86 172. 4
8 96. 15 112. 35
1. 2 有限状态机在 PLD 中实现分析
可编程逻辑器件 ( PLD) 根据内部基本逻辑单元结构
的不同分为两类 ,基本逻辑单元由与2或阵列为主构成的称
为 CPLD ,基本逻辑单元由查找表 LU T 为主构成的称为
FPGA 。由于基本逻辑单元结构的不同 ,V HDL 语言设计
的数字系统在两类器件中综合有所不同。CPLD 中逻辑块
LAB 的基本结构如图 3 所示。主要由与2或阵列、r 个宏单
元、和 m 个双向口等组成。若状态机有 L 位输入 , N 位输
出和 M 个状态 , 表示为 X = { x1 , x2 , ?, xL } , Y = { y1 , y2 ,
?, y N } 和 S = { s1 ,s2 , ?,sM} ,其中 ,状态码长为 R 位。若状
态编码采用一位有效 (one2hot) 编码方式 ,那么 ,状态数 M
与状态码 R 相等 , 即 : R = M 。在 CPLD 中实现状态机
FSM ,必须考虑满足不等式组(3) 的关系 :
N ≤m ·F
R ≤r ·F - N
L ≤ dl + m ·F - N
(3)
在不等式组 (3) 中 , F 表示 CPLD 中逻辑块 LAB 的个
数 , dl 为 CPLD 的专用逻辑控制输入端。不等式组(3) 中 ,
第 1 式表示设计的输出位数不能超过 CPLD 的用户端口 ,
第 2 式表示在 CPLD 中必须有足够的宏单元存储状态变
量 ,第 3 式表示设计中必须为输入变量留有足够的 I/ O
口。对于莫尔(Moore) 有限状态机 ,其在 CPLD 中的综合
可分为状态转换函数的实现和输出函数的实现两步 ,状态
转换函数的实现在于放置 FSM 到 CPLD 中逻辑块中的存
储单元触发器中 ,目的在于使每一个 LAB 有足够的资源
实现触发器的激励函数 ;输出函数的实现在于分配 FSM
的输出函数 到 CPLD 的逻辑块 LAB 中 ,目的在于使 LAB
有足够的资源实现输出函数。
图 3 CPLD 中逻辑块 LAB 的基本结构图
·5·
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第 30 卷 电 子 测 量 技 术
2 有限状态机的描述风格及特性分析
状态机的性能有多方面的因素决定 ,除了前面提到的
状态机的不同模式、状态编码之外 ,在 V HDL 语言描述的
状态机中 ,根据描述风格的不同可将其分为 A 、B、C、D、E 5
种 ,其对状态机的性能也会产生较大的影响。下面以多位
输出空调控制系统不同描述风格为例进行比较 ,其状态图
如图 4 所示。利用 V HDL 语言描述的不同描述风格的状
态机 ,其在 MAXPLUSII 中编译综合后下载到 EMP7032
中 ,对 CPLD 资源的占用、运行速度等特点如表 2 所示。
图 4 多位输出空调控制系统的状态转换图
表 2 不同描述风格的综合特性
描述风格 逻辑单元 乘积项 触发器 时钟/ M Hz
A 19 42 2 142
B 18 32 18 95
C 18 37 18 142
D 17 45 9 112
E 18 41 2 172
从表 2 中可以看出 ,不同的描述风格 ,其在 CPLD 中
综合时占用资源的情况及时钟的速度各不相同。V HDL
语言描述风格 A 、E 中 ,宏单元中的触发器被旁路 ,状态输
出采用组合逻辑工作方式 ,综合中 ,乘积项使用较多 ,触发
器使用较少 ,状态机的时钟速度较快。描述风格 B 状态输
出采用触发器工作方式 ,综合中 ,乘积项使用最少 ,触发器
使用较多 ,状态机的时钟速度较低。描述风格 C 状态输出
采用触发器工作方式 ,在 V HDL 语言程序设计中状态机用
一个进程实现了次态逻辑、状态寄存器及输出逻辑 ,通过
部分加强组合逻辑功能 ,时钟速度较描述风格 B 有了较大
提高。描述风格 D 用一个进程实现次态逻辑和状态寄存
器 ,用一个进程实现输出逻辑 ,在 CPLD 中占用的资源最
少。在实际的设计中 ,选用哪一种描述方式 ,可根据所选
用的器件的结构特点 ,结合各描述风格在综合时对器件资
源占用的特性来选择 ,例如 ,器件为 CPLD 则选择描述风
格 A 、E ,若器件为 FPGA 则选择描述风格 B、C。
3 结 论
利用 V HDL 语言描述的有限状态机 ,在 PLD 中综合
时 ,必须要考虑 PLD 的资源(包括 I/ O 口) 与状态机的输入
变量、状态变量及输入输出变量的关系。同时 ,有限状态
机 FSM 不同的模式、不同的状态编码及 V HDL 语言不同
的描述风格对状态机的性能会产生较大的影响。利用
V HDL 语言描述的有限状态机 ,通过状态编码及描述方式
的优化 ,其对 PLD 资源的占用可达到 33 %。
参 考 文 献
[1 ] 褚振勇 ,翁木云. FPGA 设计及应用[ M ]. 西安 :西安电
子科技大学出版社 ,2002.
[2 ] 赵俊超. 集成电路设计 V HDL 教程[ M ]. 北京 :希望电
子出版社 ,2002.
[3 ] AVEDILL O M , QUIN TANA J , HU ERTAS J . State
merging and state splitting via state assignment : a new
FSM synthesis algorithm [J ]. IEE Proceedings , Part
E ,Computers and Digital Techniques ,1994 ,141 (4) :
2292237.
[4 ] GIRAUL T A ,L EE B ,L EE E. Hierarchical finite state
machineswith multiple concurrency models [J ]. IEEE
Transactions on CAD ,1999 ,18 (6) :7422760.
[ 5 ] BOLCHINI C , MAN TANDAN R , SOL ICE F ,et al.
Design ofV HDL2Based Totally Self2checking Finite2
State Machincand Data2Path Description [ J ]. IEEE
Trans. On Very LugeScale Itiregrafion ( VLSr) S～
xtenis ,2000 ,8 (I) :1862195.
[6 ] 袁作涛. 可编程温度控制系统设计[J ]. 电子测量技术 ,
2005 (6) :53254.
[7 ] 何永泰 ,黄文卿. 基于 FPGA 的 CSD 编码乘法器[J ].
电子测量技术 ,2006 ,29 (4) :87288.
[8 ] BOLCHINI C , SOL ICE F , SCITO D. Fault Analysis
forNenwrks with Concurrent Error Detection[J ]. IEEE
DesigdTesr of Compirters ,1999 ,15 (4) :66274.
作 者 简 介
何永泰 ,男 ,1970 年出生 ,汉族 ,云南南华人 ,硕士 ,现
为楚雄师范学院副教授 ,主要研究方向为嵌入式系统 ,
FPGA 设计开发。
E2mail : hyt_127 @yahoo. com. cn
·6·
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
有限状态机FSM在PLD中的实现分析.pdf
