有限状态机的建模与优化设计
X 收稿日期 :2007 - 01 - 26
基金项目 :重庆市自然科学基金资助项目 (渝科发技字[2004]55) .
作者简介 :陈勇 (1980 - ) ,男 ,重庆人 ,硕士研究生 ,主要从事 DAB 接收机核心芯片设计和 SOC 研究.
【电子与自动化】
有限状态机的建模与优化设计 X
陈 勇
(重庆邮电大学 微电子工程重点实验室 ,重庆 400065)
摘要 :通常的 Verilog HDL 编码风格生成的电路速度慢、面积大、毛刺干扰严重. 基于此特点提出一
种优秀、高效的 Verilog HDL 描述方式来进行有限状态机设计 ,介绍了有限状态机的建模原则 ,并
通过一个可综合的实例 ,验证了该方法设计的有限状态机在面积和功耗上的优势.
关 键 词 :有限状态机 ;Verilog HDL ;仿真 ;综合 ;优化设计
中图分类号 :TN402 文献标识码 :A 文章编号 :1671 - 0924(2007) 05 - 0055 - 04
Modeling and Optimized Design of Finite State Machine
CHEN Yong
( Key Lab of Microelectronics Engineering , Chongqing University of Posts and Telecommunications , Chongqing 400065 ,China)
Abstract : The circuits generated from the common Verilog HDL coding style are slow in speed , big in
area , and serious in burr interference. Based on these characteristics , this paper presents an excellent and
efficient manner described in Verilog HDL in the design of finite state machine. In addition , it introduces
the modeling of finite state machines , and verifies with a synthesizable example the advantages of the design
method of finite state machine in the area and power consumption. This method has a certain guiding sig2
nificance in the design of very large scale integrated circuits.
Key words : Finite State Machine ; Verilog HDL ; simulation ; synthesis ; optimized design
0 引言
数字集成电路已经从电子管、晶体管、中小规
模集成电路、超大规模集成电路逐步发展到今天
的专用集成电路 (ASIC) ,数字逻辑器件也从简单
的逻辑门发展到了复杂的 SOC(System On Chip 片
上系统) ,数字系统的设计方法也随之不断演进 ,
硬件 描 述 语 言 ( HDL , Hardware Description Lan2
guage) 便由此产生. Verilog HDL 是在 1983 年由
GDA( GateWay Design Automation) 公司的 Phil Moorby
首创的. 基于 Verilog HDL 的优越性 ,IEEE 于 1995
年制定了 Verilog HDL 的 IEEE 标准 ,即 Verilog HDL
1364 - 1995[1] . Verilog HDL 作为硬件描述语言的一
种 ,用于数字电子系统设计. 它允许设计者用它来
进行各种级别的逻辑设计 ,进行数字逻辑系统的
仿真验证、时序分析、逻辑综合.
在数字集成电路系统中 ,大部分是时序电路 ,
第 21 卷 第 5 期
Vol. 21 No. 5
重 庆 工 学 院 学 报(自然科学版)
Journal of Chongqing Institute of Technology(Natural Science Edition)
2007 年 5 月
May 2007
时序电路可以用符号化的有限状态机 (Finite-State-
Machine ,简称 FSM) 来模拟. 把一个时序逻辑抽象
成一个同步有限状态机是设计可综合风格的 Ver2
ilog HDL 模块的关键 ,基于不同的有限状态机的
Verilog 编码风格 ,经综合后得到电路的物理实现
在速度、面积、时延特性、功耗上有很大的差别 ,因
此 ,对 FSM 的建模与优化设计的研究有着重要意
义. 在实际设计经验中 ,提出的是一种新的、优秀
的有限状态机 Verilog 建模方法 ,使得完成的电路
在满足时序设计要求的前提下 ,占用最小的芯片
面积 ,无论是在速度还是功耗上都有所突破.
1 有限状态机建模
1. 1 有限状态机的模型
根据状态机的输出是否与输入条件相关 ,可
将状态机分为两大类 :摩尔 (Moore) 型状态机和米
勒(Mealy) 型状态机[2] :
1) 摩尔状态机的输出仅仅依赖于当前状态 ,
而与输入条件无关 ;
2) 米勒型状态机的输出不仅依赖于当前状
态 ,而且取决于该状态的输入条件 ,如图 1 所示.
图 1 米勒状态机结构图
在逻辑设计中 ,状态机的基本描述方式有 3
种 ,分别是状态转移图、状态转移列表、HDL 语言
描述. 状态转移图是通过图形化的方式描述状态
机各个状态之间的转换关系. 状态转移列表是用
列表的方式描述状态机 ,是数字逻辑电路常用的
设计方法之一 ,经常被用于对状态化简. HDL 语言
描述状态机是使用硬件描述语言 Verilog HDL 或者
VHDL 设计高速、稳定的状态机.
1. 2 有限状态机建模原则
一个设计所消耗芯片的逻辑资源数用“面积”
来衡量 ,而设计在芯片上稳定运行所能够达到的
最高频率用“速度”来评价. 因此在 FPGA 和 ASIC
的设计中 ,必须兼顾面积和速度 2 个指标. 在满足
设计时序要求(包含对设计最高频率的要求) 的前
提下 ,占用最小的芯片面积 ,或者在所规定的面积
下 ,使设计的时序余量更大 ,频率更高. 因此 ,基于
Verilog HDL 的有限状态机建模 ,应该主要考虑以
下几点 :
1) 采用优秀的一位独热码 (one-hot) [3]编码方
案 ,译码简单且节省和简化了组合逻辑电路 ,综合
后电路速度快 ;
2) FSM 的综合实现结果避免了组合逻辑电路
产生的毛刺等异常扰动 ;
3) 状态机所有状态必须完备 ,不会进入死循
环和不确定的状态. 进入异常状态能恢复到正常
状态 ;
4) 采用双边沿触发器的设计 ,完全利用了时
钟的上、下边沿 ,从而达到节省功耗的目的 ,并满
足速度和面积的设计要求.
2 有限状态机的优化设计
一个典型的有限状态机共有 4 个状态 : S0 ,
S1 , S2 , S3 ;输入时钟信号为 clk ,高电平异步复位
信号为 rst ,输入信号为 money ,输出信号为 drink ,
状态转移图如图 2 所示 ,状态转移表如图 3 所示.
图 2 状态转移图
图 3 状态转移表
其部分 Verilog HDL 程序如下 :
/ / Design the drink vending machine coin acceptor
65 重 庆 工 学 院 学 报
using a FSM approach
module vend( money , clk , rst , drink) ;
/ / Input output port declarations
input [1∶0] money ;
input clk ,rst ;
output drink ;
reg drink ;
/ / internal FSM state declarations
reg [1∶0] state ;
/ / state encodings
parameter s0 = 2’b00 ; s1 = 2’b01 ; s2 = 2’b10 ;
s3 = 2’b11 ;
/ / 1st always block , sequential state transition
always @ (posedge clk or posedge rst)
if (rst) begin drink < = 1’b0 ;end
elsestate < = s0 ;
/ / 2nd always block , combinational condition
judgment
always @ (rst or state or money)
case (state)
s0 : begin
if (money = = 2’b10)
begindrink < = 1’b0 ;state < = s2 ;end
else if (money = = 2’b01)
begindrink < = 1’b0 ;state < = s1 ;end
else
begindrink < = 1’b0 ;state < = s0 ;end
end
??
/ / 3rd always block , the sequential FSM output
always @ (posedge clk or posedge rst)
if (rst) drink < = 1’b0 ;
else drink < = 1’b1 ;
endcase
end endmodule
从代码上看 ,采用独热码编码方式 ,状态译码
简单 ;采用双边沿触发 ,降低了冗余度 ,这种由 3
个 always 语句的建模方式多了一段寄存器 FSM 输
出. 一般来说 ,使用寄存器输出可以改善输出的时
序条件 ,还能避免组合电路的毛刺 ,所以是更为推
荐的描述方式. 在该结构中 ,从输入到寄存器状态
输出的路径上 ,要经过 2 部分组合逻辑 (状态转移
条件组合逻辑和输出组合逻辑) ,从时序上 ,这 2
部分组合逻辑完全可以看为一体. 解决普通建模
组合逻辑输出产生毛刺的方法是 ,在 FSM 后级电
路额外插入寄存器 ,调整时序 ,完成功能. 在建模
描述 FSM 的状态机输出时 ,只需指定 case 敏感表
为次态寄存器 ,然后直接在每个次态的 case 分支
中描述该状态的输出即可 ,对于复杂一些的 FSM ,
这种建模的优势就会十分显著.
为验证其 Verilog HDL 代码的正确性 , 使用
Modelsim SE6. 1C 对代码进行时序和逻辑仿真.
Mentor Graphics ModelSim SE 是业界最优秀的 HDL
语言仿真器 ,具有快速的仿真性能和最先进的调
试能力 ,它采用直接优化的编译技术 ,是作 FPGA/
ASIC 设计的 RTL 级和门级电路仿真的首选. 经
Modelsim 仿真后 ,结果如图 4 所示 ,可知时序逻辑
是正确的.
采用 Synplicity 公司的 Synplify Pro8. 1 综合工
具对该源程序针对 ALTERA STRATIX EP1S10F7802
C6 器件进行优化、综合 ,图 5 为综合后生成的 RTL
级网表.
图 4 使用 Modelsim SE的时序仿真图
75陈 勇 :有限状态机的建模与优化设计
图 5 RTL 级网表
可以看出 ,综合后使用的 I/ O 口、逻辑单元数
量很少 ,由于占用很小的面积从而功耗非常小 ,下
载到 ALTERA STRATIX EP1S10F780C6 FPGA 中验
证了其功能的正确性.
3 结束语
有限状态机不仅是一种时序电路设计工具 ,
而且还是一种思想方法. 本文中通过一个实例的
仿真、综合 ,提出的是一种先进、高效的有限状态
机 Verilog HDL 建模方法 ,消除了由于组合逻辑输
出带来的毛刺 ,这种 FSM 安全稳定 ,综合后电路速
度快且其面积也更小 ,这将有助于芯片功耗的降
低. 对于 FPGA 和 ASIC 的设计都有重要的参考价
值.
参考文献 :
[1 ] ANSI/ IEEE 1364 - 1995 , IEEE Standard Hardware De2
scription Language Based on the Verilog Hardware De2
scription Language[S].
[2] 夏宇闻. Verilog 数字系统设计教程[M]. 北京 :北京航
空航天大学出版社 ,2003.
[3] Bhasker J . Verilog HDL Synthesis a Practical Primer[M].
孙海平 ,译. 北京 :清华大学出版社 ,2004.
[4] 左长贵 ,朱祥贤. 可编程外围芯片 PSD513 与单片机
MC68332 的接口[J ]. 重庆工学院学报 ,2002(2) :64 -
68.
(责任编辑 陈 松)
(上接第 20 页)
参考文献 :
[1] 沈耀良. 固定化微生物技术及其在废水处理中的应
用[J ]. 污染防治技术 ,1995 ,8(1) :12 - 14.
[2] 范福洲 ,康勇 ,孔琦 ,等. 废水处理用生物膜载体研究
进展[J ]. 化工进展 ,2005 ,12(24) :1331 - 1335.
[3] Masatoshi ,Mat sumura. Tet suya Yamamoto[J ]. Wat Res ,
1997 ,31(5) :1027 - 1034.
[4] Dalmacija B ,Karlovic E ,Tamas Z,et al. Purification of high
- salinity wastewater by activated sludge process[J ]. Wat
Res ,1996 ,30(2) :295 - 298.
[5] Morper M R. Vpgrading of activated sludge system fornitro2
gen removal by application of the LIN POR-CN process[J ].
Wat Res ,1996 ,30(1) :242 - 245.
[6] Fang H P ,Yeong C L ,BOOK KM ,et al. Removal of COD
and nitrogen in wastewater using sequencing batch reactor
with fibrous packing[J ]. Wat Sci Technol ,1993 ,28(7) :
125 - 131.
[7] Zhao Q L , Wang B I. Evaluation on a pilot - scale at2
tached - growth ponds system treating dimestic wastewater
[J ]. Wat Res ,1996 ,30(1) :242 - 245.
[8] Liu Y. Adhesio kinetics of nitrifying bacteria on various
thermoplastic supports[J ]. Colloids and Surfaces B :Bioint2
erfaces ,1995 ,5 :213 - 219.
[9] 刘杰 ,何振坤 ,王绍堂. 炭纤维生物膜的形成机制Ι:
炭纤维表面特性对微生物固着的影响[J ]. 新型炭材
料 ,2001 ,17(3) :20 - 24.
[10] 何振坤 ,刘杰 ,王绍堂. 炭纤维生物膜的形成机制 Ⅱ:
炭纤维表面特性对微生物活性与增殖的影响[J ]. 新
型炭材料 ,2003 ,18(1) :43 - 47.
(责任编辑 陈 松)
85 重 庆 工 学 院 学 报
有限状态机的建模与优化设计.pdf
