有限状态机设计策略
有 限状态机设计策略
王 巍 高德远
西 北 工 业 大 学 , 航空微 电子 中心 西 安
摘 要 作为一个数字逻样工程师 , 经 常会碰到设计一个有限状 态机的 问题 。 该 文讨论 了 设计的一 些 注 意事
项 和相应 的 编 程风格 。
关键词 有限状态机 硬件描述语言 编码风格
, , , ’
邵 , ,
,
七 , 加 ,
状态机结构
最一般意义上的时序逻辑可 以用两种逻辑模块予 以定
义 组合逻辑块 用 表示 和寄存器逻辑块 用 表示 。 那
么时序逻辑有 、 、 和 几种类 型 这些类型
定义中信号从左向右流动 , 其中寄存器逻辑块包含沿触发
的触发器和电平触发的锁存器 。 虽然它们都不能称为有限
状态机 , 但可 以利用它们来将复杂设计分解为更简单 、 更可
控的模块 。 一个同步 邢 的一般结构如下图 。
旦
二
别 丫 勺 二
舟 夕 产
状态转移的描述 ④输出的描述 ⑤复位条件 同步或异步 。
在 描述 中 , 当前状态和输人的所有组合都被编
码 , 再针对每种编码给出对应的下一状态和输出值 。 上图中
的状态机既可 以被编码为两个独立的 语句 , 也可以
仅使用一个来描述 。 吻 型状态机适用于单个 语句
描述 , 因为它的输出不仅仅依赖于状态转移 , 而且还依赖于
当前状态 。
下面是一般规则 , 可供参考
· 每个模块只描述一个状态机
· 将无关逻辑减至最少 比如 不要往状态机描述模块
中加人其它无关代码
·
将状态触发器从其他逻辑中分离开来
型状态机示例
司
艺
塑
二
型状态机示例
的当前状态保存在状态存储器中 , 这里的状态存
储器指的是 由同一时钟锁存的一组触发器 。 状态向量 , 也称
为当前状态 , 就是状态存储器中的当前存储值 。 状态机下一
状态是状态 向量和输入的函数 。 街 型状态机的输 出是
状态 向量和输人的函数 而 型状态机的输出仅仅是
状态向量的函数 。
并没有对状态机描述规定一般格式 , 但为 了让
综合工具从 描述识别并综合出状态机来 , 还是要遵
循一定的编码风格 , 基本的 编码风格就是用 语
句或其他的等价方法 比如 一汀 一 玲 来描述 。
状态机描述必须包含以下 内容
①状态变量 , 用于指明状态机所处的状态 ②时钟 ③
状态编码
通常 , 设计状态机时所须作出的最重要 的决定是如何
进行状态编码 。 编码方式不 当会导致状态机 占用过多 的逻
辑 , 或速度太慢 。 目前 已经开发 了一些工具来形成优化的状
态编码 , 典型 的方法有 最少状态位或用类似于 的两
级逻辑来实现 。
·
压缩状态编码 该编码方式中用于存储状态向量的触
发器数量较少 , 但是状态的编码和译码需要额外逻辑 。 常用
的编码方式有 码 、 二进制码和随机码 。
一 编码 在这种编码方式中 , 对应于任何给定状
态的状态 向量各位 中仅有一位置位 , 其它位全为 。 因此 ,
状态的状态机需要 位触发器 。 由于状态 向量中的状态位
直接表示机器状态 , 所以状态译码很简单 , 不需要额外的逻
辑 。 另外 , 它还有其它一些优点 速度快 , 它的速度独立于
状态数量 , 而仅与转移到特定状态的转移数量有关 , 与之相
比 , 压缩状态编码在状态增加时速度会明显下降 不用在
寻找优化的状态编码上花费精力 , 这在修改状态机时显得
特别有效 , 因为对某一特定设计是优化的状态编码 , 在增加
或修改状态后便不能保证是优化的了 , 而 一 编码在
刚燮
作者简介 王巍 , 在职博士 , 助教 , 主要研究方向为 系统设计和电子设计 自动化 。
计算机工程与应用
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
任何情况下都是同样优化 的 一 编码的 易于
设计 , 代码可 以直接从状态转换 图得到 , 而无须再画
一个状态表 易于修改 , 增减状态或改变状态转换条件都
可 以在不影 响状态机的其它部分的情况下很方便 地实现
易于从 综合 与压缩状态编码相 比 , 付出的面
积代价不大 在静态时序分析时 , 容易寻找关键路径
易于调试 , 错误的状态转移和 当前状态的显示都很清晰 。
·
伪 一 编码 如果有两组状态的功能几乎完全相
同 比如控制一个器件 的读写访 问 , 那么 就可 以使用伪
一 编码 , 此时 , 可用一个标志位或状态位来 区别状态
机 目前在哪一组状态 中 , 其余状态位则采用 一 编码 。
因此译码一个状态必须考察两个状态位 。 这种方法在保留
了 一 编码的所有优点的情况下减少 了状态位 。 尽管
标志位是状态 向量的一部分 , 但也可 以将状态触发器的输
出看作状态机的输人之一 。 另一种伪 一 编码将全零
编码为初始状态 , 这样 , 状态机的复位就简化为将所有触发
器清零 , 这一需要 同步复位的情况下非常有用 。
妙 ’ ’
妙 ’ ‘
长
’ ’
匕 ’ ’
下状态 的缺省赋值为全 , 然后在状态转移时某一位
被置位 。 该种编码的好处就是行为级和 门级的仿真情况完
全一致 。
·
伪 一 编码 该种编码与 一 编码 的唯一
区 别在 于要考察 了一个 以 上 的状态位后 方能确定 当前状
态 。
错误恢复与非法状态
有一种观点认为状态机 的状态触发器数量应该最少
即采用压缩状态编码 , 因为这样 , 非法状态 的数量可 以减
至最少 。
但是 , 需要解决一个问题 。 人们希望 , 在状态机失灵产
生非法转移时 , 至少转移的 目标应该是一个合法状态 , 这
样 , 状态机便能恢复工作 。 但通常情况下并非如此 , 因为状
态机结束在一个“ 合法 ”状态上并不意味着它就可 以从错误
中恢复工作 。 假设有这样一种情况 状态机在 状态下
循环 , 直到接收到一个特定信号才退出循环 。 如果在偶然情
况下 , 状态机进人 状态 , 便被挂起而无法恢复工作 ,
因为该特定信号无法产生 。
另一种观点则认为 , 也许应该使用最大数量的状态触
发器 即 一 编码 。 因为在此情况下 , 如果出现错误转
移 , 则状态机几乎一定进人非法状态 由于合法状态仅 占状
态总数的很小一部分 , 一旦外部逻辑检测到非法状态 , 便
可 以采取一些措施 比如将状态机复位 让状态机恢复工作 。
输出的编码
输出的编码方法与状态转移的编码方法类似 , 也是在
语句 中根据状态值或状态转移情况决定输出值 。
如果在某些情况下 , 输出可 以是任意值 , 那么便应该给
它赋值“ ’’ , 这样可 以得到优化的综合结果 。 如果在
语句之前给输出赋一个缺省值 , 那么便可 以保证在状态与
输人所组合形成的任何条件下均有确定的输出值 。 这种缺
省赋值可 以避免在输出上形成锁存 , 而且编码也简化为仅
在需要时修改输出值即可 。 缺省值可 以是 ,’” 、 “ ’’或“ ’’ , 最
好将缺省值赋为 ‘ ,’, , 哪怕需要外加反相器 。 为什么 呢 假
设某个输出仅在一个状态下输出为“ ” , 其余均为 “ ’’ , 那么
综合器会让这个输出就等于某个状态 。 那么再假设某个输
出仅在一个状态下输出为“ ’’ , 其余均为 “ ” , 那么综合器会
让这个输出等于其余所有状态位的或运算 。
对于 一 编码的状态机 , 如果输出恰在某个状态
有效 , 那么便可以让状态位本身作为输 出 。 而且有时 , 将输
出编码为下状态的函数要 比作为当前状态的函数容易些 。
状态转移的编码
状态转移 的编码方法是用 语句来指 明下状态
值 。
· 压缩状态编码 的状态机 这种情况下 , 语句使
用状态 向量作为表达式 。 在 中 , 状态编码被声明为枚
举类型 , 枚举元素的实际值由 预先定义 第一个元素
为 , 然后 , 二 依次类推 。 在 中预先定义状态编码
较为麻烦 , 为了改善这种情况 , 有 的 工具提供 了给枚
举类型规定其实际编码值的方法 。 但并不是所有 的
仿真器都支持这种扩展 , 这意味着行为级和 门级的仿真要
采用不同的编码方式 。
· 一 编码的状态机 在使用 一 编码的状态
机时 , 只须查看状态 向量的一位便可确定状态值 。 在如下
例子中
一 少 ’ , 今
’
’ ’
锁存后 的输出
状态机的输 出可 以被锁存 , 用 简单的 触发器或
触发器均可实现 。 触发器的输出再反馈到状态机作为输人 ,
下一次输出的缺省值就是触发器的当前输 出值 。 如果没有
进一步的赋值 , 则输 出值保存 当然 , 也可 以根据需要来置
位 、 清零或取反 。 型 的锁存输出在使用伪状态位的情况
下特别有效 , 比如在用伪 一 编码时 。
输入
异步输入
有 时 , 状态机 的某些输人信号与时钟异步 , 这就需要
用一个触发器来同步 。 最简单的方法就是在状态机的外部
加同步触发器 , 然后在输人上加足够延时 以确保足够 的触
发器建立时间 。 但这需要将状态机和触发器分别编译 。
不确定输入
当输人在某些确定的时间有效而在其它情况下 是不
确定或异步的话 , 状态机也会出现问题 。 即使在编码时能保
证是在输人稳定时使用信号 , 综合器也可能在编译形成电
路时 , 使得该信号会引发一些状态机误动作 。 唯一的解决方
吓转 页
计算机工程与应用
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
主要侧重对面向对象嵌套结构索引技术的探讨 。
索引是面 向对象数据 中进行快速查询的一项 重要技
术 , 采用合理高效的索引技术 , 可减少磁盘访 问 , 对复杂对
象的 查询而言 , 索引技术对提高查询性能更具有重要
的意义 。 与传统的关系数据库在一个属性或一组属性上建
一个索引有所不同 , 中至少引人了三类新的索引 继
承类层次索引 , 嵌套属性索引及复杂的二维索引 。
· 继承类层次索引 一个继 承类层次索引建立在一个
继承类层次中的类的某个属性上 。 在探讨继承类层次索引
方面 , 传统做法是在继 承层次的每个类上都建一索引 , 这就
是单类索引 。 类层次索引则是在继承类层次上只建一个索
引 , 该索引的索引属性值与继承层次中实例的对象标志符
有关 。 总的说来 , 如果继承层次中有两个以上的类 , 则类层
次索引优于单类索引 。 此外还有 树 一 索引 , 它是
一种根据继承层次而构造的层次索引 。
·
嵌套属性索引 一个嵌套属性索引是建立在 一个聚
集类层次上 。 嵌套属性索引方面已提出的有 多索引
讼 、 路径索引勿 、嵌套索引 及路径
字典索引 等 。 其中路径字典索引存
储开销小 , 而且能提供沿聚集类层次的高效遍历 , 具有较优
的查询性能 。 另外 , 把支持文本检索的签名方法用来 支持
查询是 中索引技术的新研究方向 。
· 二维索引 一个二维索引即一个嵌套属性索引 , 再加
上索引类与索引属性实际所属类之间所有类 的一个类层次
索引 。 嵌套继承索引 一 就是综合考虑
了聚集和继承两方面的一种二维索引 。 实际上它是对路径
索引的扩展 , 增加 了类之间的继承关系 。 对二维索引进行探
讨的文献和书籍 目前还较少 , 然而可 以肯定的是 , 作为对应
于聚集类层次和继承类层次这种可视为正交的二维层次结
构 , 二维索引的研究有重大意义 , 它将随着继承类层次索引
和嵌套属性索引研究的不断深人和成熟而提上 日程 。
逻辑优化与物理优化的结合
查询优化的逻辑层和物理层 的优化是紧密联 系的 , 把
二者截然分开 , 则优化效果就不够好 , 所以应 当在逻辑优化
的同时综合考虑物理优化 , 以达到更好的优化效果 。 文献
【 中就在逻辑优化的同时还考虑了路径索引 、 对象聚集以
及反向属性 、类 中对象个数 、 类 中对象选择谓词 的选择率 ,
谓词的复杂度分类等物理信息进行综合优化 。 这种优化途
径具有较高的实用价值 。
结束语
查询优化和查询处理是数据库系统效率的关键所在 ,
也是今后要发展和完善 必须解决的重大难题之一 。
国内外 己有一些原型系统和商品化的 系统 , 并在研
制和试验这些系统的过程中 , 提出了一 些有价值和有新意
的查询策略 , 有的思想 已 在系统 中得到 了实现 , 有 的则存在
不少 尚待解决的问题 。 查询技术方面的研究虽然成
果不断 , 但问题也不少 , 颇具挑战性 。 参考有关 查询的
文献资料后 , 了解到 查询的研究工作尚处于探讨阶段 ,
但随着研究的不断深入 , 查询的研究必将 日臻完善 。
淀稿 日期 年 月
参考文 献
汪成为 , 郑小军 , 彭木 昌 面 向对象分析 、 设计及应用 北京 国防
工业出版社 ,
肖伟器 , 冯玉才 , 王元珍 面向对象数据库 与关系数据库
之 比较研究 计算机研究与发展 , 犯 一 一
何炎祥等 面 向对象数据库 武汉 武汉大学 出版社 ,
, , 叮 一
,
一
叮 , 、
一 』‘
, 一
, 罗 、。 ,
, ,
一
昊胜利 , 王能斌 面 向对象数据库中基于有向图的联系代数
计算机学报 , 一
高级 功能委员会 第三代数据库系统宣 言 , 计算机科学 ,
一
, , 一
即 罗 部
廖 ‘ , , 一
张成洪 , 施伯乐 , 胡运发 面 向对象数据库的推理查询语言
软件学报 , 赠 刊 一
冯玉才 , 冯铃 面向对象数据库系统的查询处理 计算机研究
与发展 , 一
, 伍。 洲 川 呷 而
一 即 , 滋
, 一
其它参考文献略
上接 页
法就是给这类输人信号加上 门控使能 陈门控信号通 常 由
状态向量译码得到 , 这样便只有在使能信号有效时才会有
可用输人 , 而不会出现不确定情况 。 但有时这种技术会在模
块中形成冗余逻辑 , 导致一些节点不可测 , 于是在形成测试
向量时便会有问题 。
结束语
以上只是作者在工程设计实践中总结 的一些经 验与
体会 , 希望能抛砖引玉 , 共同提高 。 淀稿 日期 年 月
参考文献
以 , 几 著 , 周祖成译 “ 电子设计硬件描述语言 —” 学苑出版社 , 年
计算机工程与应用
? 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
有限状态机设计策略.pdf
