异步电路验证算法  

Verification Algorithms for Asynchronous Circuits

作　　者：茅剑锋[1] 赵千川[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《计算机学报》2004年第1期66-78,共13页Chinese Journal of Computers

基　　金：国家自然科学基金 (60 0 740 12 ;60 2 740 11);国家攀登计划预研项目(970 2 110 17);教育部留学人员回国启动基金;清华大学"九八五"基础研究基金(985信息 0 7 基金 0 7)资助

摘　　要：异步电路因不受时钟偏差的限制而逐渐成为电路设计研究的热点 .发展自动化的验证工具已成为确保大规模异步电路质量和性能的关键 .其核心课题就是建立异步电路的验证算法 .该文整理列举了基于多种数学模型的验证算法 ,如逻辑模型、代数模型、符号模型、数值模型和几何模型的验证算法 ,并从应用的角度将现有的异步电路验证算法分为两类 ,分别是事件时序分析类算法和状态空间搜索类算法 ,从算法的理论基础、应用背景、模型结构、图形描述、适用范围、算法复杂度编程复杂度等多个角度作了比较研究 ,给出了部分代表算法的应用算例 。Verification algorithms for asynchronous circuit are surveyed by selecting several representative ones from five types of model: logic, algebraic, symbolic, numerical and geometrical model and summarized. Those aspects include model structure, graphical specification, problem formulation, theoretical background, computational complexity, and applicable area. All summarizations and comparisons are undertaken in a framework of applications, i.e., all algorithms are classified as two classes by two key problems induced from real applications: timing analysis of events and exploration of state space. Several typical algorithms and their examples of applications are specified. In this paper, a comprehensive map of the asynchronous circuit verification algorithms is revealed for engineers and researchers. And basic principles for choosing appropriate verification algorithms are summarized. In the future, symbolic and approximate method will be the promising directions.

关 键 词：异步电路 计算机辅助电路设计 验证算法 数学模型 逻辑模型 代数模型 符号模型 数值模型 几何模型 

分 类 号：TN702[电子电信—电路与系统]