基于状态转换图同构求解的等价性验证算法

摘要：

文中提出了一种基于状态转换图同构求解的时序电路等价性验证算法.算法将两时序电路的等价性问题转化为验证相应状态转换图的同构性.首先将初始状态对匹配为待验证对,然后采用递归的方法验证以初始状态对的下一状态对为初始状态的子状态转换图是否同构,从而得到时序电路是否等价的信息.若两状态转换图同构,则两图中的状态均可--配对为待验证状态对,即所有的代验证状态对均为等价状态对.该方法可以有效地克服算法级描述到底层实现之间跨度太大的问题.

关键词：状态转换图、同构、时序电路、等价状态对

所属期刊栏目：19

分类号：TP301.6(计算技术、计算机技术)

资助基金：安徽省高等学校省级自然科学计划项目资助2006KJ013A

在线出版日期：2009-04-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：74-76,83