UIO序列的启发式算法  

Heuristic algorithm for Unique Input/Output sequence generation

作　　者：孙海平[1] 张溯[1] 高明伦[1] 

机构地区：[1]合肥工业大学电气工程学院,安徽合肥230009

出　　处：《合肥工业大学学报（自然科学版）》2001年第4期486-492,共7页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目 ( 6 9876 0 1 0 ) ;国家教委高等学校博士学科点专项科研基金资助 ( 980 3590 1 )

摘　　要：UIO序列是对有限状态机进行功能测试的有效手段 ,在 VLSI设计、通信协议等时序系统中有很强的实际应用背景。文章基于可区分状态组这一概念设计了一个搜索算法 ,进一步利用搜索信息建立了一个基于“小于”关系的启发策略 ,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝 ,新设计出的多路 OPEN/CLOSED表存储机制也加快了相关的判别和处理过程。这些措施改进了搜索过程 ,减少了搜索信息的产生 ,提高了搜索速度。该算法与以往的算法相比 ,在时间和空间两方面都得到了很大改进。Unique Input/Output (UIO) sequence is an efficient method to perform functional test of Finite State Machine (FSM), which arises in many applications, such as VLSI designs, communication protocols,etc. A search algorithm based on Distinguishable State Group (DSG) is described to generate UIO sequence. A heuristic strategy derived from searching information is defined by a 'less' relationship, effective pruning strategies are used to cut off nonsense branches to the greatest extent,and a new store mechanism of multiple OPEN/CLOSED lists is designed to speed up the course of corresponding calculation. By all the optimization steps, the search process is improved and shortened, the data generated in the process are reduced. In comparison with previous algorithms, the presented algorithm shows many improvements in the aspects of time and space.

关 键 词：有限状态机 UIO序列 启发式搜索算法 优化策略 功能测试 搜索速率 剪枝策略 

分 类 号：TN911.23[电子电信—通信与信息系统]